Rump, Siegfried M.Siegfried M.Rump2026-10-292026-10-292026-10-08SIAM Journal on Matrix Analysis and Applications 47 (4): 1739-1784 (2026)https://hdl.handle.net/11420/65616Verification methods provide mathematically correct error bounds for the solution of a numerical problem. That includes the proof of solvability of the problem and often uniqueness of the solution within the computed bounds. There are many verification methods for standard problems in numerical analysis, including linear and nonlinear systems of equations, matrix decompositions, eigenproblems, local and global optimization, and ordinary and partial differential equations. Many of those are included in INTLAB, the MATLAB/Octave toolbox for reliable computing. Despite several efforts, the verified solution of general sparse linear systems was an open problem. There are satisfactory algorithms for systems with symmetric positive definite input matrix. To that end error bounds for the solution of \(Ax=b\) with general matrix \(A\) could be computed using \(A^TAx = A^T b\), but that reduces the applicability in double precision to matrices with condition number up to \(10^8\). We give in this note an algorithm to compute entrywise error bounds for the solution of general real or complex sparse systems with condition number up to the limit \(10^{16}\). Our algorithm splits into three subalgorithms for symmetric positive definite, symmetric indefinite, and general input matrix \(A\). It is based on a mathematically correct lower bound on the smallest singular value \(\sigma_{\min }(A)\). A key point is a factorization \(A \approx L_1L_2\) such that \(L_1\) and \(L_2\) have identical sets of singular values with the smallest one close to \(\sigma_{\min }(A)^{1/2}\). A mathematically correct lower bound on \(\sigma_{\min }(L_1)=\sigma_{\min }(L_2)\) is then computed using \(L_1^T L_1\). Numerical evidence suggests that bounds for the solution of a linear system are computed for condition numbers up to \(10^{16}\), and that often the bounds for all entries are close to maximally accurate, i.e., the bounds differ by few bits. We present a new a priori error bound based on Perron–Frobenius theory on the residual of a floating-point Cholesky decomposition which improves on existing ones by some two orders of magnitude. Our three subalgorithms benefit from this new bound. Based on the results in this Part I, an alternative approach will be presented in Part II of this note. Those methods are somewhat simpler, but often slower. However, they seem to be more robust, i.e., produce verified inclusions where the methods of Part I fail. Both approaches for square linear systems will be used in Part II of this note to compute verified error bounds for the solution of least squares problems and for underdetermined linear systems. Moreover, inclusions of the solution of general real or complex systems of nonlinear equations with sparse Jacobi matrix are computed by transforming the problem into a linear system with point matrix and interval right-hand side.en1095-71622026417391784Society for Industrial & Applied Mathematics (SIAM)accurate dot productsINTLABlower bound on the smallest singular valuemathematically correct error boundssparse linear systemsverification methodsComputer Science, Information and General Works::005: Computer Programming, Programs, Data and SecurityNatural Sciences and Mathematics::510: MathematicsJournal Article10.1137/25M1722573