1#![doc = r#"
2# R-Math Algorithms
3
4A Rust crate for rare, high-performance mathematical algorithms not commonly found in mainstream libraries aimed for practical use.
5
6## Features
7- Chakravala: Solves Pell's equation x² - d*y² = 1 for a given non-square integer d.
8- Berlekamp's Algorithm: Factorization of polynomials over finite fields (GF(p))
9- Tonelli-Shanks: Modular square roots (r^2 ≡ n mod p) over prime moduli (constant-time version)
10- Cuthill-McKee & Reverse Cuthill-McKee: Bandwidth reduction for sparse symmetric matrices (adjacency list, CSR, and CSC formats)
11 - Supports conversion from `sprs` sparse matrix types
12- Freivalds' Algorithm: Fast probabilistic verification of matrix multiplication (scalar, modular, and SIMD-accelerated variants)
13- Fast Minimum Degree Algorithm: Exact elimination ordering for sparse matrices with O(nm) complexity
14 - First algorithm to improve on the naive O(n³) approach (Cummings et al., 2020)
15 - Achieves output-sensitive bounds of O(min{m√m*, Δm*} log n)
16 - Based on breakthrough theoretical results from Cummings, Fahrbach, and Fatehpuria
17- Well-documented, tested, and benchmarked implementations
18- SIMD acceleration for Freivalds' algorithm (nightly Rust required, `simd` feature)
19- `no_std` compatible (except for benchmarks and RNG)
20
21## Usage
22
23Add to your `Cargo.toml`:
24```toml
25[dependencies]
26rma = "0.4"
27```
28
29Enable SIMD features (nightly Rust required):
30```toml
31[dependencies]
32rma = { version = "0.4", features = ["simd"] }
33```
34
35## SIMD Feature
36- The `simd` feature enables SIMD-accelerated Freivalds' algorithm. Requires nightly Rust and the `portable_simd` feature.
37- On stable Rust, only scalar and modular versions are available.
38
39## Examples
40
41See the documentation for each algorithm.
42
43## License
44Licensed under either of
45- Apache License, Version 2.0
46- MIT license
47
48"#]
49#![cfg_attr(feature = "simd", feature(portable_simd))]
50
51pub mod freivalds;
52
53pub use freivalds::freivalds_verify_scalar;
54pub use freivalds::freivalds_verify_scalar_mod;
55#[cfg(feature = "simd")]
56pub use freivalds::freivalds_verify_simd;
57
58pub mod cuthill_mckee;
59pub use cuthill_mckee::{
60 CscMatrix, CsrMatrix, cuthill_mckee, cuthill_mckee_csc, cuthill_mckee_csr,
61 reverse_cuthill_mckee, reverse_cuthill_mckee_csc, reverse_cuthill_mckee_csr,
62};
63
64pub mod tonelli_shanks;
65pub use tonelli_shanks::{TonelliShanksError, tonelli_shanks_ct};
66
67pub mod berlekamp;
68
69pub mod chakravala;
70pub use chakravala::chakravala;
71
72pub mod fast_minimum_degree;
73pub use fast_minimum_degree::{fast_minimum_degree, fast_minimum_degree_with_stats, FastMinimumDegreeError};