deep_causality_linear
Summary
Linear algebra for the DeepCausality project. The crate holds the workspace's matrix
representations and the algorithms over them: sparse (CSR), dense row-major, and bit-packed ๐ฝโ matrices, a dense
vector, eliminations, decompositions, direct and iterative solvers, and an exact integer path. It has zero external
runtime dependencies; its only dependencies are deep_causality_num, deep_causality_algebra, and
deep_causality_haft.
Two decisions shape the design. Storage is a local choice, because all three representations sit behind one read trait. And every operation is bounded on the weakest trait from the algebra tower that makes it correct, which admits the integers and ๐ฝโ alongside the floats.
The crate defines no scalar trait, marker, or newtype of its own. Gf2, Float106, and the primitives come from
deep_causality_num; the laws they satisfy come from deep_causality_algebra.
Three representations, one read seam
Choosing a representation is the central decision in linear algebra, so the crate holds all three, plus a vector.
| Type | Storage | Reach for it when |
|---|---|---|
CsrMatrix<T> |
compressed sparse row | boundary and coboundary operators, discrete Laplacians, adjacency |
DenseMatrix<T> |
dense row-major | covariance, metric tensors, density matrices, anything decomposed |
PackedGf2<W> |
one bit per entry, in W |
mod-2 elimination, homology read as a code |
DenseVector<T> |
contiguous buffer | chains, states, right-hand sides, coefficient vectors |
The vector carries the larger half of the workload: a census across the seven consumer crates counted 60 rank-1 constructions against 46 rank-2.
Three traits form the seam:
| Trait | What it gives | Implemented by |
|---|---|---|
MatrixView |
shape and entries by value | all three matrices, plus CausalTensor |
MatrixBuild |
zeros, identity, set |
all three matrices |
RowOps |
swap_rows, scale_row, axpy_rows, pivot_in_column |
dense and packed ๐ฝโ only |
get returns Self::Scalar by value, because a bit-packed matrix has one bit inside a word and no element to lend a
reference to. Reading a position outside a sparse matrix's stored pattern returns the scalar zero and is not an error;
only an index outside the shape fails.
CsrMatrix implements only the read side. Adding a multiple of one sparse row to another changes that row's non-zero
pattern, which in CSR means reallocating every row after it. Sparse elimination needs a fill-reducing ordering and a
symbolic factorisation, so a caller who needs elimination converts to a dense layout at the call site, where the cost is
visible.
use ;
// Sparse: only the stored entries cost anything.
let sparse = from_triplets.unwrap;
assert_eq!;
assert_eq!;
// A position outside the stored pattern is a zero.
assert_eq!;
// Dense: the layout the eliminations and decompositions work on.
let dense = csr_to_dense;
assert_eq!;
// Bit-packed ๐ฝโ: entries reduce mod 2 on the way in, so {-1, 0, 1} is accepted.
let packed = from_i64_mod2.unwrap;
assert_eq!;
PackedGf2 is generic over its word type. A caller picks the width that suits the target; the suite runs at a narrow
width so that a column count crossing a word boundary shows up in a matrix small enough to read. A test checks that the
same matrix packed at two widths reports the same rank and the same pivot columns.
Where this sits against deep_causality_tensor
The split is by arity. A two-index object is a matrix and lives here. ein_sum, broadcasting, the
Kronecker product, the axis reductions, and the tensor-train stack take an N-index object and stay in the tensor crate.
deep_causality_linear sits below deep_causality_tensor in the dependency graph and never depends on it.
CausalTensor's rank-2 decompositions delegate to the bodies here, so a density matrix in the quantum layer and a
stiffness matrix in the fluids layer run the same kernel.
Bounded by algebra
Each operation names the algebra rung it needs:
| Operation | Bound | Admits |
|---|---|---|
| transpose, dot product | CommutativeSemiring |
โ upward |
entrywise subtraction, Module<R> |
CommutativeRing |
โค upward |
determinant_exact, rank_exact |
EuclideanDomain |
โค only |
rref, rank, kernel and image |
Field |
๐ฝโ, โ, โ, โ |
rref_stable, determinant, solve |
NormedScalar |
โ, โ, Float106 |
| the decompositions, Cholesky | ConjugateScalar |
โ, โ, Dual (forward-mode AD) |
| the norms | NormedScalar |
โ, โ, Float106 |
The determinant is a polynomial in the entries and needs no division, so it is defined over any commutative ring. Gaussian elimination divides by its pivot and leaves โค on the first step. Both facts are in the bounds.
Four compile_fail doctests guard the bounds that a widening would leave compiling and passing every behavioural
test: f64 refused by EuclideanDomain on both integer entry points, and a matrix refused by CommutativeRing and by
IntegralDomain. [[1,0],[0,0]] times [[0,0],[0,1]] is zero with neither factor zero, so cancellation fails over
matrices, and Bareiss elimination rests on cancellation.
The container memberships run the other way. Every matrix reaches Ring and Module<R>; the vector reaches
AbelianGroup and Module<R> and no multiplicative rung, having no Mul that returns a vector. Module<R: Ring> is
the tower's name for a vector space, and stating it over a ring admits DenseVector<i64>, which topology's integer
chains need. src/traits/tower_pins.rs pins these memberships as ordinary items rather than tests, because a
membership test passes by compiling and reports nothing the build has not already settled.
Elimination, and everything read off it
Every entry point runs the same private elimination over the RowOps seam, naming no representation, no scalar, and no
word width. They come in pairs, because the pivot rule cannot be chosen by the representation alone:
| Suffix | Pivot | Admits |
|---|---|---|
| none | first non-zero at or below the row | any Field: ๐ฝโ, โ, โ, โ |
_stable |
largest modulus at or below the row | any NormedScalar: โ, โ, Float106 |
The exact rule needs no ordering and no epsilon, which admits ๐ฝโ and โ. Over the floats a pivot near zero amplifies
rounding, so a float caller wants the _stable entry point. Both search the column; neither assumes a non-zero
diagonal. A Cayley-Menger matrix has m[0][0] = 0 by construction, and an elimination that assumes the diagonal
returns zero for every simplex volume.
rref and rref_stable return a Reduced carrying the rank and the pivot columns, both from one pass.
rank, rank_stable, kernel_basis, image_basis, and determinant read off the same core.
use ;
let a = from_vec.unwrap;
assert_eq!;
assert_eq!;
let b = from_vec;
let x = solve.unwrap;
assert_eq!;
Solving
| Entry point | Method |
|---|---|
Lu::factor |
LU with partial pivoting, kept as a value so it can be applied often |
solve |
one factorisation, one application |
solve_lower / solve_upper |
forward and back substitution, no factorisation |
inverse |
one factorisation, n applications |
cholesky |
A = L Lแดด for a Hermitian positive-definite A |
solve_least_squares |
the normal equations through the Cholesky factor |
Lu is a value because factorising costs O(nยณ) and each application costs O(nยฒ). Both workloads in this workspace
that solve repeatedly, the Kalman filter in deep_causality_physics and the ridge fits in deep_causality_algorithms,
hold one matrix and many right-hand sides. The permutation travels inside the factorisation, since applying L and U
without it solves a different system.
The Cholesky factorisation tests positive-definiteness: the first diagonal entry whose radicand is non-positive shows
that the input does not qualify, and LinearError::NotPositiveDefinite carries that index. A non-singular matrix can
still fail there, so the variant is separate from Singular.
Decompositions
svd, svd_sorted, svd_truncated, singular_values, qr, eigen_hermitian, and cholesky are bounded on
ConjugateScalar. That bound spans real fields, dual numbers for forward-mode AD, and complex. Magnitudes and
thresholds live in the associated real type and only the rotations are injected back, so a Hermitian complex matrix
decomposes as readily as a real symmetric one. RealField cannot cover it, because Complex is unordered.
qr and eigen_hermitian take MatrixView rather than RowOps. They copy the entries into a flat buffer and never
mutate a row, so they accept read-only representations.
Thresholds scale by the input's Frobenius norm. An absolute epsilon burns the whole sweep budget on a large-magnitude matrix and fires immediately on a small one.
use ;
let a = from_vec.unwrap;
let l = cholesky.unwrap; // A = L Lแดด, lower triangular
assert_eq!;
assert_eq!;
let = qr.unwrap; // thin: Q is mรk, R is kรn, k = min(m, n)
assert_eq!;
let = eigen_hermitian.unwrap; // A = V diag(ฮป) Vแดด
assert_eq!;
assert_eq!;
Truncation keeps "at most rank k" and "everything above epsilon" as distinct requests.
Exact paths
Rank over โ, rank over โค, and rank over ๐ฝโ are three different questions. Each has its own entry point, so the choice of field is visible at the call site.
Over ๐ฝโ
rank_gf2, kernel_basis_gf2, and image_basis_gf2 run the generic elimination on the bit-packed
representation. They take no tolerance and apply none; every non-zero element of ๐ฝโ is its own inverse, so the
elimination divides by nothing that could be near zero.
use ;
// Rows 0 and 1 sum to row 2 over ๐ฝโ, so the rank is two and the kernel is one-dimensional.
let m = from_i64_mod2.unwrap;
assert_eq!;
assert_eq!;
Over โค
determinant_exact and rank_exact use fraction-free Bareiss elimination. No float appears at any point, including
intermediates. The determinant of an integer matrix is an integer, and Bareiss keeps every intermediate in the ring
while reaching the answer in cubic time, where Laplace expansion takes factorial time.
use ;
let m = from_vec.unwrap;
assert_eq!;
assert_eq!;
EuclideanDomain supplies the division; IntegralDomain, one rung below, makes those divisions exact, because an
integral domain has no zero divisors and therefore licenses cancellation.
Conjugate gradient, matrix-free
cg_solve, cg_solve_preconditioned, and cg_solve_preconditioned_from take a closure applying the operator rather
than a matrix, so a caller with a Laplacian it never assembles can use them, and the sparse-versus-dense question does
not arise. tolerance is relative to โbโ. CgFailure names three cases: a reached iteration limit, an operator that
is not positive definite, and a length mismatch. Each calls for a different response, so each gets a variant.
use cg_solve;
// A 1-D Dirichlet Laplacian, applied without assembling it.
let apply = ;
let x = cg_solve.unwrap;
assert!;
assert!;
LU on a sparse matrix fills in, and the factors are dense even when the matrix is not. The CG solvers cover the symmetric positive-definite case, which is the one the workspace solves.
Vectors and norms
vector_norm_l1, vector_norm_l2, vector_norm_sq, and vector_norm_inf are generic over a slice, and the
DenseVector methods of the same names delegate to them. deep_causality_multivector holds a Vec<T> of
coefficients and CausalMultiField holds a tensor's buffer; the slice form lets both take a norm without copying the
coefficient vector.
matrix_norm_l1, matrix_norm_inf, and matrix_norm_frobenius are generic over any MatrixView, so they apply to the
sparse and packed representations too.
use ;
let v = from_vec;
assert_eq!;
assert_eq!;
assert_eq!;
let outer = v.outer;
assert_eq!;
dot is bounded on CommutativeSemiring and is available over โ. hermitian_inner is separate and computes
ฮฃ conj(aแตข) ยท bแตข. Over โ the plain dot product induces no norm, and deep_causality_quantum works in Complex<R>
throughout.
Higher-kinded witnesses
Three witnesses lift the containers into the deep_causality_haft surface, so fmap, fold, and the rest read the
same here as on a tensor, a manifold, or a propagating effect.
| Witness | Container | Traits |
|---|---|---|
CsrMatrixWitness |
CsrMatrix<T> |
Functor, Foldable, Pure, Applicative, CoMonad |
DenseMatrixWitness |
DenseMatrix<T> |
Functor, Foldable, Pure, Applicative, CoMonad |
DenseVectorWitness |
DenseVector<T> |
the same, plus Monad |
DenseVector implements Monad; the two matrices stop at Applicative and CoMonad. A shaped container cannot satisfy
the monad laws: pure has to choose a shape for a single value, and right identity bind(m, pure) == m then asks
bind to reassemble an m ร n matrix from m ยท n one-by-ones. A vector's only shape is its length, so it satisfies
the laws.
CsrMatrixWitness::fmap maps the stored entries and leaves the structural zeros alone, which keeps the result
sparse. A caller who wants a function applied to the whole logical matrix densifies first, explicitly.
use ;
use ;
let v = from_vec;
assert_eq!;
// The fold visits the stored entries; a structural zero contributes nothing.
let m = from_triplets.unwrap;
assert_eq!;
PackedGf2 has no witness. It is generic in its word and fixed to Gf2 in its element, so there is no PackedGf2<T>
for Type<T> to name; the route out is packed_to_dense_gf2.
Conversions
Conversions are explicit, because a conversion changes the cost model of everything done afterwards.
| From | To | |
|---|---|---|
| sparse | dense | total; costs memory |
| dense | sparse | total |
| dense or sparse | packed ๐ฝโ | fallible: the target holds only {0, 1} |
| packed ๐ฝโ | dense Gf2 |
total |
Only the packing direction fails, and for one reason: an entry outside {0, 1}. The error names the position, so a
caller does not re-scan to find it. csr_to_packed_gf2_mod2 reduces mod 2 instead, for topology's boundary operators,
whose entries are {-1, 0, 1}.
Errors
One error type, LinearError, covers all representations and all algorithms. It is a newtype over LinearErrorEnum,
so a new failure mode is a new variant on the inner enum and a downstream match with a wildcard arm keeps compiling.
Variants carry the numbers needed to say what went wrong: IndexOutOfBounds carries the position and the shape it was
checked against, Singular carries the column elimination stopped at, WrongTriangle carries the first offending
position. CgFailure is separate, being generic over the real type it reports a residual in.
Measurements
Four figures from the design work, each behind a decision in the source:
| Measurement | Result |
|---|---|
Packed u64 elimination against a byte-per-entry Gf2 scalar |
1.7ร faster at n=128, 3.2ร at n=2048, on one eighth the memory |
The RowOps seam against a hand-written non-generic loop |
0.92โ0.95ร the time, because from_col skips columns already zeroed |
csr_to_dense by scatter against reading every position back |
0.24 ms against 23.6 ms, on 800ร800 holding 64000 entries |
to_row_major as a memcpy against the per-entry default |
the default ran 4.7% slower on a 48ร48 QR |
Measured on an M3 Max, 16 cores, 128 GB, macOS 26.
Verification
580 tests cover the crate, laid out to mirror src, plus five doctests of which four are compile_fail guards.
SCENARIOS.md maps every scenario in the four capabilities to the test that serves it, and marks the ones covered by a
compile-time pin instead.
The ๐ฝโ layer is machine-checked in Lean 4 against Mathlib. Four theorems, zero sorry, each with a Rust witness test
under tests/formalization_lean/. The load-bearing one is rank-nullity: ChainComplex::betti_number_over in
deep_causality_homology substitutes n_k โ rank โ_k for dim ker โ_k, and nothing in either crate's source states
that identity. The witnesses compute the two sides by different routines, the rank by elimination and the nullity by
counting kernel-basis columns, so the test is two independent computations agreeing. See
LEAN_LINEAR.md.
Dependency
Add the crate to your Cargo.toml:
[]
= "0.1"
Build configurations
| Configuration | Cargo features | Supported |
|---|---|---|
std, hosted |
default | โ |
no-std with a heap |
default-features = false, features = ["no-std"] |
โ |
no-std on core alone, no heap |
โ | โ |
Without std the crate needs a heap: the program must define a #[global_allocator].
CI builds every supported bare-metal configuration for thumbv7em-none-eabihf.
README_NO_STD.md describes the build configuration of every crate in the workspace.
Features and no-std
| Feature | Effect |
|---|---|
std |
default; enables std on the three internal dependencies |
alloc |
the collections the containers are built from |
no-std |
alloc plus no-std on the three internal dependencies |
The crate is #![no_std] when std is off. It always needs an allocator, since every container owns a Vec.
579 of the 580 tests run in that configuration; the one left out pins LinearError as a std::error::Error, which
exists only under std.
Under Bazel:
Safety
No unsafe: the crate opts into the workspace-wide unsafe_code = "forbid" lint policy. No macros in library code.
Contribution
Contributions are welcomed especially related to documentation, example code, and fixes. If unsure where to start, just open an issue and ask.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in deep_causality by you, shall be licensed under the MIT licence, without any additional terms or conditions.
Licence
This project is licensed under the MIT license.
Security
For details about security, please read the security policy.