{"id":"arxiv/2604.16075","url":"https://arxiv.org/abs/2604.16075","tags":["math.NA","cs.DS","cs.LG","math.OC"],"score":0,"title":"Towards Universal Convergence of Backward Error in Linear System Solvers","domain":"math.NA","source":"arxiv","authors":["Michał Dereziński","Yuji Nakatsukasa","Elizaveta Rebrova"],"reviews":0,"subject":"math.NA","summary":"The quest for an algorithm that solves an $n\\times n$ linear system in $O(n^2)$ time complexity, or $O(n^2 \\text{poly}(1/ε))$ when solving up to $ε$ relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science. There are two predominant paradigms for measuring relative error: forward error (i.e., distance from the output to the optimum solution) and backward error (i.e., distance to the nearest problem solved by the output). In most prior studies, convergence of iterative linear system solvers is measured via various notions of forward error,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-17","reactions":{}}