Solving Linear Systems in \widetilde{O}(mn \log \fracκε) Bit Operations

DOI10.48550/arXiv.2609.38101MaRDI QIDQ7360719arXivFDO

Authors Jonathan A. Kelner

Publication date 29 September 2026

Published in arXiv

Tldr We solve linear systems in O(mn log(κ/ε)) bit operations using a new algorithm that scales up the standard conjugate gradient method via modular arithmetic, achieving a long-sought goal that has eluded researchers for over 70 years.

Full work available at URL https://doi.org/10.48550/arXiv.2609.38101

arXiv classification

cs.CCcs.DSmath.NA

Cites work

• Acceleration of Euclidean Algorithm and Rational Number Reconstruction
• Behavior of slightly perturbed Lanczos and conjugate-gradient recurrences
• Efficient rational number reconstruction
• Exact solution of linear equations using p-adic expansions
• Fast linear algebra is stable
• Matrix anti-concentration inequalities with applications
• Maximal quotient rational reconstruction
• Methods of conjugate gradients for solving linear systems
• Modern computer arithmetic
• On Rational Number Reconstruction and Approximation
• P-adic reconstruction of rational numbers
• Solving sparse linear systems faster than matrix multiplication
• Stability of the Lanczos method for matrix function approximation
• Triangular factorization and inversion by fast matrix multiplication

This page was built for publication: Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7360719)