rma 0.4.0

Rare, high-performance mathematical algorithms for Rust.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

#![doc = r#"
# R-Math Algorithms

A Rust crate for rare, high-performance mathematical algorithms not commonly found in mainstream libraries aimed for practical use.

## Features
- Chakravala: Solves Pell's equation x² - d*y² = 1 for a given non-square integer d.
- Berlekamp's Algorithm: Factorization of polynomials over finite fields (GF(p))
- Tonelli-Shanks: Modular square roots (r^2 ≡ n mod p) over prime moduli (constant-time version)
- Cuthill-McKee & Reverse Cuthill-McKee: Bandwidth reduction for sparse symmetric matrices (adjacency list, CSR, and CSC formats)
    - Supports conversion from `sprs` sparse matrix types
- Freivalds' Algorithm: Fast probabilistic verification of matrix multiplication (scalar, modular, and SIMD-accelerated variants)
- Fast Minimum Degree Algorithm: Exact elimination ordering for sparse matrices with O(nm) complexity
    - First algorithm to improve on the naive O(n³) approach (Cummings et al., 2020)
    - Achieves output-sensitive bounds of O(min{m√m*, Δm*} log n)
    - Based on breakthrough theoretical results from Cummings, Fahrbach, and Fatehpuria
- Well-documented, tested, and benchmarked implementations
- SIMD acceleration for Freivalds' algorithm (nightly Rust required, `simd` feature)
- `no_std` compatible (except for benchmarks and RNG)

## Usage

Add to your `Cargo.toml`:
```toml
[dependencies]
rma = "0.4"
```

Enable SIMD features (nightly Rust required):
```toml
[dependencies]
rma = { version = "0.4", features = ["simd"] }
```

## SIMD Feature
- The `simd` feature enables SIMD-accelerated Freivalds' algorithm. Requires nightly Rust and the `portable_simd` feature.
- On stable Rust, only scalar and modular versions are available.

## Examples

See the documentation for each algorithm.

## License
Licensed under either of
- Apache License, Version 2.0
- MIT license

"#]
#![cfg_attr(feature = "simd", feature(portable_simd))]

pub mod freivalds;

pub use freivalds::freivalds_verify_scalar;
pub use freivalds::freivalds_verify_scalar_mod;
#[cfg(feature = "simd")]
pub use freivalds::freivalds_verify_simd;

pub mod cuthill_mckee;
pub use cuthill_mckee::{
    CscMatrix, CsrMatrix, cuthill_mckee, cuthill_mckee_csc, cuthill_mckee_csr,
    reverse_cuthill_mckee, reverse_cuthill_mckee_csc, reverse_cuthill_mckee_csr,
};

pub mod tonelli_shanks;
pub use tonelli_shanks::{TonelliShanksError, tonelli_shanks_ct};

pub mod berlekamp;

pub mod chakravala;
pub use chakravala::chakravala;

pub mod fast_minimum_degree;
pub use fast_minimum_degree::{fast_minimum_degree, fast_minimum_degree_with_stats, FastMinimumDegreeError};