Verified linear algebra
- Cost
- ball operations for interval LU decomposition; preconditioned solving costs an approximate LU decomposition in floating-point arithmetic, two or three ball matrix products and an interval LU decomposition or a norm bound, which is with fast ball matrix multiplication.
Let be an matrix and an matrix with ball entries. Solving rigorously means computing a ball matrix that contains for every pair of matrices , with entries in the balls of and , or reporting failure if this cannot be done (in particular if the balls of contain a singular matrix). There are two basic approaches: carry out an exact algorithm (Gaussian elimination) in ball arithmetic, or compute an approximate solution in floating-point arithmetic and then prove an error bound for it [Rum2010]. FLINT uses both, depending on the dimension and the precision.
Interval Gaussian elimination#
Gaussian elimination with partial pivoting in ball arithmetic (arb_mat_lu) chooses as pivot in each column an entry whose ball does not contain zero, among those the one with the largest midpoint, and fails if all candidates contain zero. The resulting balls contain the factors of every matrix in the balls of (with the same permutation), so triangular solving in ball arithmetic (arb_mat_solve_lu_precomp) then gives a correct enclosure of the solution. Success proves that every matrix in the balls is nonsingular.
The weakness is radius growth. Each elimination step computes and the radius of the result includes the radii of all three inputs multiplied by the magnitudes of the others; the errors introduced in one step are treated as independent in the next, although they are strongly correlated. As a result, the radii can grow exponentially with even for well-conditioned matrices, so that bits or more are lost [HS1967]. If the precision is large compared to , a loss of bits is harmless, and interval elimination is the fastest method; this is why arb_mat_solve uses it when or . The recursive LU decomposition (arb_mat_lu_recursive, for ) performs most of the work in ball matrix products and has the same behaviour.
Preconditioning#
Hansen and Smith [HS1967] observed that the radius growth disappears if the system is first multiplied by an approximate inverse (a matrix with exact floating-point entries): is close to the identity matrix, all pivots are close to 1 and the off-diagonal entries are small, so the elimination of in ball arithmetic loses only a few bits. The solution set is unchanged, since is nonsingular whenever is.
Input: , and a precision .
- Compute an approximate LU decomposition of the midpoint matrix of in floating-point arithmetic (
arb_mat_approx_lu) and from it an approximate inverse (arb_mat_approx_solvewith ). Fail if a pivot is zero. - Compute the ball matrices and .
- If , solve by interval Gaussian elimination.
- Otherwise, compute an upper bound for . If , return with each entry of column enlarged by (see Theorem 1); otherwise solve as in step 3.
Theorem 1. Let be an matrix with . Then is nonsingular, and for every vector , the solution of satisfies .
Proof. With , the Neumann series converges since , and has norm at most .
Applied to each matrix in the balls of and each column of in the balls of , with bounding the norm of all simultaneously, the theorem shows that the solution lies in the ball around of radius , which is contained in the returned ball. This variant costs two matrix products (forming and ) instead of an triangular solve with ball entries and is used when there are many right-hand sides, for example by arb_mat_inv, which solves . The cost of preconditioning is dominated by the three matrix multiplications ( from the LU decomposition, , ), which use the fast ball matrix multiplication of Ball matrix multiplication.
The radius of the result is about relative to the solution, where is the condition number, and the method succeeds as soon as the precision exceeds by a few bits, independently of . The interval elimination of step 3 is rarely the bottleneck because is almost diagonal.
Floating-point backends for the approximate functions#
The approximate functions that compute and the approximate solutions (arb_mat_approx_lu, arb_mat_approx_solve, arb_mat_approx_inv, arb_mat_approx_solve_lu_precomp, arb_mat_approx_solve_tril, arb_mat_approx_solve_triu, their complex versions, and acb_mat_approx_eig_qr for eigenvalues) work only on the midpoints and promise no accuracy beyond that of floating-point arithmetic at precision . They therefore convert the midpoints to a faster floating-point type when one can do the work, call the generic algorithm of gr_mat there, and convert the result back:
- The multi-double formats of
dfloat(Matrix arithmetic in multi-double formats),dNordNcwith the smallest such that : up to 53, 104, 155 and 206 bits. The padding of bits covers the slightly lower effective accuracy of the expansions: measured on random matrices, solutions are as accurate as witharf_tat bits (within one bit), while the eigenvalues lose about 1.5 bits withd2cand up to 3 bits on average (6 at worst) withd4c. Sincenfloatis faster for small matrices at three and four doubles,dfloatis used for LU decompositions and solving only from dimension when (always for and for eigenvalues).dfloatmust be supported on the target (dfloat_is_supported). - Otherwise,
nfloatornfloat_complexat rounded up to a multiple of 64 bits, if this is at most 4224 bits. - Otherwise, or if both fail,
arf_t(acf_tfor complex matrices) at bits, or 53 if is smaller (at a handful of bits the QR iteration gives meaningless results); the entries are not converted or scaled.
The same generic algorithms of gr_mat run in all three cases; the functions have no other implementation. dfloat and nfloat are used from dimension 4, and for triangular solving only with four or more right-hand sides (below that, the conversions cost as much as the solving).
Scaling. The doubles have exponents in (and the last component of an expansion lies bits below the first), the nfloat exponents are bounded by about , while the exponents of arf_t are unbounded. The matrix and the right-hand side are therefore scaled by powers of two, exactly, to bring their largest entries into , and the result is scaled back: for and , eigenvalues by , while eigenvectors and the relative deflation tolerance are unaffected. The factor of an LU decomposition is scaled, the unit triangular factor is not (it contains the ones of its diagonal, so its range is fixed). After scaling, dfloat is used only if the exponents of the nonzero entries span at most bits (452, 426, 399 and 373 for ), so that products of two entries keep all their components above the subnormal range; a matrix with a wider range, such as , goes to nfloat. Inputs with nonfinite midpoints or exponents beyond go to arf_t directly.
Fallbacks. A backend fails if a conversion or an operation overflows or underflows (which nfloat reports), if the dfloat result has a nonfinite entry, if an LU decomposition finds the matrix singular, or if the QR iteration does not converge; the next backend is then tried on the original data, and arf_t, which does not fail on exponents, has the last word: it decides that a matrix is singular, and the eigenvalue function then writes its approximations even if the iteration has not converged. The results are written only when the computation has succeeded, so the outputs may alias the inputs.
Times in milliseconds for matrices with random entries, one thread, for the former implementations on arf_t and with the backends (with the conversions; dfloat up to 200 bits, nfloat above):
| 53 | 100 | 150 | 200 | 256 | 1024 | 4096 | |
|---|---|---|---|---|---|---|---|
arb_mat_approx_inv, arf_t | 2.9 | 3.3 | 7.3 | 8.1 | 8.2 | 28 | 265 |
arb_mat_approx_inv, backend | 0.31 | 0.81 | 1.7 | 2.7 | 3.9 | 18 | 162 |
acb_mat_approx_inv, acf | 12 | 13 | 28 | 32 | 32 | 108 | 1055 |
acb_mat_approx_inv, backend | 0.68 | 2.3 | 4.7 | 8.5 | 12 | 58 | 497 |
acb_mat_approx_eig_qr, acf | 228 | 284 | 562 | 649 | 730 | 3350 | |
acb_mat_approx_eig_qr, backend | 4.0 | 23 | 59 | 116 | 329 | 2492 |
(acb_mat_approx_eig_qr with right eigenvectors.) Since these functions dominate the time of arb_mat_solve, arb_mat_inv and the eigenvalue enclosures at low precision, those become several times faster as well; the ball arithmetic of the certification is unchanged.
Certifying an approximate solution#
If an approximate solution and an approximate inverse are already known, for example from a previous call at lower precision or from a floating-point solver, they can be certified directly.
Theorem 2. Let , be matrices and , be matrices with . Then is nonsingular, and each column of and the corresponding columns of and of satisfy
arb_mat_solve_preapprox evaluates and in ball arithmetic and returns with these error bounds. The residual is small when is accurate, so the radius is of the order of the error of plus the rounding errors in the residual, and the result can be much tighter than the one obtained by solving from scratch at the same precision. The cost is three matrix products. This is the approach to use for iterative refinement: compute by a fast floating-point method, improve it if needed, and certify it at the end.
Determinants#
arb_mat_det uses explicit formulas for , the product of the diagonal for triangular matrices, and otherwise either interval elimination (for or ; for acb_mat_det) or preconditioning. The interval elimination version arb_mat_det_lu multiplies the pivots; if the elimination stops at step because all candidate pivots contain zero, the determinant of the remaining block is bounded by Hadamard's inequality,
where are the rows of , so that the result is still a valid (if wide) enclosure rather than a failure.
- Compute an approximate decomposition in floating-point arithmetic and approximate inverses (exactly unit lower triangular) and (exactly upper triangular).
- Compute the ball matrix , which is close to , and .
- Return , where is enclosed by the ball and the sign is that of the permutation .
- If the result contains zero, also compute
arb_mat_det_luand return the narrower of the two.
The enclosure of follows from Gershgorin's theorem: every eigenvalue of satisfies , so . Since and exactly, .
Symmetric positive definite matrices#
For a symmetric positive definite matrix, arb_mat_cho computes the Cholesky factor with in ball arithmetic and fails if a diagonal entry is not provably positive; success proves that every symmetric matrix in the balls is positive definite. arb_mat_ldl computes without square roots. These decompositions need no pivoting, and the radius growth is moderate since the entries of are bounded by . They are used by arb_mat_spd_solve and arb_mat_spd_inv (and the _precomp variants), which do not precondition.
Use in FLINT#
arb_mat_solveandacb_mat_solvechoose between*_solve_lu(Interval Gaussian elimination) and*_solve_precond(Algorithm 1) as described above;arb_mat_invandacb_mat_invcall them with ;*_solve_preapproximplements Theorem 2. See Solving linear systems with ball matrices.arb_mat_det,arb_mat_det_lu,arb_mat_det_precondand the complex versions (Determinants).- The approximate functions
arb_mat_approx_lu,arb_mat_approx_solve,arb_mat_approx_invandarb_mat_approx_mulwork with midpoints only and give no error bounds; all but the product use the floating-point backends of Floating-point backends for the approximate functions. - Generic code:
gr_mat_detover the ball contexts callsarb_mat_detandacb_mat_det, andgr_mat_mulcalls the ball matrix multiplication, butgr_mat_nonsingular_solveandgr_mat_invuse generic elimination without preconditioning (gr_mat.h). - Eigenvalue enclosures (Eigenvalue enclosures) use the same idea of certifying approximate results with norm bounds.
Referenced from#
acb_mat_approx_eig_qr- Eigenvalues and eigenvectors
- acb_mat.h (module)
- Eigenvalue enclosures (algorithm)
- Ball matrix multiplication (algorithm)
- Matrix arithmetic in multi-double formats (algorithm)
- The QR algorithm for eigenvalues (algorithm)
- arb_mat.h (module)
- Solving linear systems with ball matrices
- Performance of dfloat
- Numerical eigenvalues
- LU decompositions and linear systems
References#
- [Rum2010] S. M. Rump, "Verification methods: Rigorous results using floating-point arithmetic", Acta Numerica 19 (2010), 287-449.
- [HS1967] E. Hansen and R. Smith, "Interval Arithmetic in Matrix Computations, Part II", SIAM Journal of Numerical Analysis, 4(1):1-9 (1967). https://doi.org/10.1137/0704001
The FLINT team, “Verified linear algebra,” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/algorithms/ball-arithmetic/linear-systems.html (generated 2026-11-20).
@misc{flint-doc-algorithms-ball-arithmetic-linear-systems,
author = {{The FLINT team}},
title = {{Verified linear algebra}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/algorithms/ball-arithmetic/linear-systems.html},
note = {Generated 2026-11-20}
}