Crate la_stack

Expand description

§la-stack

la-stack

Fast, stack-allocated linear algebra for fixed dimensions in Rust.

This crate grew from the need to support delaunay with fast, stack-allocated linear algebra primitives and algorithms while keeping the API intentionally small and explicit.

§Contents

Introduction
Use this crate when
Quickstart
Scalar and bounded-value types
API at a glance
Features
Mathematical basis
Design goals
Anti-goals
Documentation Map
Examples
Benchmarks
Contributing
Citation
References
AI Agents
License

§📐 Introduction

la-stack provides a handful of const-generic, stack-backed building blocks:

gram_matrix(&[Vector<N>; M]) for allocation-free Matrix<M> construction from pairwise vector inner products, with bit-for-bit symmetry. Gram matrices encode lengths and angles and support simplex/facet volume calculations; see Gram matrices and geometric measures. Each independent dot product is checked once; rounding has no certified error bound, and positive definiteness or affine independence must still be established by factorization or the caller. Benchmark square simplex and rectangular facet inputs through dimension 8 with cargo bench --locked --features bench --bench gram.
Interval and IntervalMatrix<const D: usize> for outward-rounded, proof-bearing determinant filters through D=7
Ldlt<const D: usize> for no-pivot factorization intended for exactly symmetric positive-definite matrices (solve + det; typed pivot diagnostics)
Lu<const D: usize> for LU factorization with partial pivoting (solve + det)
Matrix<const D: usize> for fixed-size square f64 matrices backed by [[f64; D]; D]
RationalVector<const D: usize> and RationalMatrix<const D: usize> for exact rational inputs behind the optional "exact" feature
ScalarWithErrorBound for proof-bearing fixed-vector dot products and affine differences over finite f64 inputs
Vector<const D: usize> for fixed-length f64 vectors backed by [f64; D]

§✅ Use this crate when

Robust predicates matter for geometry-style workloads near degeneracy
Stack allocation and Copy value semantics fit your data flow
You need a certified sign or threshold comparison for a fixed-vector dot product or axis · (left - right) expression
You need a cheap, sound interval filter for determinant expressions assembled from rounded binary64 operations
You need exact determinants, exact determinant signs, or exact linear solves for fixed-size systems
You prefer a default build with no runtime dependencies
You want explicit LU / LDLT / determinant APIs rather than a broad algebra toolkit
Your matrices and vectors have small, fixed dimensions known at compile time

§🚀 Quickstart

The minimum supported Rust version (MSRV) is 1.98.1.

Add this to your Cargo.toml:

[dependencies]
la-stack = "0.4.6"

§Solve a 5×5 system

This system has solution [1, 2, 3, 4, 5] and requires partial pivoting:

use la_stack::prelude::*;

fn main() -> Result<(), LaError> {
    // The zero leading entry requires LU pivoting.
    let a = Matrix::<5>::try_from_rows([
        [0.0, 2.0, -1.0, 1.0, 3.0],
        [4.0, -1.0, 2.0, 0.0, 1.0],
        [1.0, 3.0, 5.0, -2.0, 0.0],
        [2.0, 0.0, -1.0, 4.0, 1.0],
        [-1.0, 2.0, 0.0, 1.0, 6.0],
    ])?;
    let b = Vector::try_new([20.0, 13.0, 14.0, 20.0, 37.0])?;
    let lu = a.lu(DEFAULT_SINGULAR_TOL)?;
    let x = lu.solve(b)?;

    for (&actual, expected) in x.as_array().iter().zip([1.0, 2.0, 3.0, 4.0, 5.0]) {
        assert!((actual - expected).abs() <= 1e-12);
    }
    Ok(())
}

The assertion tolerance is suitable for this known example; LU does not provide a certified solution error bound.

§Feature flags

bench: repository-development gate used only by benchmark targets and benchmark-input tests; application crates should not enable it
default: no runtime dependencies; includes outward-rounded Interval and IntervalMatrix APIs
exact: exact determinant signs, determinant values, and solves over stored f64 values or caller-supplied BigRational inputs

§🔢 Scalar and bounded-value types

The public point-value scalar model deliberately has two input domains:

arbitrary-precision BigRational through RationalMatrix<D> and RationalVector<D> behind the optional "exact" feature;
finite f64 through Matrix<D> and Vector<D> for floating-point work.

Interval is a separate bounded-value layer over finite f64 endpoints. It encloses exact-real values during a small set of outward-rounded operations and feeds IntervalMatrix<D> determinant proofs; it does not make Matrix generic over alternate scalars or provide a general interval package.

This is not a generic scalar-parameterized API. Exact support intentionally covers the robustness-sensitive operations that require it: determinant sign, determinant value, and linear solve, followed by explicit strict or rounded conversion when an f64 result is required. It does not promise a BigRational counterpart for every floating-point helper or factorization.

Lower-precision f32 / f16 throughput-oriented workloads are outside the crate’s scope; they usually indicate large-matrix or accelerator-oriented use cases better served by broader linear-algebra libraries.

§🧩 API at a glance

Start with the capability you need; the API reference lists the complete public surface, and the worked examples show how to combine operations.

Capability	Main entry points
Certified dot, affine-difference, and determinant estimates	`ScalarWithErrorBound`, `DeterminantWithErrorBound`
Exact signs, determinants, solves, and output conversion¹	Exact arithmetic examples
Floating-point determinants and solves	`Matrix<D>`, `Lu<D>`, `Ldlt<D>`
Gram matrix construction	`gram_matrix`
Interval expressions and determinant signs	`Interval`, `IntervalMatrix<D>`
Runtime selection of a const-generic matrix dimension	Dimension dispatch examples
Vector operations and norms	`Vector<D>`

Tolerance validates numerical rejection thresholds. LaError and its reason/location enums preserve structured failure details; match non-exhaustive enums with a wildcard and struct-style variants with ... See the storage, access, and error guide for the full contracts.

¹ Requires features = ["exact"].

§✨ Features

§Adaptive determinant filtering (D ≤ 4)

det_direct_with_errbound() pairs a determinant with its certified absolute bound, without optional dependencies. Resolve the sign when |det| > bound; otherwise an exact fallback is needed. With exact, det_sign_exact() handles filtering and fallback automatically. Worked examples: the floating-point filter and exact fallback.

§Certified dot products and affine differences

dot_with_errbound() and dot_difference_with_errbound() return certified bounds for dot products and axis · (left - right) over the original stored coordinates. Their endpoints support sign and threshold proofs; a bound that straddles the threshold or an unavailable certificate is inconclusive. Worked examples: dot-product signs and affine threshold tests.

§Compile-time determinants (D ≤ 4)

det_direct() evaluates closed-form determinants in const contexts through D=4. det() selects those formulas automatically and uses zero-tolerance LU for larger dimensions; a failed numerical pivot remains LaError::Singular. Compile-time example and dimension contracts.

§Exact arithmetic (`"exact"` feature)

Enable exact determinant signs, determinant values, and solves:

[dependencies]
la-stack = { version = "0.4.6", features = ["exact"] }

Matrix / Vector exact methods preserve stored f64 values; RationalMatrix / RationalVector also preserve rational expressions before any f64 rounding. Keep exact results or explicitly choose strict versus rounded conversion with ExactF64Conversion. Worked examples: rational inputs, exact solves, and output conversion.

§LDLT determinant

Matrix::ldlt() provides a square-root-free factorization for exactly symmetric positive-definite matrices, supporting determinants and solves without pivoting. Approximate symmetry is not sufficient, and floating-point success is not an exact positive-definiteness certificate. Worked example and typed pivot diagnostics.

§LU solve

Matrix::lu() uses partial pivoting for general square systems. Reuse one Lu factorization for multiple right-hand sides or a determinant; pivot tolerances control rejection, not solution accuracy. Worked example: solving and reusing factors.

§Outward-rounded interval determinants

Interval preserves bounds while assembling differences, squares, and other expressions. IntervalMatrix::det_sign() certifies determinant signs through D=7: an enclosure separated from zero proves its sign, and [0, 0] proves exact zero. Other overlaps with zero are inconclusive and may need exact fallback. Worked example: lifted coordinates, range errors, and fallback.

§Overflow-safe Euclidean norms

Vector::norm() avoids unnecessary overflow and underflow from squaring coordinates. norm_squared() computes the squared norm and can overflow even when the norm is finite. Both results remain approximate, without a certified error bound. Worked example and range contracts.

v0.4.6 migration: Vector::norm2_sq() is renamed to Vector::norm_squared(), the unreleased Vector::norm2() API is named Vector::norm(), and Matrix::inf_norm() is renamed to Matrix::norm_inf(). The old method names are removed; their numerical behavior and error contracts are unchanged by the renames. Matrix::norm_inf() remains the maximum absolute row sum.

§🧮 Mathematical basis

la-stack operates on finite IEEE 754 binary64 values in small, fixed dimensions. Its floating-point paths use LU with partial pivoting, LDLT without pivoting for exactly symmetric positive-definite matrices, and closed-form determinants through D=4. These results remain subject to conditioning and binary64 rounding; factorization tolerances are rejection thresholds, not accuracy guarantees. For D≤4, direct determinants can be paired with a conservative absolute roundoff bound when its range preconditions hold. Fixed-vector dot products and direct affine differences can likewise return a paired estimate and certified absolute roundoff bound without enabling arbitrary-precision dependencies.

Derived binary64 expressions can instead be assembled with Interval subtraction, addition, multiplication, negation, and square. The resulting IntervalMatrix<D> determinant sign is certified through D=7 when its enclosure separates zero; the singleton [0, 0] also certifies exact zero. Every other overlap with zero is explicitly inconclusive. This default-feature surface is distinct from arbitrary-precision exact arithmetic.

With features = ["exact"], callers can either lift stored binary64 inputs losslessly or supply already-exact rational inputs for exact determinant signs, determinant values, and solves. Exactness over binary64 input starts at the stored values and cannot recover information rounded away before construction. See the mathematical basis for the algorithms, validity boundaries, and supporting references.

§🎯 Design goals

✅ const fn where possible (compile-time evaluation of determinants, dot products, etc.)
✅ Const-generic storage (no dynamically sized matrix or vector representation)
✅ Copy types where possible
✅ Defined binary64 arithmetic semantics: Rust’s f64::algebraic_* operations are forbidden because their unspecified reassociation, precision, and special-value behavior is incompatible with the crate’s error bounds, non-finite classification, exact fallbacks, and reproducibility contract; deliberate f64::mul_add remains allowed for its defined single-rounding semantics
✅ Error-bounded f64 dot, affine-difference, and determinant filtering plus optional exact signs (dot_with_errbound, dot_difference_with_errbound, det_errbound, det_sign_exact)
✅ Overflow- and underflow-safe Euclidean vector norms (norm)
✅ Outward-rounded interval expressions and division-free determinant signs through D=7, with explicit inconclusive evidence
✅ Exact determinant values and linear solves via optional arbitrary-precision arithmetic (det_exact, solve_exact, strict/rounded f64 conversions)
✅ Explicit algorithms (LU, solve, determinant)
✅ Inline, stack-backed storage for core types; optional arbitrary-precision exact values allocate as required
✅ No runtime dependencies by default (optional features may add deps)
✅ unsafe forbidden

See CHANGELOG.md for release history and docs/roadmap.md for current release planning.

§🚫 Anti-goals

Alternate scalar families: la-stack deliberately supports finite f64 and optional exact BigRational input domains, not f32, f16, complex, or generic scalar APIs
Bare-metal performance: use blas or lapack with a native backend selected through blas-src, lapack-src, or openblas-src
Broad general-purpose linear algebra: use nalgebra
Large matrices/dimensions with parallelism: use faer

§🗺️ Documentation Map

API guide — worked examples, API selection, storage, and error contracts.
Benchmarking — benchmark suites, comparison workflows, and measurement methodology.
Coverage — local and CI coverage commands and report locations.
Mathematical basis — algorithms, numerical guarantees, and limitations.
Performance reports — release-to-release measurement results and provenance.
Releasing — release preparation, validation, and publication.
Roadmap — release planning, future directions, and non-goals.

§📋 Examples

The examples/ directory contains small, runnable programs:

const_det_4x4 — compile-time 4×4 determinant via det_direct()
det_5x5 — determinant of a 5×5 matrix via LU
exact_det_3x3 — exact determinant value of a near-singular 3×3 matrix (requires exact feature)
exact_sign_3x3 — exact determinant sign of a near-singular 3×3 matrix (requires exact feature)
exact_solve_3x3 — exact solve of a near-singular 3×3 system vs f64 LU (requires exact feature)
ldlt_solve_3x3 — solve a 3×3 symmetric positive definite system via LDLT
rational_input_5x5 — exact rational solve of a 5×5 system that becomes singular as f64 (requires exact feature)
solve_5x5 — solve a 5×5 system via LU with partial pivoting

just examples
# or individually:
cargo run --example const_det_4x4
cargo run --example det_5x5
cargo run --features exact --example exact_det_3x3
cargo run --features exact --example exact_sign_3x3
cargo run --features exact --example exact_solve_3x3
cargo run --example ldlt_solve_3x3
cargo run --features exact --example rational_input_5x5
cargo run --example solve_5x5

§📈 Benchmarks (vs nalgebra/faer)

LU solve (factor + solve): median time vs dimension

Raw data: docs/assets/bench/vs_linalg_lu_solve_median.csv Measurement provenance: docs/assets/bench/vs_linalg_lu_solve_median.provenance.json

Representative benchmark: lu_solve factors the matrix and solves one right-hand side. Median time is lower-is-better, and the “la-stack vs nalgebra/faer” columns show the % time reduction relative to each baseline (positive means the recorded la-stack median is lower). These are descriptive point-estimate ratios, not statistical significance claims or an aggregate score across operations.

Timings count only when the implementation preserves the documented correctness guarantees and invariants. Performance claims require comparable before-and-after evidence using the same inputs, configuration, and environment. This snapshot records the measured source state, available CPU model, operating system, Rust toolchain, dependency lock and harness digests, Criterion command, and correctness-gate result in the adjacent JSON sidecar. The publication workflow requires complete canonical-dimension coverage and regenerates the CSV, SVG, README table, and provenance together.

For the full per-kernel comparison methodology, algorithm citations, input construction, and release-comparison workflow details, see docs/BENCHMARKING.md. For the current release-to-release performance snapshot, see docs/performance.md. The exact release suite includes the already-exact rational-input groups for D=2 through D=8. Those rows report RationalMatrix::det_sign, det, and solve alongside straightforward BigRational Gaussian determinant and solve references. Releases produced with the rational-input harness include Criterion point estimates and confidence intervals for these rows; comparisons against a pre-API baseline retain them as explicit current-only measurements.

The focused interval Criterion suite covers conclusive and inconclusive relative-coordinate lifted determinant signs at D=4 and the maximum supported D=7 workload. Run it with just bench-interval; fixture validation stays outside the timed closures.

The focused linear_form Criterion suite compares plain and certified dot products and covers both well-separated and inconclusive dot/affine-difference filters at D=4. Run it with just bench-linear-form; exact small-integer fixture expectations are validated outside the timed closures.

D	la-stack median (ns)	nalgebra median (ns)	faer median (ns)	reduction vs nalgebra (point est.)	reduction vs faer (point est.)
2	2.021	4.479	182.532	+54.9%	+98.9%
3	9.977	22.795	217.567	+56.2%	+95.4%
4	22.101	51.739	241.525	+57.3%	+90.8%
5	46.070	69.003	326.848	+33.2%	+85.9%
8	128.364	165.933	401.400	+22.6%	+68.0%
16	643.532	569.446	903.140	-13.0%	+28.7%
32	2,755.773	2,710.235	2,919.290	-1.7%	+5.6%
64	17,518.634	14,313.979	12,108.783	-22.4%	-44.7%

§🤝 Contributing

A short contributor workflow:

Install Rust 1.98.1 through rustup, Git, GitHub CLI, Python 3.14, uv 0.12.5, and jq. Then install the pinned just release from its locked dependency graph:

cargo install --locked just --version 1.58.0
just setup        # install/verify dev tools + sync Python deps + build
just check        # lint/validate (non-mutating)
just fix          # apply auto-fixes (mutating)
just ci           # lint + tests + examples + bench compile

The repository uses cargo-nextest for runnable Rust tests, cargo-machete for unused-dependency checks, rumdl for Markdown, dprint plus yamllint for YAML/CFF, taplo for TOML, and typos for spelling. Python 3.14 support tooling is locked with uv and checked by Ruff, Ty, and Semgrep. GitHub Actions references are SHA-pinned, restricted to an explicit allowlist, and kept with readable version comments for review.

CI runs just ci on Ubuntu, macOS, and Windows to keep platform coverage aligned with the local comprehensive validation path.

For coverage commands and report locations, see docs/MEASURING_COVERAGE.md. For the full contributor workflow, see CONTRIBUTING.md.

§📚 Citation

If you use this library in academic work, please cite it using CITATION.cff (or GitHub’s “Cite this repository” feature). Tagged releases are archived on Zenodo under the all-versions concept DOI.

§🔎 References

For canonical references to the algorithms used by this crate, see REFERENCES.md.

§🤖 AI Agents

AI coding assistants should read AGENTS.md before proposing or applying changes. See CONTRIBUTING.md for the repository’s AI-assisted development note.

§📜 License

BSD 3-Clause License. See LICENSE.

Modules§

guide: Worked examples and contracts for choosing and combining APIs.
prelude: Common imports for ergonomic usage.

Macros§

try_with_interval_matrix: Fallibly dispatch a runtime dimension to a concrete interval matrix.
try_with_rational_matrixexact: Fallibly dispatch a runtime dimension to a concrete exact rational matrix.
try_with_stack_matrix: Fallibly dispatch a runtime dimension to a concrete stack-allocated matrix.

Structs§

BigIntexact: A big signed integer type.
DeterminantWithErrorBound: A closed-form determinant and its certified absolute error bound.
Interval: A closed finite binary64 interval [lower, upper].
IntervalMatrix: Fixed-size square matrix of outward-rounded Interval entries.
Ldlt: LDLT factorization (A = L D Lᵀ) for exactly symmetric positive-definite matrices.
Lu: LU decomposition (PA = LU) with partial pivoting.
Matrix: Finite fixed-size square matrix D×D, stored inline.
RationalMatrixexact: Exact rational square matrix with compile-time dimension D.
RationalVectorexact: Exact rational vector with compile-time dimension D.
ScalarWithErrorBound: A scalar estimate paired with a certified absolute error bound.
Tolerance: Finite, non-negative tolerance used by numerical predicates and factorizations.
Vector: Finite fixed-size vector of length D, stored inline.

Enums§

ArithmeticOperation: Arithmetic operation associated with a computation failure.
DeterminantSignexact: The exact sign of a determinant.
FactorizationKind: Factorization whose pivot policy rejected a matrix as numerically singular.
IntervalBound: Endpoint of an interval constructor input.
IntervalDeterminantSign: Sign evidence from an outward-rounded interval determinant.
IntervalOperand: Operand of a binary scalar operation used to construct an interval.
InvalidToleranceReason: Reason a raw tolerance cannot become a crate::Tolerance.
LaError: Linear algebra errors.
NonFiniteLocation: Location at which a non-finite value was observed.
NonFiniteOrigin: Provenance of a non-finite value.
PositiveSemidefiniteViolation: Computed LDLT condition that violates the no-pivot positive-semidefinite factorization requirements.
SingularityReason: Mathematical or numerical reason a matrix was classified as singular.
UnrepresentableReason: Reason an exact result cannot satisfy an exact-to-f64 conversion contract.

Constants§

DEFAULT_SINGULAR_TOL: Default absolute threshold used for singularity/degeneracy detection.
ERR_COEFF_2: Absolute error coefficient for Matrix::<2>::det_direct.
ERR_COEFF_3: Absolute error coefficient for Matrix::<3>::det_direct.
ERR_COEFF_4: Absolute error coefficient for Matrix::<4>::det_direct.
MAX_INTERVAL_MATRIX_DIM: Largest dimension supported by IntervalMatrix::det and IntervalMatrix::det_sign.
MAX_RATIONAL_MATRIX_DISPATCH_DIMexact: Largest dimension supported by try_with_rational_matrix!.
MAX_STACK_MATRIX_DISPATCH_DIM: Largest dimension supported by try_with_stack_matrix!.

Traits§

ExactF64Conversionexact: Convert an already-computed exact result to finite binary64 output.
FromPrimitiveexact: A generic trait for converting a number to a value.
Signedexact: Useful functions for signed numbers (i.e. numbers that can be negative).
ToPrimitiveexact: A generic trait for converting a value to a number.

Functions§

gram_matrix: Construct a stack-backed Matrix<M> of pairwise vector dot products.

Type Aliases§

BigRationalexact: Alias for arbitrary precision rationals.

Crate la_stack

Crate la_stack Copy item path

§la-stack

§Contents

§📐 Introduction

§✅ Use this crate when

§🚀 Quickstart

§Solve a 5×5 system

§Feature flags

§🔢 Scalar and bounded-value types

§🧩 API at a glance

§✨ Features

§Adaptive determinant filtering (D ≤ 4)

§Certified dot products and affine differences

§Compile-time determinants (D ≤ 4)

§Exact arithmetic ("exact" feature)

§LDLT determinant

§LU solve

§Outward-rounded interval determinants

§Overflow-safe Euclidean norms

§🧮 Mathematical basis

§🎯 Design goals

§🚫 Anti-goals

§🗺️ Documentation Map

§📋 Examples

§📈 Benchmarks (vs nalgebra/faer)

§🤝 Contributing

§📚 Citation

§🔎 References

§🤖 AI Agents

§📜 License

Modules§

Macros§

Structs§

Enums§

Constants§

Traits§

Functions§

Type Aliases§

Crate la_stack

§Exact arithmetic (`"exact"` feature)