О вычислении коэффициентов характеристического полинома

Авторы

  • О.Н. Переславцева

Ключевые слова:

характеристический полином
вычислительная сложность
параллельные алгоритмы

Аннотация

Рассматриваются алгоритмы вычисления точных значений коэффициентов характеристических полиномов матриц больших порядков. Даются рекомендации по применению этих алгоритмов в зависимости от размера матрицы. Обсуждается параллельная реализация алгоритмов. Приводятся результаты экспериментов для последовательных и параллельных вычислительных систем. Ключевые слова: характеристический полином, вычислительная сложность, параллельные алгоритмы


Загрузки

Опубликован

2008-10-10

Выпуск

Раздел

Раздел 1. Вычислительные методы и приложения

Автор

О.Н. Переславцева


Библиографические ссылки

  1. Le Verrier U.J. J. Sur les variations séculaires des éléments elliptiques des sept planétes principales: Mercure, Venus, La Terre, Mars, Jupiter, Saturne et Uranus // J. de Mathématiques Pures et Appliquees. 1840. N 4. 220-254.
  2. Воронов В.С. Показатели устойчивости и качества робастных систем управления // Изв. РАН. Теория и системы управления. 1995. № 6. 49-54.
  3. Robuk V.N. A constructive formula for function of matrix. Alternative to the Lagrange -Silvester formula // Nuclear Instruments and Methods in Physics Research. 2004. T. A 534. 319-323.
  4. Крылов А.Н. О численном решении уравнения, которым в технических вопросах определяются частоты малых колебаний материальных систем. Собрание сочинений. 5. М.: Изд-во АН СССР, 1937.
  5. Виленкин Н.Я. Специальные функции и теория представлений групп. М.: Наука, 1991.
  6. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М., Л.: Физматлит, 1963.
  7. Chistov A.L. Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic // Proc. FCT’85. Springer Lecture Notes in Computer Science. Volume 199. Berlin: Springer, 1985. 147-150.
  8. Сейфуллин Т.Р. Вычисление определителя, присоединенной матрицы и характеристического полинома без деления // Кибернетика и системный анализ. 2002. № 5. 18-42.
  9. Переславцева О.Н. Об оценке коэффициентов характеристического полинома // Вестник Тамбовского ун-та. Сер. «Естественные и технические науки». 2008. 13, вып. 1. 124-126.
  10. Berkowitz S.J. On computing the determinant in small parallel time using a small number of processors // Information Processing Letters. 1984. 18. 147-150.
  11. Малашонок Г.И. A computation of the characteristic polynomial of an endomorphism of a free module // Записки научных семинаров ЛОМИ. 1999. 258. 101-114.
  12. Переславцева О.Н. Метод вычисления характеристического полинома матрицы // Вестник Тамбовского ун-та. Сер. «Естественные и технические науки». 2008. 13, вып. 1. 131-133.
  13. Икрамов Х.Д. О конечных спектральных процедурах в линейной алгебре // Программирование. 1994. № 1. 56-69.
  14. Данилевский А.М. О численном решении векового уравнения // Матем. сб. 1937. T. 2(44), № 1. 169-172.
  15. Переславцева О.Н. Вычислительные эксперименты с алгоритмами вычисления характеристических полиномов матриц // Вестник Тамбовского ун-та. Сер. «Естественные и технические науки». 2007. 12, вып. 1. 126-128.
  16. Переславцева О.Н. Вычисление характеристического полинома в кольце целых чисел // Proc. Int. Conf. on Polynomial Computer Algebra. Санкт-Петербург, 2008. 57-61.