The shifted number system for fast linear algebra on integer matrices

DOI10.1016/j.jco.2005.04.002zbMath1101.68045OpenAlexW2146380740MaRDI QIDQ2387425

Arne Storjohann

Publication date: 2 September 2005

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

Full work available at URL: https://doi.org/10.1016/j.jco.2005.04.002

zbMATH Keywords

Las Vegas algorithmsMatrix multiplicationInteger matrixBit complexityMatrix determinantLinear system solving

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity and performance of numerical algorithms (65Y20) Numerical linear algebra (65F99)

Related Items (15)

Solving equations and optimization problems with uncertainty ⋮ Schur aggregation for linear systems and determinants ⋮ A proof of the conjectured run time of the Hafner-McCurley class group algorithm ⋮ Fast Cauchy sum algorithms for polynomial zeros and matrix eigenvalues ⋮ Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x\)] ⋮ On the complexity of inverting integer and polynomial matrices ⋮ Counting solutions of a polynomial system locally and exactly ⋮ Hardness of graph-structured algebraic and symbolic problems ⋮ Generalized fraction-free \(LU\) factorization for singular systems with kernel extraction ⋮ Foreword ⋮ Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation ⋮ Improved algorithms for computing determinants and resultants ⋮ Fast computation of Hermite normal forms of random integer matrices ⋮ Algorithms for solving linear systems over cyclotomic fields ⋮ A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix

Uses Software

• ATLAS
• gmp
• IML - Integer Matrix Library

Cites Work

• Parallel algorithms for matrix normal forms
• Matrix multiplication via arithmetic progressions
• Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations
• Exact solution of linear equations using p-adic expansions
• Rectangular matrix multiplication revisited
• Computing the sign or the value of the determinant of an integer matrix, a complexity survey.
• Improved algorithms for computing determinants and resultants
• On the complexity of computing determinants
• High-order lifting and integrality certification
• Efficient exact evaluation of signs of determinants
• Gaussian elimination is not optimal
• On the computational power of pushdown automata
• Fast multiplication of large numbers
• Fast computation of continued fraction expansions.
• Approximate formulas for some functions of prime numbers
• Certified dense linear system solving
• A generalization of the fast LUP matrix decomposition algorithm and applications
• Asymptotically Fast Triangularization of Matrices over Rings
• Matrix rank certification
• On Rational Number Reconstruction and Approximation
• Nearly Optimal Algorithms for Canonical Matrix Forms
• A BLAS based C library for exact linear algebra on integer matrices
• Automated empirical optimizations of software and the ATLAS project
• 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

This page was built for publication: The shifted number system for fast linear algebra on integer matrices