API - Norm Bounds and Matrix Classes

upper_bound_frobenius(A::BallMatrix) -> T

Rigorous upper bound on the Frobenius norm of every matrix in the ball A: the Frobenius norm of upper_abs(A), accumulated with upward rounding.

The Frobenius norm is the entrywise ℓ² norm of the matrix, √(Σ_ij |a_ij|²), and it is not an operator norm; it bounds the spectral norm from above, which is how upper_bound_L2_opnorm uses it. For a ball matrix in any arithmetic other than Float32 or Float64 the value is that of upper_bound_norm(A, 2), the same quantity.

triangular_inverse_inf_norm_bound(U)

An upper bound of ‖U⁻¹‖_∞, the largest row sum of the moduli of the entries of the inverse, for an upper triangular matrix U with exact entries, Inf when a diagonal entry is zero. For a ball matrix U, upper triangular with the balls below the diagonal equal to the point zero, the bound holds for every matrix of the ball, and it is Inf when a ball on the diagonal contains zero: the recursion below is then run with a lower bound of |u_ii| and upper bounds of |u_ij| over the balls. With y the solution of

|u_ii| y_i = 1 + Σ_{j>i} |u_ij| y_j,    i = m, m−1, …, 1,

the bound is max_i y_i: y = M⁻¹e for the matrix M with diagonal |u_ii| and off-diagonal entries −|u_ij|, and |U⁻¹| ≤ M⁻¹ entrywise. The recursion is evaluated with every operation rounded up and the moduli on the diagonal rounded down.

triangular_inverse_one_norm_bound(U)

An upper bound of ‖U⁻¹‖₁, the largest column sum of the moduli of the entries of the inverse: the bound of triangular_inverse_inf_norm_bound for the transpose, and Inf under the same conditions. U may be a matrix with exact entries or an upper triangular BallMatrix whose balls below the diagonal are the point zero, and in the second case the bound holds for every matrix of the ball.

svd_bound_L2_resolvent(A::BallMatrix, λ::Ball)

An upper bound of the spectral norm of the resolvent, ‖(M − zI)⁻¹‖₂, holding for every matrix M of the ball A and every z of the ball λ at once: the ball A − λI is formed first, so that its entries enclose M − zI for every such pair, and svd_bound_L2_opnorm_inverse is applied to it.

Inf is returned when the enclosure of the smallest singular value of A − λI reaches zero, which is what happens near the spectrum; it does not say that some M − zI is singular.

similarity_condition_number(X)

An upper bound of κ₂(S(X)) = ‖S(X)‖₂‖S(X)⁻¹‖₂ for the unit block triangular matrix S(X) = [I X; 0 I]: psi_squared evaluated at upper_bound_L2_opnorm of X, which is legitimate because ψ is increasing. X may be a matrix with exact entries or a BallMatrix, and in the second case the bound holds for every X of the ball.

_fast_gamma_bound(A::BallMatrix{T}, B::BallMatrix{T}, C::BallMatrix{T},
                  Dd_diag::Vector{T}, D_rad::Matrix{T}, Df::BallMatrix{T}) where {T}

Equation (9) of [8]:

‖D_d⁻¹(D_f − CA⁻¹B)‖₂ ≤ π(D_d⁻¹D_f) + π(D_d⁻¹C) π(A⁻¹B) =: γ,

with π(N) = √(‖N‖₁‖N‖_∞) (pi_norm) an upper bound of ‖N‖₂. So γ < 1 establishes the hypothesis (7) of Theorem 1.3 without forming the product CA⁻¹B, which brings the cost of the test from O((n−m)²m) to O((n−m)m²) operations.

The three factors are enclosed by _diagonal_scale_left and _solve_ball_system, so the inequality is established for every matrix of the ball G; the sum and the product are rounded up.

Returns

(γ, A_inv_B), the second being the enclosure of A⁻¹B that the caller reuses, or (Inf, nothing) when one of the three bounds is not finite.

_inverse_diagonal_norm(d, d_rad)

An upper bound of max_i 1/|x_i| over |x_i − d[i]| ≤ d_rad[i, i], the 2-norm of the inverse of the diagonal matrix; Inf where an entry may vanish. The lower bound of |x_i| is rounded down.

_diagonal_scale_left(d::Vector, d_rad::Matrix, M::BallMatrix)

An enclosure of Δ⁻¹ N, where Δ is the diagonal matrix whose i-th entry lies in the ball of centre d[i] and radius d_rad[i, i] and N is any matrix of the ball M. Row i is the product of the ball inv(Ball(d[i], d_rad[i, i])) with the balls of row i of M, so the rounding of the inverse and of the products is carried in the radii.

d_rad is passed as the radius matrix of the block whose diagonal d is, and only its diagonal is read. A row whose ball may contain zero gets radius Inf rather than raising: no bound of Δ⁻¹ exists there, and that is reported through the enclosure.

_solve_ball_system(A::BallMatrix, B::BallMatrix)

An enclosure of A⁻¹B, as a BallMatrix whose midpoint X̃ is the floating-point solution of mid(A) X = mid(B) and each of whose radii is ‖A⁻¹‖₂ ‖R‖₂ for R the residual B − A X̃ computed in ball arithmetic.

The solve itself is not trusted: for every M of the ball A and N of the ball B the exact solution X of M X = N satisfies X − X̃ = M⁻¹(N − M X̃), and N − M X̃ is enclosed by R, so ‖X − X̃‖₂ ≤ ‖M⁻¹‖₂ ‖R‖₂. The modulus of an entry of a matrix is at most its ℓ² operator norm, so that single number bounds every entry of X − X̃ and is used as the radius of each. The two factors are bounded uniformly over the balls by svd_bound_L2_opnorm_inverse and collatz_upper_bound_L2_opnorm, and their product is rounded up. The radius is Inf when either factor is, which is what happens when the ball A may contain a singular matrix.

_solve_ball_system_transpose(A::BallMatrix, C::BallMatrix)

An enclosure of C A⁻¹, obtained as _solve_ball_system does but from the other side: the midpoint is the floating-point solution X̃' of mid(A)' X = mid(C)', the residual R = C − X̃' A is computed in ball arithmetic, and each radius is ‖A⁻¹‖₂ ‖R‖₂, which bounds every entry of C M⁻¹ − X̃' for every M of the ball A and every C of its ball since C M⁻¹ − X̃' = (C − X̃' M) M⁻¹.

off_diagonal_abs(A::BallMatrix)

A point ball matrix whose off-diagonal entries are upper bounds of the moduli of the off-diagonal entries of every matrix of the ball A (upper_abs), and whose diagonal is zero.

It is the off-diagonal part of the comparison matrix with its sign removed: with diagonal_abs_lower_bound it gives the two arrays that is_M_matrix and is_H_matrix compare, and being entrywise above the whole ball it dominates the corresponding part of every matrix of the ball, which is what makes a single test cover the ball.

diagonal_abs_lower_bound(A::BallMatrix) -> Vector

Lower bounds of |a_ii|, one for each i, holding for every matrix of the ball A: the modulus of the midpoint rounded down, less the radius, rounded down again.

An entry is negative when the ball on the diagonal contains zero, and is returned as it stands rather than clamped at zero; the callers in this file use it only through μ − dlo[i], which stays an upper bound of μ − a_ii whatever the sign.