Module linear 

Dense linear algebra, in honest enclosures: a pivot counts as zero exactly when it could be zero. One implementation per algorithm, for every solver of the kernel:

• solve_linear_system: a small fixed-size system, by Gaussian elimination with partial pivoting on sharpened magnitudes.
• solve_pivoted: a square system with several right-hand sides, by Gaussian elimination with partial pivoting on midpoints.
• solve_banded: a banded system that needs no pivoting.
• solve_symmetric2: a symmetric 2x2 system — a Newton step on a surface’s two parameters — by Cramer’s rule.
• cholesky and solve_cholesky: a symmetric positive semi-definite one, rows that say nothing new left out.
• shortest_solution: the shortest step meeting a few linear conditions in space — least squares where they are too many.
• eliminate, null_space, rank, inverse: Gauss-Jordan elimination with complete pivoting over a Jacobian — which rows are independent, what they leave free, and inverses.

solve_linear_system and solve_pivoted are the same algorithm in two shapes, but not the same arithmetic: they choose their pivots by different comparisons, and the latter back-substitutes by multiplying with the pivot’s reciprocal where the former divides. Their callers build curves and surfaces, which are sensitive to the last bit, so the two are kept as they are rather than merged into one that would round differently for one of them.

Structs

Elimination

The outcome of Gauss-Jordan elimination (see eliminate).

Functions

augmented

rows each with the row of the identity beside it, [row | I]: an elimination of them reduces the identity alongside, which then says what combination of the rows each reduced row is.

cholesky

The Cholesky factor L of the symmetric a, a = L Lᵀ — leaving out every row whose pivot could be zero or less, or is too small to divide by: one that, in the light of the rows before it, says nothing new (or nothing positive). Which rows were left out is true in the second.

eliminate

Gauss-Jordan elimination of rows (each over n variables) with complete pivoting: each pivot the entry of largest magnitude among the rows and the columns not used yet — a free choice among those that cannot be zero; elimination stops when every candidate could be zero. Which constraints are independent and which variables they determine is decided from the rows’ own enclosures; where it matters for correctness, crate::solvers::system’s enclosure verifies what it is used for.

inverse

An enclosure of the inverse of the square matrix a, by Gauss-Jordan elimination: each entry encloses that of the inverse of every matrix a encloses. None if a could be singular.

null_space

A basis of the null space of rows (each over n variables): the directions in which every row stays put, to first order. One vector per variable no pivot determines, which is one there and zero at every other such variable.

rank

How many of rows (each over n variables) are independent: those an elimination finds a pivot that cannot be zero for.

shortest_solution

The shortest d with n_i . d = r_i for every (n_i, r_i) — for more than three conditions, of which three can be met at most, the d that misses them least in the least-squares sense.

solve_banded

Solves a x = rhs for the banded m x m matrix a and C right-hand sides, by Gaussian elimination without pivoting: row k is nonzero only in the columns first[k] ..= last[k], and the bands never move left down the rows. Safe without pivoting only where the matrix says so — a B-spline collocation matrix is totally positive (Piegl & Tiller §9.2.1), the reason the curve interpolation that builds it does not pivot either.

solve_cholesky

The solution of L Lᵀ x = b, zero at the rows left_out.

solve_linear_system

Solve the dense N x N system a * x = b by Gaussian elimination with partial pivoting, returning x.

solve_pivoted

Solves a x = rhs for the n x n matrix a and C right-hand sides by Gaussian elimination, pivoting on the entry of largest magnitude in each column. Which row to pivot on is a free choice — every pivot that cannot be zero gives the same enclosed solution — and the largest is the well-conditioned one. Fails if no entry of a column definitely differs from zero.

solve_symmetric2

The solution (x, y) of the symmetric 2x2 system [[a11, a12], [a12, a22]] (x, y) = (b1, b2), by Cramer’s rule: an error where the determinant could be zero.