On the complexity of computing determinants
Résumé
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
Domaines
Informatique [cs]| Origine | Fichiers produits par l'(les) auteur(s) |
|---|