Expand description
Linear algebra for the DeepCausality crates.
This crate owns the workspace’s matrix representations and the algorithms over them. The split
against deep_causality_tensor is by arity, not density: a two-index object is a matrix
and lives here; ein_sum, broadcast, kronecker, the axis reductions and the tensor-train
stack take an N-index object and stay there.
§Three representations, side by side
Choosing a representation is the central decision in linear algebra, and this crate holds all three so that the choice is local rather than architectural:
| representation | for |
|---|---|
| compressed sparse row | boundary and coboundary operators, discrete Laplacians |
| dense row-major | covariance, metric tensors, density matrices |
| bit-packed 𝔽₂ | mod-2 elimination, homology read as a code |
plus a dense vector, which the construction census found to be the larger need: 60 rank-1 constructions against 46 rank-2 across the seven consumer crates.
§Banded on the tower, not on f64
Every operation is bounded on the weakest trait from deep_causality_algebra that makes it
correct, so the crate is generic over the integers as well as the floats. The determinant is a
polynomial in the entries and needs no division, so it is defined over any commutative ring —
bounding it on Field is what would have excluded ℤ. Gaussian elimination divides by its pivot
and so leaves ℤ on the first step, and is bounded accordingly.
The crate defines no scalar trait, marker or newtype of its own.
§Position in the tier graph
This crate sits below deep_causality_tensor and must not depend on it under any feature.
CausalTensor’s decompositions delegate into here, and a crate can only call into what it
depends on. Given that edge, the orphan rule leaves deep_causality_tensor as the only place the
access-trait impl for CausalTensor can be written.
Structs§
- CsrMatrix
- A matrix in compressed sparse row form.
- CsrMatrix
Witness - The higher-kinded witness for
CsrMatrix. - Dense
Matrix - A dense matrix stored row-major.
- Dense
Matrix Witness - The higher-kinded witness for
DenseMatrix. - Dense
Vector - A dense vector, carrying its length.
- Dense
Vector Witness - The higher-kinded witness for
DenseVector. - Linear
Error - Every way an operation in this crate can fail.
- Lu
- An LU factorisation with partial pivoting, kept so it can be applied more than once.
- Packed
Gf2 - A matrix over 𝔽₂ storing one bit per entry, packed into words of type
W. - Packed
Gf2Vector - A vector over 𝔽₂, one bit per entry, packed into words of type
W. - Reduced
- What a row reduction learned, beyond the reduced matrix itself.
- ZipDense
Vector Witness - The elementwise higher-kinded view of
DenseVector.
Enums§
- CgFailure
- Why a conjugate-gradient solve stopped without converging.
- Linear
Error Enum - The classification behind
LinearError. - Truncation
- How a truncated decomposition decides what to keep.
Traits§
- Matrix
Build - Construction and mutation of a matrix, position by position.
- Matrix
View - Read access to a matrix: its shape, and its entries by value.
- RowOps
- The three row operations every elimination is built from.
Functions§
- cg_
solve - Solves
Ax = bby conjugate gradient, withapplysupplyingA. - cg_
solve_ preconditioned - Solves
Ax = bby Jacobi-preconditioned conjugate gradient. - cg_
solve_ preconditioned_ from - As
cg_solve_preconditioned, starting from a supplied initial guess. - cholesky
- The Cholesky factor
Lof a Hermitian positive-definite matrix, so thatA = L Lᴴ. - csr_
i8_ to_ dense_ i64 - Widens an
i8sparse matrix to a densei64one, row-major. - csr_
to_ dense - Densifies a sparse matrix, materialising its structural zeros.
- csr_
to_ packed_ gf2_ mod2 - Packs an integer matrix by reducing every entry modulo 2.
- csr_
to_ packed_ gf2_ strict - Packs an integer matrix, rejecting any entry outside
{0, 1}. - dense_
gf2_ to_ packed - Packs a dense matrix of 𝔽₂ entries.
- dense_
to_ csr - Sparsifies a dense matrix, storing only its non-zeros.
- determinant
- The determinant, pivoting on magnitude.
- determinant_
3x3 - The determinant of a
3×3, by cofactor expansion along the first row. - determinant_
4x4 - The determinant of a
4×4, by the six2×2minors of the first two rows. - determinant_
exact - The determinant of an integer matrix, by fraction-free (Bareiss) elimination.
- dot
- The inner product
Σ aᵢ·bᵢof two equal-length slices. - dot_n
- The inner product of two arrays of the same compile-time length.
- double_
dot_ 3x3 - The Frobenius inner product
A : B = Σᵢ Σⱼ aᵢⱼ·bᵢⱼ, for two3×3matrices. - eigen_
hermitian - The eigendecomposition of a Hermitian matrix, as
(eigenvalues, eigenvectors). - eigen_
symmetric_ 3x3 - The three eigenvalues of a real symmetric
3×3, sorted descending. - image_
basis - A basis of the image, as the columns of the returned matrix.
- image_
basis_ gf2 - A basis of the image over 𝔽₂.
- inverse
- The inverse.
- inverse_
3x3 - The inverse of a
3×3, as the adjugate over the determinant. - inverse_
4x4 - The inverse of a
4×4, as the adjugate over the determinant. - kernel_
basis - A basis of the kernel, as the columns of the returned matrix.
- kernel_
basis_ gf2 - A basis of the kernel over 𝔽₂.
- mat3_
vec - The matrix-vector product
M·vfor a3×3and a 3-vector. - matrix_
norm_ frobenius - The Frobenius norm:
sqrt(Σ |aᵢⱼ|²). - matrix_
norm_ inf - The ∞-norm: the largest row sum of moduli.
- matrix_
norm_ l1 - The 1-norm: the largest column sum of moduli.
- packed_
to_ dense_ gf2 - Unpacks into a dense matrix of 𝔽₂ entries.
- qr
- The QR decomposition, as
(Q, R). - rank
- The rank, by exact elimination.
- rank_
exact - The rank of an integer matrix, exactly.
- rank_
gf2 - The rank over 𝔽₂, exactly.
- rank_
stable - The rank, by elimination pivoting on magnitude.
- rref
- Reduces
mto reduced row echelon form in place, pivoting on the first non-zero. - rref_
stable - Reduces
mto reduced row echelon form in place, pivoting on the largest modulus. - singular_
values - The singular values alone, descending.
- solve
- Solves
Ax = bfor a dense square system, by LU with partial pivoting. - solve_
least_ squares - The least-squares solution of
A x ≈ bby the normal equations, factored with Cholesky. - solve_
lower - Solves a lower-triangular system by forward substitution.
- solve_
upper - Solves an upper-triangular system by backward substitution.
- svd
- The singular value decomposition, as
(U, S, Vᵀ). - svd_
sorted - The full decomposition, singular values real and sorted descending.
- svd_
truncated - The singular value decomposition truncated by a rank or a tolerance.
- trace_
of_ square_ 3x3 - The trace of the square,
tr(A²) = Σᵢ Σⱼ aᵢⱼ·aⱼᵢ, for a3×3. - vector_
norm_ inf - The ∞-norm of a vector,
max |aᵢ|. - vector_
norm_ l1 - The 1-norm of a vector,
Σ |aᵢ|. - vector_
norm_ l2 - The 2-norm of a vector,
sqrt(Σ |aᵢ|²), computed in the scaled form. - vector_
norm_ sq - The squared 2-norm of a vector,
Σ |aᵢ|².
Type Aliases§
- Eigen
Pair - The eigenvalues and eigenvectors of a Hermitian matrix.
- QrFactors
- The two factors of a QR decomposition.
- SvdFactors
- The three factors of a singular value decomposition:
U,SandVᵀ. - SvdReal
- The full singular value decomposition with real singular values, sorted descending.