FLINT3.7.0-dev
Algorithm

Verified linear algebra

Cost
O(n3)O(n^3) 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 O(nω)O(n^\omega) with fast ball matrix multiplication.

Let AA be an n×nn \times n matrix and BB an n×mn \times m matrix with ball entries. Solving AX=BAX = B rigorously means computing a ball matrix XX that contains A~−1B~\tilde A^{-1} \tilde B for every pair of matrices A~\tilde A, B~\tilde B with entries in the balls of AA and BB, or reporting failure if this cannot be done (in particular if the balls of AA 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 LULU factors of every matrix PA~P\tilde A in the balls of PAPA (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 ajk−(aji/aii)aika_{jk} - (a_{ji}/a_{ii}) a_{ik} 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 nn even for well-conditioned matrices, so that O(n)O(n) bits or more are lost [HS1967]. If the precision pp is large compared to nn, a loss of O(n)O(n) bits is harmless, and interval elimination is the fastest method; this is why arb_mat_solve uses it when n≤4n \le 4 or p>10np > 10n. The recursive LU decomposition (arb_mat_lu_recursive, for n≥8n \ge 8) 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 R≈A−1R \approx A^{-1} (a matrix with exact floating-point entries): RARA is close to the identity matrix, all pivots are close to 1 and the off-diagonal entries are small, so the elimination of RAX=RBRAX = RB in ball arithmetic loses only a few bits. The solution set is unchanged, since RR is nonsingular whenever RARA is.

Algorithm 1: Preconditioned solving

Input: AA, BB and a precision pp.

  1. Compute an approximate LU decomposition of the midpoint matrix of AA in floating-point arithmetic (arb_mat_approx_lu) and from it an approximate inverse RR (arb_mat_approx_solve with B=IB = I). Fail if a pivot is zero.
  2. Compute the ball matrices RARA and RBRB.
  3. If m<0.1n+1m < 0.1 n + 1, solve (RA)X=RB(RA) X = RB by interval Gaussian elimination.
  4. Otherwise, compute an upper bound δ\delta for ∥I−RA∥∞\|I - RA\|_\infty. If δ<1\delta < 1, return X=RBX = RB with each entry of column jj enlarged by δ1−δmax⁡i∣(RB)ij∣\frac{\delta}{1 - \delta} \max_i |(RB)_{ij}| (see Theorem 1); otherwise solve as in step 3.

Theorem 1. Let MM be an n×nn \times n matrix with ∥I−M∥∞≤δ<1\|I - M\|_\infty \le \delta < 1. Then MM is nonsingular, and for every vector yy, the solution xx of Mx=yM x = y satisfies ∥x−y∥∞≤δ1−δ∥y∥∞\|x - y\|_\infty \le \frac{\delta}{1 - \delta} \|y\|_\infty.

Proof. With E=I−ME = I - M, the Neumann series M−1=∑k≥0EkM^{-1} = \sum_{k \ge 0} E^k converges since ∥E∥∞<1\|E\|_\infty < 1, and x−y=(M−1−I)y=∑k≥1Ekyx - y = (M^{-1} - I) y = \sum_{k \ge 1} E^k y has norm at most ∑k≥1δk∥y∥∞\sum_{k \ge 1} \delta^k \|y\|_\infty.

Applied to each matrix M~=RA~\tilde M = R \tilde A in the balls of RARA and each column y~\tilde y of RB~R \tilde B in the balls of RBRB, with δ\delta bounding the norm of all I−M~I - \tilde M simultaneously, the theorem shows that the solution lies in the ball around y~\tilde y of radius δ1−δ∥y~∥∞\frac{\delta}{1-\delta} \|\tilde y\|_\infty, which is contained in the returned ball. This variant costs two matrix products (forming RARA and RBRB) instead of an O(n2m)O(n^2 m) triangular solve with ball entries and is used when there are many right-hand sides, for example by arb_mat_inv, which solves AX=IAX = I. The cost of preconditioning is dominated by the three matrix multiplications (RR from the LU decomposition, RARA, RBRB), which use the fast ball matrix multiplication of Ball matrix multiplication.

The radius of the result is about κ(A)⋅2−p\kappa(A) \cdot 2^{-p} relative to the solution, where κ(A)=∥A∥∥A−1∥\kappa(A) = \|A\| \|A^{-1}\| is the condition number, and the method succeeds as soon as the precision exceeds log⁡2κ(A)\log_2 \kappa(A) by a few bits, independently of nn. The interval elimination of step 3 is rarely the bottleneck because RARA is almost diagonal.

Floating-point backends for the approximate functions#

The approximate functions that compute RR 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 pp. 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:

  1. The multi-double formats of dfloat (Matrix arithmetic in multi-double formats), dN or dNc with the smallest N≤4N \le 4 such that p+2(N−1)≤53Np + 2(N - 1) \le 53N: up to 53, 104, 155 and 206 bits. The padding of 2(N−1)2(N-1) bits covers the slightly lower effective accuracy of the expansions: measured on random matrices, solutions are as accurate as with arf_t at 53N53N bits (within one bit), while the eigenvalues lose about 1.5 bits with d2c and up to 3 bits on average (6 at worst) with d4c. Since nfloat is faster for small matrices at three and four doubles, dfloat is used for LU decompositions and solving only from dimension 8N8N when N≥2N \ge 2 (always for N=1N = 1 and for eigenvalues). dfloat must be supported on the target (dfloat_is_supported).
  2. Otherwise, nfloat or nfloat_complex at pp rounded up to a multiple of 64 bits, if this is at most 4224 bits.
  3. Otherwise, or if both fail, arf_t (acf_t for complex matrices) at pp bits, or 53 if pp 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 [−1022,1023][-1022, 1023] (and the last component of an expansion lies 53(N−1)53(N-1) bits below the first), the nfloat exponents are bounded by about 2612^{61}, 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 [1/2,1)[1/2, 1), and the result is scaled back: X=2sA−sBX′X = 2^{s_A - s_B} X' for A′=2sAAA' = 2^{s_A} A and B′=2sBBB' = 2^{s_B} B, eigenvalues by 2−sA2^{-s_A}, while eigenvectors and the relative deflation tolerance are unaffected. The UU factor of an LU decomposition is scaled, the unit triangular LL 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 (1022−53N)/2−32(1022 - 53N)/2 - 32 bits (452, 426, 399 and 373 for N=1,…,4N = 1, \ldots, 4), so that products of two entries keep all their components above the subnormal range; a matrix with a wider range, such as diag⁡(1,2−2000)\operatorname{diag}(1, 2^{-2000}), goes to nfloat. Inputs with nonfinite midpoints or exponents beyond ±261\pm 2^{61} 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 64×6464 \times 64 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):

pp5310015020025610244096
arb_mat_approx_inv, arf_t2.93.37.38.18.228265
arb_mat_approx_inv, backend0.310.811.72.73.918162
acb_mat_approx_inv, acf12132832321081055
acb_mat_approx_inv, backend0.682.34.78.51258497
acb_mat_approx_eig_qr, acf2282845626497303350
acb_mat_approx_eig_qr, backend4.023591163292492

(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 TT and an approximate inverse RR 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 AA, RR be n×nn \times n matrices and TT, BB be n×mn \times m matrices with ∥I−RA∥∞≤δ<1\|I - RA\|_\infty \le \delta < 1. Then AA is nonsingular, and each column xx of A−1BA^{-1} B and the corresponding columns tt of TT and cc of C=R(AT−B)C = R(AT - B) satisfy

∥x−t∥∞≤∥c∥∞1−δ.\|x - t\|_\infty \le \frac{\|c\|_\infty}{1 - \delta}.

Proof. RARA is nonsingular by Theorem 1, so AA is. Since RA(t−x)=R(At−b)=cRA(t - x) = R(At - b) = c and ∥(RA)−1∥∞≤∑kδk=1/(1−δ)\|(RA)^{-1}\|_\infty \le \sum_k \delta^k = 1/(1 - \delta), the bound follows [Rum2010, Theorem 10.2].

arb_mat_solve_preapprox evaluates δ\delta and CC in ball arithmetic and returns TT with these error bounds. The residual AT−BAT - B is small when TT is accurate, so the radius is of the order of the error of TT 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 TT by a fast floating-point method, improve it if needed, and certify it at the end.

Determinants#

arb_mat_det uses explicit formulas for n≤3n \le 3, the product of the diagonal for triangular matrices, and otherwise either interval elimination (for n≤10n \le 10 or p>10np > 10n; n≤14n \le 14 for acb_mat_det) or preconditioning. The interval elimination version arb_mat_det_lu multiplies the pivots; if the elimination stops at step rr because all candidate pivots contain zero, the determinant of the remaining (n−r)×(n−r)(n - r) \times (n - r) block SS is bounded by Hadamard's inequality,

∣det⁡S∣≤∏i∥si∥2,|\det S| \le \prod_i \|s_i\|_2,

where sis_i are the rows of SS, so that the result is still a valid (if wide) enclosure rather than a failure.

Algorithm 2: Preconditioned determinant
  1. Compute an approximate decomposition PA≈LUPA \approx LU in floating-point arithmetic and approximate inverses L′≈L−1L' \approx L^{-1} (exactly unit lower triangular) and U′≈U−1U' \approx U^{-1} (exactly upper triangular).
  2. Compute the ball matrix M=L′PAU′M = L' P A U', which is close to II, and ε≥max⁡i∑j∣Mij−δij∣\varepsilon \ge \max_i \sum_j |M_{ij} - \delta_{ij}|.
  3. Return ±det⁡(M)/∏iUii′\pm \det(M) / \prod_i U'_{ii}, where det⁡(M)\det(M) is enclosed by the ball 1±(enε−1)1 \pm (e^{n \varepsilon} - 1) and the sign is that of the permutation PP.
  4. If the result contains zero, also compute arb_mat_det_lu and return the narrower of the two.

The enclosure of det⁡M\det M follows from Gershgorin's theorem: every eigenvalue λ\lambda of MM satisfies ∣λ−1∣≤ε|\lambda - 1| \le \varepsilon, so ∣det⁡M−1∣=∣∏iλi−1∣≤(1+ε)n−1≤enε−1|\det M - 1| = |\prod_i \lambda_i - 1| \le (1 + \varepsilon)^n - 1 \le e^{n\varepsilon} - 1. Since det⁡L′=1\det L' = 1 and det⁡U′=∏iUii′\det U' = \prod_i U'_{ii} exactly, det⁡A=±det⁡M/det⁡U′\det A = \pm \det M / \det U'.

Symmetric positive definite matrices#

For a symmetric positive definite matrix, arb_mat_cho computes the Cholesky factor LL with A=LLTA = LL^T in ball arithmetic and fails if a diagonal entry aii−∑klik2a_{ii} - \sum_k l_{ik}^2 is not provably positive; success proves that every symmetric matrix in the balls is positive definite. arb_mat_ldl computes A=LDLTA = LDL^T without square roots. These decompositions need no pivoting, and the radius growth is moderate since the entries of LL are bounded by aii\sqrt{a_{ii}}. They are used by arb_mat_spd_solve and arb_mat_spd_inv (and the _precomp variants), which do not precondition.

Use in FLINT#

Referenced from#

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
Cite this page

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).