On the complexity of computing determinants - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

On the complexity of computing determinants


By combining Kaltofen's 1992 baby steps/giant steps technique for Wiedemann's 1986 determinant algorithm with Coppersmith's 1994 projections by a block of vectors in the Wiedemann approach and Villard's 1997 analysis of the block technique, we obtain new algorithms for dense matrix problems of asymptotically fast running time. The rst category of problems is for a dense nn matrix A with integer entries. We express the cost in terms of bit operations on the exact integers and denote by kAk the largest entry in absolute value. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of A in (n and (n bit operations, where the exponent adjustment by +o(1) captures additional factors C1(log n) for positive real constants C1 , C2 , C3 and where the rst, asymptotically slower bit complexity does not require any of the sub-cubic matrix multiplication algorithms. Our algorithms are randomized, and we can certify the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n ring additions, subtractions and multiplications, that without utilizing sub-cubic matrix multiplication algorithms. With the asymptotically fast matrix multiplication algorithms by Coppersmith and Winograd our method computes the determinant and adjoint in O(n ) ring operations and the characteristic polynomial in O(n ) ring operations. We achieve our results in part through new proofs for Villard's 1997 analysis of the block Wiedemann/Lanczos algorithm and a genralisation od the Knuth/Schönhage/Moenck Euclidean remainder sequence algorithm to matrix polynomials
Fichier principal
Vignette du fichier
RR2003-36.pdf (520.07 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02102099 , version 1 (17-04-2019)


  • HAL Id : hal-02102099 , version 1


Erich Kaltofen, Gilles Villard. On the complexity of computing determinants. [Research Report] LIP RR-2003-36, Laboratoire de l'informatique du parallélisme. 2003, 2+35p. ⟨hal-02102099⟩
62 Consultations
2187 Téléchargements


Gmail Mastodon Facebook X LinkedIn More