Metraipolis › archive › dc_fd9d8698bfcc

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations — arXiv:2609.38101

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.38101
License (as archived): CC0-1.0
Archived: 2026-10-07T18:06:31.966Z
SHA-256 of the archived text: 4ee6f81d9e735ebc59b17e5fd36d891fac5c1eb947870c7f75bbdbf6f0796d42
Stable URL of this page: https://metraipolis.com/documento/dc_fd9d8698bfcc

How to cite

Solving Linear Systems in $\widetilde{O}(mn \log \fracκε)$ Bit Operations — arXiv:2609.38101 — arXiv (en), https://arxiv.org/abs/2609.38101 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd9d8698bfcc (Metraipolis archive dc_fd9d8698bfcc, sha256 4ee6f81d9e735ebc59b17e5fd36d891fac5c1eb947870c7f75bbdbf6f0796d42)

BibTeX

@misc{dcfd9d8698bfcc,
  title = {Solving Linear Systems in $widetildeO(mn log fracκε)$ Bit Operations — arXiv:2609.38101},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.38101},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd9d8698bfcc; sha256 4ee6f81d9e735ebc59b17e5fd36d891fac5c1eb947870c7f75bbdbf6f0796d42},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.38101. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We give a deterministic algorithm that solves a nonsingular linear system $Ax=b$, where $A\in\mathbb{R}^{n\times n}$ has $m$ nonzero entries and condition number $\kappa$, to any relative residual tolerance $0<\epsilon\le1/2$ using $\widetilde{O(}mn\log(\kappa/\epsilon))$ bit operations for inputs with logarithmically many bits per entry. For sparse, polynomially conditioned systems with $m=\widetilde{O}(n)$, this gives an $\widetilde{O}(n^2)$ algorithm for any inverse-polynomial accuracy, improving on the algorithm of Peng and Vempala, as sharpened by Nie, whose running time in this regime is approximately $O(n^{2.2707})$ with the best current matrix multiplication exponent, and largely closing a gap between the idealized performance of the conjugate gradient method in exact arithmetic and the running time achievable with finite-precision computation that has persisted for over 70 years. The algorithm is surprisingly simple. For integer inputs, we apply Dixon's lifting algorithm to the perturbed system $(A+I/R)x=b$ for a suitable integer $R$. After scaling, the matrix of this system is $RA+I\equiv I\pmod R$, so its modular inverse is trivial, and each lifting step needs only a sparse matrix-vector product with $A$ on $O(\log R)$-bit numbers. Fast rational reconstruction then recovers the exact solution of the perturbed system, which is an $\epsilon$-accurate solution of the original one. Normalization and rounding extend the result to fixed-point and floating-point inputs, with floating-point outputs represented using short integer significands and a common encoded exponent. A computable certificate removes the need for prior knowledge of $\kappa$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.NA).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Computational Complexity (cs.CC); Numerical Analysis (math.NA).
Pagina del lavoro: https://arxiv.org/abs/2609.38101 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T17:39:14.425Z dalla pagina https://arxiv.org/catchup/math.NA/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).