CS Paper Radar

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

Jonathan A. Kelner

cs.DS cs.CCmath.NA ·submitted 2026-09-29 17:44 UTC · v1

Abstract

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 $κ$, to any relative residual tolerance $0<ε\le1/2$ using $\widetilde{O(}mn\log(κ/ε))$ 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 $ε$-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 $κ$.

Closest papers

Nearest neighbours by meaning across the whole index.

Fast Spectral Signing for Vector Balancing

cs.DS ·2026-09-24 ·Xiaoyu Li
theoryhighly cited similarity 0.69
Abstract

The Komlós conjecture, now a theorem, asserts that whenever the columns of a matrix $A\in\mathbb{R}^{m\times n}$ have Euclidean norm at most one, some signs $\varepsilon\in\{-1,1\}^n$ make every coordinate of $A\varepsilon$ bounded by an absolute constant. Guo, Fang, and Lu gave the first polynomial-time algorithm for finding such signs, a deterministic spectral signing procedure with discrepancy $8272$ and running time $O((mn^9+n^{10})\log(m+n))$. We give a deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations, where $ω>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $ω$ this is $\widetilde O(mn+n^{4.372})$. Our algorithm uses the same framework: it rounds a single fractional coloring and watches all rows through the top eigenvalue of a Gram matrix of energy-corrected barriers. Steps follow flat directions, rescaled so that no barrier near its threshold moves faster than a constant, and the regularizer grows as coordinates freeze; together these bound the number of updates by $O(n^2\log n)$. A weak quadratic charge on the tracked row sums leaves $O(n\log^2 n)$ rows to evaluate at any time, and a motion clock bounds when any other row could approach its barrier. Each update is a short sequence of matrix products. Its direction is read off by conditional expectations from a polynomial soft projector, its small constraint residual is repaired in affine row representations, and one identity accounts for every change of representation. For rational input the algorithm has polynomial bit complexity.

0.32

Sparse Matrix Multiplication Exponent 1.5 in the Low-bandwidth Model

cs.DC cs.DS ·2026-11-11 ·Chetan Gupta, Jukka Suomela, Hossein Vahidi
theory similarity 0.66
Abstract · Lean formalization available at https://doi.org/10.5281/zenodo.24127514

We study sparse matrix multiplication in the low-bandwidth model: $n$ computers multiply two $n\times n$ matrices, and each computer can send and receive one $O(\log n)$-bit message per round. The input matrices are uniformly sparse, meaning that there are at most $d$ nonzero entries in each row and column, and the task is to compute a uniformly sparse part of their product. In prior work, Gupta et al.~(SPAA 2022) presented an $O(d^{1.907})$-round algorithm over fields for this problem when the sparsity structure is globally known in advance (this is referred to as the supported setting). The upper bound was later improved to $O(d^{1.832})$ rounds. In this work, we give a deterministic algorithm that solves this problem in $O(d^{3/2})$ rounds in the supported setting, improving the previous bounds over fields and semirings.

0.14

The Komlós Problem in Matrix-Multiplication Time

cs.DS cs.DM ·2026-10-14 ·Emile Anand, Peter Chen
similarity 0.65
Abstract · 30 pages

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^ω)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $ω$ is the exponent of matrix multiplication. The previous fastest algorithm with a constant discrepancy bound, due to Li, is deterministic and uses $O(mn+n^{ω+2}\log^3 n)$ arithmetic operations. We build on the spectral signing framework of Guo, Fang, and Lu and of Li, which rounds a single fractional coloring while one spectral potential controls every row. Li's potential tracks a top eigenvalue, and the gap below that eigenvalue, which can be of order $1/n$, limits the length of every step. We replace it with a resolvent potential that is smooth without any gap condition, and we draw step signs at random, so that the potential only needs to be concave while progress is measured separately. Our key insight is to reuse a single subspace of directions throughout a batch of steps, thereby using only one spectral computation, so that the more expensive linear algebraic operations are paid for only polylogarithmically often at each scale. Within a batch, we sample directions from a Gaussian completion matrix whose inverse we maintain under rank-one row replacements. Finally, we use a finite-precision analysis to prove stability of the algorithm and attain the bit-complexity bound.

0.39

Faster Linear Programming with $\sqrt{\mathrm{rank}}$ Linear System Solves

cs.DS math.OC ·2026-09-25 ·Zhao Song
similarity 0.65
Abstract

Lee and Sidford [LS19] showed that the linear program $\min\{c^\top x\ :\ A^\top x=b,\ l\leq x\leq u\}$ over $x\in\mathbb{R}^m$, where $A\in\mathbb{R}^{m\times n}$, can be solved to accuracy $ε$ using $O(\sqrt n\log^{13}m\cdot\log(mU/ε))$ solves of linear systems in $A^\top\mathbf DA$ for positive diagonal matrices $\mathbf D$, where $U$ bounds the magnitudes of the input and of the initial point. Theirs is the first such bound governed by $\mathrm{rank}(A)=n$ rather than by the number of constraints $m$. Song [Son19] mentioned that reducing the $\log^{13}m$ factor is an interesting future direction. Given an interior point and a finite certified magnitude bound $U$, we give an algorithm that uses $O(\sqrt n\log^{4}m\cdot\log(mU/ε))$ solves of such linear systems, improving the Lee--Sidford bound by a factor of $\log^{9}m$. We conjecture that $O(\sqrt n\log(mU/ε))$ such linear-system solves suffice.

0.26

A Fast and Accurate Algorithm for the $p \to q$ Norm of Sparse Non-Negative Matrices

cs.DS ·2026-11-06 ·Marco Pirazzini, Daniel A. Spielman
similarity 0.65
Abstract · 31 pages, 6 figures

We present an algorithm that computes the $p \to q$ norm of a non-negative matrix with $s$ nonzero entries to accuracy $\varepsilon$ in time $\widetilde{O}(s^{3/2} \log (1/\varepsilon))$, for any $p \ge q \ge 1$. The fastest algorithm previously designed for this problem has running time $\widetilde{O}(s / \varepsilon)$ (Objois and Vladu, 2026), which is slower when high accuracy solutions are desired. Our algorithm employs a surprising application of Laplacian solvers inside an Interior Point Method (IPM). We formulate the problem as a linear optimization problem over a product of power cones, and show that the Newton updates of the IPM can be computed by solving a Laplacian system in a Schur complement after subtracting a rank-2 matrix. We also discuss an implementation of our algorithm, showing that it is practical and it outperforms optimized solvers such as MOSEK by factors of up to $20\times$ on a variety of tasks.

0.31

Solving Linear Programs in the Matrix Multiplication Time

cs.DS ·2026-11-05 ·Zhao Song
similarity 0.64
Abstract · 124 pages, 5 figures

We give a randomized algorithm for feasible bounded-box linear programs with $n$ variables and $d\le n=O(d)$ linearly independent equality constraints. For additive accuracy $ε$, its expected running time is $O((n^ω+n^2\log n)\log(1/ε))$, where $ω$ is the matrix multiplication exponent. This answers the matrix-multiplication-time open question posted in Song's Ph.D. thesis [Son19] in this setting.

0.34

Strongly Refuting Semirandom Linear Systems in Subexponential Time

cs.DS ·2026-09-24 ·Pravesh K. Kothari, Andrew D. Lin, Peter Manohar
theory similarity 0.63
Abstract

In this paper, we consider the problem of refuting $\mathbb{F}_2$-linear equations with random right-hand sides. Formally, we give a sub-exponential $2^{O(n/\log n)}$-time randomized algorithm that takes as input an arbitrary $m \times n$ matrix $A$ and a uniformly random vector $b \in \mathbb{F}_2^m$, and outputs a witness showing that no assignment satisfies more than a $\frac{1}{2}+ε$ fraction of the equations provided that $m \geq 2^{O(n/\log n)}$. The setting above is the semirandom refutation variant of the famous work [BKW03] that gives a $2^{O(n/\log n)}$-time search algorithm for the learning parity with noise (LPN) problem with $m \geq 2^{O(n/\log n)}$ equations. Building on the search algorithm of [Lyub05], we also give a $2^{O(n/\log \log n)}$-time refutation algorithm that succeeds with only $m \geq n^{1 + γ}$ equations, for a small constant $γ$. Finally, we prove that our algorithm is not captured by the sum-of-squares hierarchy by proving a degree-$Ω(n)$ sum-of-squares lower bound, showing that ''[BKW03]-style'' algorithms achieve better runtime than can be done under sum-of-squares. We thus obtain a natural example of a noise-tolerant signal recovery problem that exhibits a nontrivial gap between the performance of efficient algorithms and that of those based on the sum-of-squares hierarchy.

0.35

Even Faster Algorithms for Bounded Integer Programming

cs.DS ·2026-11-18 ·Lin Chen, Yuchen Mao, Guochuan Zhang
similarity 0.63
Abstract

We study integer programs $\min\{\mathbf{c}^{T}\mathbf{x}: A\mathbf{x}=\mathbf{b},\mathbf{l}\le\mathbf{x}\le\mathbf{u},\mathbf{x}\in\mathbb{Z}^n\}$ with a fixed number $d$ of equality constraints and constraint coefficients of absolute value at most $N$. Chen, Mao, and Zhang recently solved such programs in almost $N^{2d}$ time. We show that any polynomial saving for $(\min,+)$-convolution carries over to this problem. If witnessed $(\min,+)$-convolution of arrays of length $m$ can be computed in $\tilde{O}(m^ρ)$ time with error probability $p$, then for every $\varepsilon>0$ bounded integer programming can be solved in $\tilde{O}\bigl(n+N^{(\max\{ρ,3/2\}+\varepsilon)d}\bigr)$ time with the same error probability $p$, up to polynomial factors in the encoding length and the cost of one linear program. A deterministic convolution algorithm yields a deterministic integer programming algorithm. Combined with recent truly subquadratic algorithms for $(\min,+)$-convolution, this gives a deterministic algorithm running in $\tilde{O}(n+N^{1.99986\,d})$ time and a randomized algorithm running in $\tilde{O}(n+N^{1.9602\,d})$ time, up to the same factors.

0.09