The shifted number system for fast linear algebra on integer matrices
From MaRDI portal
Publication:2387425
DOI10.1016/j.jco.2005.04.002zbMath1101.68045OpenAlexW2146380740MaRDI QIDQ2387425
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
Las Vegas algorithmsMatrix multiplicationInteger matrixBit complexityMatrix determinantLinear system solving
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
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
