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

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

Gilles Villard, Erich L. Kaltofen

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

algorithmsRandomized algorithmssignDeterminantApproximate computationBit-complexityExact computationInteger matrix

Mathematics Subject Classification ID

Numerical computation of determinants (65F40) Complexity and performance of numerical algorithms (65Y20) Matrices of integers (15B36)

Related Items

Faster geometric algorithms via dynamic determinant computation, The shifted number system for fast linear algebra on integer matrices, On the extension of Sarrus' rule to \(n \times n\) (\(n > 3\)) matrices: development of new method for the computation of the determinant of \(4 \times 4\) matrix, On the computation of the HNF of a module over the ring of integers of a number field, Some inequalities related to the Seysen measure of a lattice, Rational univariate reduction via toric resultants, Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme

Uses Software

• mctoolbox
• MAPC
• Hull

Cites Work

• 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
• 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