On the complexity of inverting integer and polynomial matrices

DOI10.1007/s00037-015-0106-7zbMath1333.68302OpenAlexW1862524307MaRDI QIDQ901933

Arne Storjohann

Publication date: 6 January 2016

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0106-7

zbMATH Keywords

randomized algorithminteger matrixpolynomial matrixSmith normal formmatrix inversebit complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Theory of matrix inversion and generalized inverses (15A09) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Matrices over function rings in one or more variables (15A54) Randomized algorithms (68W20)

Related Items (4)

Fast, deterministic computation of the Hermite normal form and determinant of a polynomial matrix ⋮ Čech type approach to computing homology of maps ⋮ Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation ⋮ A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact solution of linear equations using p-adic expansions
• Essentially optimal computation of the inverse of generic polynomial matrices
• On the complexity of computing determinants
• A deterministic algorithm for inverting a polynomial matrix
• The shifted number system for fast linear algebra on integer matrices
• Fast multiplication of large numbers
• Fast computation of continued fraction expansions.
• Certified dense linear system solving
• Fast Integer Multiplication Using Modular Arithmetic
• Modern Computer Algebra
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Worst-Case Complexity Bounds on Algorithms for Computing the Canonical Structure of Finite Abelian Groups and the Hermite and Smith Normal Forms of an Integer Matrix
• Additive Preconditioning for Matrix Computations
• Faster Integer Multiplication
• Asymptotically Fast Triangularization of Matrices over Rings
• Computing hermite forms of polynomial matrices
• Elementary Divisors and Modules

This page was built for publication: On the complexity of inverting integer and polynomial matrices