sketch_spgemm/
lib.rs

1//! Adaptive, sketch-based sparse matrix multiplication.
2//!
3//! `sketch-spgemm` computes products `C = A * B` for sparse matrices. Its
4//! high-level [`auto_spgemm`] entry point estimates an `i64` workload,
5//! chooses either an exact kernel or compressed moment-sketch recovery, and
6//! verifies recovered candidates with independent residual fingerprints.
7//!
8//! The default feature set has no dependencies. Enable `sprs` for zero-copy
9//! borrowed `sprs` CSR operands and native output, or `petgraph` for weighted
10//! adjacency and two-hop path-count helpers. See the `interop` module when either
11//! feature is enabled.
12//!
13//! Matrix containers, [`CsrInput`], [`try_spgemm`], [`spgemm_hash`],
14//! [`try_spgemm_hash`], [`try_spgemm_hash_checked`], and [`dense_matmul`] are
15//! generic over their scalar.
16//! [`try_spgemm`] uses automatic exact/sketch selection for [`Scalar`] (`i64`)
17//! and direct multiplication for other supported scalars. Sketch recovery and
18//! residual fingerprints remain on `i64` because their decoding and field
19//! mapping require stronger integer semantics. The ordinary kernels follow
20//! Rust's normal overflow behavior; [`try_spgemm_checked`] and
21//! [`try_dense_matmul_checked`] report non-representable scalar arithmetic.
22//!
23//! # Example
24//!
25//! ```
26//! use sketch_spgemm::{auto_spgemm, AutoSpGemmConfig, CsrMatrix};
27//!
28//! let a = CsrMatrix::from_triplets(
29//!     2,
30//!     2,
31//!     &[(0, 0, 2), (0, 1, 3), (1, 1, 4)],
32//! );
33//! let b = CsrMatrix::from_triplets(
34//!     2,
35//!     2,
36//!     &[(0, 0, 5), (1, 0, 7), (1, 1, 11)],
37//! );
38//!
39//! let (c, stats) = auto_spgemm(&a, &b, AutoSpGemmConfig::default());
40//!
41//! assert_eq!(c.to_dense().data, vec![31, 33, 28, 44]);
42//! println!("selected path: {:?}", stats.choice);
43//! ```
44//!
45//! See the [project README](https://github.com/RustedBytes/sketch-spgemm#readme)
46//! for algorithm details, workload guidance, and benchmark options.
47
48#![forbid(unsafe_code)]
49
50/// Automatic workload analysis and exact/sketch execution selection.
51pub mod auto;
52/// Scalar-aware high-level exact/sketch dispatch.
53pub mod dispatch;
54/// Errors returned by fallible multiplication and adapter APIs.
55pub mod error;
56/// Probabilistic residual fingerprints for recovered products.
57pub mod fingerprint;
58/// Explicit Guruswami–Umans–Vadhan recovery construction.
59pub mod guv;
60/// Generic dense, CSR, and representation-independent matrix types.
61pub mod matrix;
62/// Canonical CSR transformations and checked element-wise operations.
63pub mod ops;
64/// Sparse-recovery backends and nested multiplication algorithms.
65pub mod recovery;
66/// Adaptive rectangular dense/sparse multiplication kernels.
67pub mod rect;
68/// Implicit sketch maps and the theoretical round schedule.
69pub mod sketch;
70/// Exact baseline sparse and dense multiplication kernels.
71pub mod spgemm;
72/// Deterministic synthetic workloads for experiments and benchmarks.
73pub mod synthetic;
74
75/// Optional interoperability with sparse-matrix and graph ecosystems.
76#[cfg(any(feature = "sprs", feature = "petgraph"))]
77pub mod interop;
78
79pub use auto::{
80    analyze_workload, auto_spgemm, candidate_product_count, try_analyze_workload, try_auto_spgemm,
81    AutoChoice, AutoSpGemmConfig, AutoSpGemmStats, AutoTimingStats, ExactMethod, WorkloadEstimate,
82};
83pub use dispatch::{try_spgemm, SpGemmDispatchScalar, SpGemmExecutionStats};
84pub use error::{ArithmeticOperation, MatrixOperand, SpGemmError};
85pub use fingerprint::{FingerprintConfig, FingerprintStats, ResidualFingerprint};
86pub use guv::{GuvConfig, GuvError, GuvParameters, GuvRecovery};
87pub use matrix::{
88    CheckedAddScalar, CheckedSpGemmScalar, CsrBuildError, CsrBuilder, CsrInput, CsrMatrix,
89    CsrRowIter, CsrStructureError, CsrView, DenseMatrix, Matrix, MatrixLike, Scalar, SpGemmScalar,
90};
91pub use recovery::{
92    left_recovery_sketch, nested_spgemm, nested_spgemm_with_options, nested_spgemm_with_policy,
93    right_recovery_sketch, right_recovery_sketch_masked, safe_decode_product, safe_decode_scalar,
94    BinaryRecoveryMatrix, CorrectionPassStats, MomentConfig, MomentRecovery, NestedOptions,
95    NestedRoundStats, NestedSpGemmStats, RecoveryBackend, SignatureConfig, SignatureRecovery,
96};
97pub use rect::{
98    adaptive_matmul, adaptive_matmul_prepared, PreparedFactor, RectangularKernel,
99    RectangularPolicy, RectangularStats,
100};
101pub use sketch::{
102    direct_two_sided_sketch, left_sketch, paper_schedule, right_sketch, RoundParams, SketchMap,
103};
104pub use spgemm::{
105    dense_matmul, spgemm_hash, try_dense_matmul_checked, try_spgemm_checked,
106    try_spgemm_checked_with_accumulator, try_spgemm_hash, try_spgemm_hash_checked,
107    try_spgemm_hash_checked_with_options, try_spgemm_hash_with_options, try_spgemm_semiring,
108    PlusTimes, Semiring, SpGemmOptions, SpGemmStats,
109};
110pub use synthetic::{overlap_problem, sparse_output_problem, SyntheticProblem};
sketch_spgemm/lib.rs

sketch_spgemm/
lib.rs
