Computing the sign or the value of the determinant of an integer matrix, a complexity survey.

DOI10.1016/j.cam.2003.08.019zbMath1037.65044MaRDI QIDQ1421221

Erich L. Kaltofen, Gilles Villard

Publication date: 26 January 2004

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cam.2003.08.019

zbMATH Keywords

algorithms; Randomized algorithms; sign; Determinant; Approximate computation; Bit-complexity; Exact computation; Integer matrix

Mathematics Subject Classification ID

65F40: Numerical computation of determinants

65Y20: Complexity and performance of numerical algorithms

15B36: Matrices of integers

Related Items

Faster geometric algorithms via dynamic determinant computation, Some inequalities related to the Seysen measure of a lattice, Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme, The shifted number system for fast linear algebra on integer matrices, Rational univariate reduction via toric resultants

Uses Software

• mctoolbox
• MAPC
• Hull

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Evaluating signs of determinants using single-precision arithmetic
• Matrix multiplication via arithmetic progressions
• Complexity of parallel matrix computations
• Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations
• Factoring polynomials with rational coefficients
• Exact solution of linear equations using p-adic expansions
• The complexity of partial derivatives
• Fast rectangular matrix multiplication and applications
• Sign determination in residue number systems
• Efficient matrix preconditioners for black box linear algebra
• Rectangular matrix multiplication revisited
• The complexity of matrix rank and feasible systems of linear equations
• Efficient exact evaluation of signs of determinants
• Gaussian elimination is not optimal
• Fast multiplication of large numbers
• Certified dense linear system solving
• Hermite Normal Form Computation Using Modulo Determinant Arithmetic
• Solving sparse linear equations over finite fields
• Congruence Techniques for the Exact Solution of Integer Systems of Linear Equations
• Solving Homogeneous Linear Equations Over GF(2) via Block Wiedemann Algorithm
• Stability of block algorithms with fast level-3 BLAS
• Triangular Factorization and Inversion by Fast Matrix Multiplication
• A Complete Implementation for Computing General Dimensional Convex Hulls
• Analysis of Coppersmith's Block Wiedemann Algorithm for the Parallel Solution of Sparse Linear Systems
• Systems of distinct representatives and linear algebra
• Computational Solutions of Matrix Problems Over an Integral Domain
• Certification of numerical computation of the sign of the determinant of a matrix
• Fast computation of the Smith form of a sparse integer matrix