Geodesic
Calculation of the characteristic polynomial of a~matrix
Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 28-45.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider efficient algorithms of calculation of the characteristic polynomials of matrices over commutative rings. We give estimates of complexity treated as the number of ring operations, and for the ring of integers the estimates are presented in terms of the number of multiplication operations over the machine words. We suggest a new algorithm to calculate the characteristic polynomial which has the best estimate of complexity in the ring operations. We give recommendations concerning applications of the algorithm of calculation of the characteristic polynomials depending on the size of the matrix, in particular, the algorithm suggested in this paper is recommended to be applied to integer-element matrices of size greater than 60. 
@article{DM_2011_23_1_a2,
     author = {O. N. Pereslavtseva},
     title = {Calculation of the characteristic polynomial of a~matrix},
     journal = {Diskretnaya Matematika},
     pages = {28--45},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_1_a2/}
}
TY  - JOUR
AU  - O. N. Pereslavtseva
TI  - Calculation of the characteristic polynomial of a~matrix
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 28
EP  - 45
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_1_a2/
LA  - ru
ID  - DM_2011_23_1_a2
ER  - 
%0 Journal Article
%A O. N. Pereslavtseva
%T Calculation of the characteristic polynomial of a~matrix
%J Diskretnaya Matematika
%D 2011
%P 28-45
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_1_a2/
%G ru
%F DM_2011_23_1_a2
O. N. Pereslavtseva. Calculation of the characteristic polynomial of a~matrix. Diskretnaya Matematika, Tome 23 (2011) no. 1, pp. 28-45. http://geodesic.mathdoc.fr/item/DM_2011_23_1_a2/

[1] Le Verrier U. J. J., “Sur les variations séculaires des éléments elliptiques des sept planètes principales: Mercure, Vénus, la Terre, Mars, Jupiter, Saturne et Uranus”, J. de Mathématiques Pures et Appliquées, 5 (1840), 220–254

[2] Faddeev D. K., Faddeeva V. N., Vychislitelnye metody lineinoi algebry, GIFML, Moskva–Leningrad, 1963 | MR

[3] Knut D. E., Iskusstvo programmirovaniya dlya EVM, v. 2, Mir, Moskva, 1977 | Zbl

[4] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[5] Chistov A. L., “Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic”, Lecture Notes Computer Sci., 199, 1985, 147–150 | MR

[6] Seifullin T. R., “Vychislenie opredelitelya, prisoedinennoi matritsy i kharakteristicheskogo polinoma bez deleniya”, Kibernetika i sistemnyi analiz, 38:5 (2002), 18–42 | MR | Zbl

[7] Berkowitz S. J., “On computing the determinant in small parallel time using a small number of processors”, Inform. Process. Lett., 18 (1984), 147–150 | DOI | MR | Zbl

[8] Malashonok G. I., “A computation of the characteristic polynomial of an endomorphism of a free module”, J. Math. Sci., 108 (2002), 966–976 | DOI | MR

[9] Pereslavtseva O. N., “Istoriya i sovremennoe sostoyanie teorii algoritmov vychisleniya kharakteristicheskogo polinoma matritsy”, Trudy Mezhdunarodnoi nauchnoi konferentsii “Sovremennoe matematicheskoe obrazovanie i problemy istorii i metodologii matematiki”, Pershin, Tambov, 2006, 130–134

[10] Malashonok G. I., Matrichnye metody vychislenii v kommutativnykh koltsakh, Izd-vo Tambovskogo gos. un-ta, Tambov, 2002

[11] Pereslavtseva O. N., “Metod vychisleniya kharakteristicheskogo polinoma matritsy”, Vestnik Tambovskogo Universiteta. Ser. Estestvennye i Tekhnicheskie Nauki, 13:1 (2008), 131–133

[12] Dumas J.-G., Pernet C., Wan Z., “Efficient computation of the characteristic polynomial”, Proc. ISSAC' 05, ed. M. Kauers, ACM, New York, 2005, 140–147 | MR