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

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