yui-matrix 0.5.0

yui-matrix

Sparse and dense matrix types for the yui workspace, together with the decompositions (PLUQ, Smith normal form, LLL) used by the homology-computation pipeline.

Layout

src/
├── perm.rs       — `Perm`: permutation of 0..n
├── dense/
│   ├── mat.rs    — `Mat<R>`: dense matrix (over `nalgebra::DMatrix`)
│   ├── pluq.rs   — dense PLUQ decomposition + solver
│   ├── snf.rs    — Smith normal form
│   └── lll.rs    — LLL / Hermite normal form
└── sparse/
    ├── sp_mat.rs — `SpMat<R>`: CSC sparse matrix (over `nalgebra_sparse::CscMatrix`)
    ├── sp_vec.rs — `SpVec<R>`: CSC sparse column vector
    ├── trans.rs  — `Trans<R>`: forward/backward basis-change tracking
    ├── pivot.rs  — pivot-finding heuristic (Bouillaguet–Delaplace–Voge)
    ├── pluq.rs   — sparse PLUQ + iterative linear solver
    ├── schur.rs  — Schur-complement reduction
    ├── snf.rs    — sparse Smith normal form
    └── triang.rs — triangular solves

Mat and SpMat both implement the minimal MatTrait (shape, n_rows, n_cols, is_square).

Key types

Shared

Perm — permutation of 0..n. Stored as Either<usize, Vec<usize>> so Perm::id(n) is zero-cost. Operations: inv, composition via Mul (right-to-left, (p * q)(i) = p(q(i))), apply_to / apply_inv_to (consuming left / inverse-left action on Vec<R>), shift / extend (prepend / append identity slots), forward_indices (build a perm that pulls a prefix to the front).

Dense

Mat<R> — dense matrix. Constructors: zero, id, from_row_major, generate, diag, scalar. Operations: transpose, map, plus the entry-level mutators swap_rows, add_row_to, left_elementary, etc.

Sparse

SpMat<R> — sparse matrix (CSC). Same constructor surface as Mat plus from_entries, from_col_vecs. Block ops: block_split, block_combine, block_diag, h_stack / v_stack, h_split / v_split. Permutation: permute, permute_rows, permute_cols, permute_and_split. Sub-extraction (each produces a new matrix): extract, submat, submat_rows, submat_cols.
SpVec<R> — sparse column vector (CSC with n_cols = 1). Stacking / slicing via stack, split, subvec.
Trans<R> — composable forward/backward transformation (a sequence of sparse matrices), used to track basis changes through reductions.

Algorithms

These are tailored to the needs of the homology-computation pipeline rather than being a general-purpose linear-algebra library; coverage is intentionally narrow.

Algorithm	Dense	Sparse
Heuristic pivot finder (Bouillaguet–Delaplace–Voge)	—	`sparse::pivot::find_pivots`
Schur-complement reduction	—	`sparse::schur::Schur`
Triangular solve	(used internally by dense PLUQ)	`sparse::triang`
PLUQ decomposition over a ring	`dense::pluq::pluq`	`sparse::pluq::pluq` / `pre_pluq`
Linear solve over a field (`A·x = y`)	`dense::pluq::solve_pluq`	`sparse::pluq::solve_pluq` (+ incremental `solve_pluq_incr`)
Smith normal form	`dense::snf`	`sparse::snf::sp_snf`
LLL lattice reduction / Hermite normal form	`dense::lll::{lll, lll_hnf}`	—

Conventions

All algorithms are generic over R: Ring, for<'x> &'x R: RingOps<R> (or R: Field, for<'x> &'x R: FieldOps<R> for solvers). The for<'x> HRTB on the reference impl is required throughout.
Permutations compose right-to-left in math convention: (p * q)(i) = p(q(i)). Perm::apply_to(y) is the left action result[p(i)] = y[i].

Quick example

use yui_matrix::sparse::SpMat;

let a = SpMat::from_row_major((3, 3), [
    1, 2, 0,
    0, 3, 4,
    5, 0, 6,
]);
let b = a.transpose();
let c = &a + &b;
assert_eq!(c, SpMat::from_row_major((3, 3), [
    2, 2, 5,
    2, 6, 4,
    5, 4, 12,
]));

Feature flags

multithread (default) — parallelizes the triangular solver and the cycle-free pivot search via [rayon].
serde — Serialize / Deserialize for SpMat and Trans.

License

This library is licensed under the MIT License.

This README was generated by Claude.