sketch-spgemm 0.11.0

Adaptive SketchSpGEMM with low-overhead auto selection and fused residual fingerprints
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

//! Adaptive, sketch-based sparse matrix multiplication.
//!
//! `sketch-spgemm` computes products `C = A * B` for sparse matrices. Its
//! high-level [`auto_spgemm`] entry point estimates an `i64` workload,
//! chooses either an exact kernel or compressed moment-sketch recovery, and
//! verifies recovered candidates with independent residual fingerprints.
//!
//! The default feature set has no dependencies. Enable `sprs` for zero-copy
//! borrowed `sprs` CSR operands and native output, or `petgraph` for weighted
//! adjacency and two-hop path-count helpers. See the `interop` module when either
//! feature is enabled.
//!
//! Matrix containers, [`CsrInput`], [`try_spgemm`], [`spgemm_hash`],
//! [`try_spgemm_hash`], [`try_spgemm_hash_checked`], and [`dense_matmul`] are
//! generic over their scalar.
//! [`try_spgemm`] uses automatic exact/sketch selection for [`Scalar`] (`i64`)
//! and direct multiplication for other supported scalars. Sketch recovery and
//! residual fingerprints remain on `i64` because their decoding and field
//! mapping require stronger integer semantics. The ordinary kernels follow
//! Rust's normal overflow behavior; [`try_spgemm_checked`] and
//! [`try_dense_matmul_checked`] report non-representable scalar arithmetic.
//!
//! # Example
//!
//! ```
//! use sketch_spgemm::{auto_spgemm, AutoSpGemmConfig, CsrMatrix};
//!
//! let a = CsrMatrix::from_triplets(
//!     2,
//!     2,
//!     &[(0, 0, 2), (0, 1, 3), (1, 1, 4)],
//! );
//! let b = CsrMatrix::from_triplets(
//!     2,
//!     2,
//!     &[(0, 0, 5), (1, 0, 7), (1, 1, 11)],
//! );
//!
//! let (c, stats) = auto_spgemm(&a, &b, AutoSpGemmConfig::default());
//!
//! assert_eq!(c.to_dense().data, vec![31, 33, 28, 44]);
//! println!("selected path: {:?}", stats.choice);
//! ```
//!
//! See the [project README](https://github.com/RustedBytes/sketch-spgemm#readme)
//! for algorithm details, workload guidance, and benchmark options.

#![forbid(unsafe_code)]

/// Automatic workload analysis and exact/sketch execution selection.
pub mod auto;
/// Scalar-aware high-level exact/sketch dispatch.
pub mod dispatch;
/// Errors returned by fallible multiplication and adapter APIs.
pub mod error;
/// Probabilistic residual fingerprints for recovered products.
pub mod fingerprint;
/// Explicit Guruswami–Umans–Vadhan recovery construction.
pub mod guv;
/// Generic dense, CSR, and representation-independent matrix types.
pub mod matrix;
/// Canonical CSR transformations and checked element-wise operations.
pub mod ops;
/// Sparse-recovery backends and nested multiplication algorithms.
pub mod recovery;
/// Adaptive rectangular dense/sparse multiplication kernels.
pub mod rect;
/// Implicit sketch maps and the theoretical round schedule.
pub mod sketch;
/// Exact baseline sparse and dense multiplication kernels.
pub mod spgemm;
/// Deterministic synthetic workloads for experiments and benchmarks.
pub mod synthetic;

/// Optional interoperability with sparse-matrix and graph ecosystems.
#[cfg(any(feature = "sprs", feature = "petgraph"))]
pub mod interop;

pub use auto::{
    analyze_workload, auto_spgemm, candidate_product_count, try_analyze_workload, try_auto_spgemm,
    AutoChoice, AutoSpGemmConfig, AutoSpGemmStats, AutoTimingStats, ExactMethod, WorkloadEstimate,
};
pub use dispatch::{try_spgemm, SpGemmDispatchScalar, SpGemmExecutionStats};
pub use error::{ArithmeticOperation, MatrixOperand, SpGemmError};
pub use fingerprint::{FingerprintConfig, FingerprintStats, ResidualFingerprint};
pub use guv::{GuvConfig, GuvError, GuvParameters, GuvRecovery};
pub use matrix::{
    CheckedAddScalar, CheckedSpGemmScalar, CsrBuildError, CsrBuilder, CsrInput, CsrMatrix,
    CsrRowIter, CsrStructureError, CsrView, DenseMatrix, Matrix, MatrixLike, Scalar, SpGemmScalar,
};
pub use recovery::{
    left_recovery_sketch, nested_spgemm, nested_spgemm_with_options, nested_spgemm_with_policy,
    right_recovery_sketch, right_recovery_sketch_masked, safe_decode_product, safe_decode_scalar,
    BinaryRecoveryMatrix, CorrectionPassStats, MomentConfig, MomentRecovery, NestedOptions,
    NestedRoundStats, NestedSpGemmStats, RecoveryBackend, SignatureConfig, SignatureRecovery,
};
pub use rect::{
    adaptive_matmul, adaptive_matmul_prepared, PreparedFactor, RectangularKernel,
    RectangularPolicy, RectangularStats,
};
pub use sketch::{
    direct_two_sided_sketch, left_sketch, paper_schedule, right_sketch, RoundParams, SketchMap,
};
pub use spgemm::{
    dense_matmul, spgemm_hash, try_dense_matmul_checked, try_spgemm_checked,
    try_spgemm_checked_with_accumulator, try_spgemm_hash, try_spgemm_hash_checked,
    try_spgemm_hash_checked_with_options, try_spgemm_hash_with_options, try_spgemm_semiring,
    PlusTimes, Semiring, SpGemmOptions, SpGemmStats,
};
pub use synthetic::{overlap_problem, sparse_output_problem, SyntheticProblem};