[//]: # (---)
[//]: # (SPDX-License-Identifier: MIT)
[//]: # (---)
# deep_causality_linear
[![Crates.io][crates-badge]][crates-url]
[![Docs.rs][docs-badge]][docs-url]
[![MIT licensed][mit-badge]][mit-url]
[crates-badge]: https://img.shields.io/badge/Crates.io-Latest-blue
[crates-url]: https://crates.io/crates/deep_causality_linear
[docs-badge]: https://img.shields.io/badge/Docs.rs-Latest-blue
[docs-url]: https://docs.rs/deep_causality_linear/latest/deep_causality_linear/
[mit-badge]: https://img.shields.io/badge/License-MIT-blue.svg
[mit-url]: https://github.com/deepcausality-rs/deep_causality/blob/main/LICENSE
## Summary
Linear algebra for the [DeepCausality project](http://www.deepcausality.com). 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.
| `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:
| `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.
```rust
use deep_causality_linear::{CsrMatrix, MatrixView, PackedGf2, csr_to_dense};
// Sparse: only the stored entries cost anything.
let sparse = CsrMatrix::from_triplets(3, 3, &[(0, 0, 2.0), (1, 1, 3.0), (2, 0, 1.0)]).unwrap();
assert_eq!(sparse.shape(), (3, 3));
assert_eq!(sparse.values().len(), 3);
// A position outside the stored pattern is a zero.
assert_eq!(sparse.get(0, 2).unwrap(), 0.0);
// Dense: the layout the eliminations and decompositions work on.
let dense = csr_to_dense(&sparse);
assert_eq!(dense.shape(), (3, 3));
// Bit-packed ๐ฝโ: entries reduce mod 2 on the way in, so {-1, 0, 1} is accepted.
let packed = PackedGf2::<u64>::from_i64_mod2(&[1, -1, 0, 0, 1, 1], 2, 3).unwrap();
assert_eq!(packed.shape(), (2, 3));
```
`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:
| 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:
| 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.
```rust
use deep_causality_linear::{DenseMatrix, DenseVector, determinant, rank_stable, solve};
let a = DenseMatrix::from_vec(vec![4.0, 1.0, 1.0, 3.0], 2, 2).unwrap();
assert_eq!(determinant(&a).unwrap(), 11.0);
assert_eq!(rank_stable(&a).unwrap(), 2);
let b = DenseVector::from_vec(vec![11.0, 0.0]);
let x = solve(&a, &b).unwrap();
assert_eq!(x.as_slice(), &[3.0, -1.0]);
```
## Solving
| `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.
```rust
use deep_causality_linear::{DenseMatrix, cholesky, eigen_hermitian, qr, MatrixView};
let a = DenseMatrix::from_vec(vec![4.0, 1.0, 1.0, 3.0], 2, 2).unwrap();
let l = cholesky(&a).unwrap(); // A = L Lแดด, lower triangular
assert_eq!(l.as_slice()[0], 2.0);
assert_eq!(l.as_slice()[1], 0.0);
let (q, r) = qr(&a).unwrap(); // thin: Q is mรk, R is kรn, k = min(m, n)
assert_eq!(q.shape(), (2, 2));
let (values, vectors) = eigen_hermitian(&a).unwrap(); // A = V diag(ฮป) Vแดด
assert_eq!(values.len(), 2);
assert_eq!(vectors.shape(), (2, 2));
```
`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.
```rust
use deep_causality_linear::{PackedGf2, kernel_basis_gf2, rank_gf2};
// Rows 0 and 1 sum to row 2 over ๐ฝโ, so the rank is two and the kernel is one-dimensional.
let m = PackedGf2::<u64>::from_i64_mod2(&[1, 1, 0, 0, 1, 1, 1, 0, 1], 3, 3).unwrap();
assert_eq!(rank_gf2(&m).unwrap(), 2);
assert_eq!(kernel_basis_gf2(&m).unwrap().shape(), (3, 1));
```
### 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.
```rust
use deep_causality_linear::{DenseMatrix, determinant_exact, rank_exact};
let m = DenseMatrix::from_vec(vec![2i64, 3, 1, 4], 2, 2).unwrap();
assert_eq!(determinant_exact(&m).unwrap(), 5);
assert_eq!(rank_exact(&m).unwrap(), 2);
```
`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.
```rust
use deep_causality_linear::cg_solve;
// A 1-D Dirichlet Laplacian, applied without assembling it.
.map(|i| {
let left = if i == 0 { 0.0 } else { x[i - 1] };
let right = if i + 1 == x.len() { 0.0 } else { x[i + 1] };
2.0 * x[i] - left - right
})
.collect()
};
let x = cg_solve(apply, &[1.0, 1.0, 1.0], 1e-12, 100).unwrap();
assert!((x[0] - 1.5).abs() < 1e-10);
assert!((x[1] - 2.0).abs() < 1e-10);
```
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.
```rust
use deep_causality_linear::{DenseVector, MatrixView};
let v = DenseVector::from_vec(vec![3.0, 4.0]);
assert_eq!(v.norm_l2(), 5.0);
assert_eq!(v.norm_l1(), 7.0);
assert_eq!(v.dot(&v).unwrap(), 25.0);
let outer = v.outer(&DenseVector::from_vec(vec![1.0, 0.0]));
assert_eq!(outer.shape(), (2, 2));
```
`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.
| `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.
```rust
use deep_causality_haft::{Foldable, Functor};
use deep_causality_linear::{CsrMatrix, CsrMatrixWitness, DenseVector, DenseVectorWitness};
let v = DenseVector::from_vec(vec![1, 2, 3]);
assert_eq!(DenseVectorWitness::fmap(v, |x| x * 2).as_slice(), &[2, 4, 6]);
// The fold visits the stored entries; a structural zero contributes nothing.
let m = CsrMatrix::from_triplets(2, 2, &[(0, 0, 1), (1, 1, 2)]).unwrap();
assert_eq!(CsrMatrixWitness::fold(m, 0, |acc, x| acc + x), 3);
```
`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.
| 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:
| 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`](LEAN_LINEAR.md).
## Dependency
Add the crate to your `Cargo.toml`:
```toml
[dependencies]
deep_causality_linear = "0.1"
```
## Build configurations
| `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](https://github.com/deepcausality-rs/deep_causality/blob/main/README_NO_STD.md) describes the build configuration of every crate in the workspace.
## Features and `no-std`
| `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`.
```bash
cargo build --no-default-features --features no-std -p deep_causality_linear
cargo test --no-default-features --features no-std -p deep_causality_linear
```
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:
```bash
bazel build //deep_causality_linear/...
bazel test //deep_causality_linear/...
```
## 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](https://github.com/deepcausality-rs/deep_causality/blob/main/LICENSE).
## Security
For details about security, please read
the [security policy](https://github.com/deepcausality-rs/deep_causality/blob/main/SECURITY.md).