Expand description
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 for algorithm details, workload guidance, and benchmark options.
Re-exports§
pub use auto::analyze_workload;pub use auto::auto_spgemm;pub use auto::candidate_product_count;pub use auto::try_analyze_workload;pub use auto::try_auto_spgemm;pub use auto::AutoChoice;pub use auto::AutoSpGemmConfig;pub use auto::AutoSpGemmStats;pub use auto::AutoTimingStats;pub use auto::ExactMethod;pub use auto::WorkloadEstimate;pub use dispatch::try_spgemm;pub use dispatch::SpGemmDispatchScalar;pub use dispatch::SpGemmExecutionStats;pub use error::ArithmeticOperation;pub use error::MatrixOperand;pub use error::SpGemmError;pub use fingerprint::FingerprintConfig;pub use fingerprint::FingerprintStats;pub use fingerprint::ResidualFingerprint;pub use guv::GuvConfig;pub use guv::GuvError;pub use guv::GuvParameters;pub use guv::GuvRecovery;pub use matrix::CheckedAddScalar;pub use matrix::CheckedSpGemmScalar;pub use matrix::CsrBuildError;pub use matrix::CsrBuilder;pub use matrix::CsrInput;pub use matrix::CsrMatrix;pub use matrix::CsrRowIter;pub use matrix::CsrStructureError;pub use matrix::CsrView;pub use matrix::DenseMatrix;pub use matrix::Matrix;pub use matrix::MatrixLike;pub use matrix::Scalar;pub use matrix::SpGemmScalar;pub use recovery::left_recovery_sketch;pub use recovery::nested_spgemm;pub use recovery::nested_spgemm_with_options;pub use recovery::nested_spgemm_with_policy;pub use recovery::right_recovery_sketch;pub use recovery::right_recovery_sketch_masked;pub use recovery::safe_decode_product;pub use recovery::safe_decode_scalar;pub use recovery::BinaryRecoveryMatrix;pub use recovery::CorrectionPassStats;pub use recovery::MomentConfig;pub use recovery::MomentRecovery;pub use recovery::NestedOptions;pub use recovery::NestedRoundStats;pub use recovery::NestedSpGemmStats;pub use recovery::RecoveryBackend;pub use recovery::SignatureConfig;pub use recovery::SignatureRecovery;pub use rect::adaptive_matmul;pub use rect::adaptive_matmul_prepared;pub use rect::PreparedFactor;pub use rect::RectangularKernel;pub use rect::RectangularPolicy;pub use rect::RectangularStats;pub use sketch::direct_two_sided_sketch;pub use sketch::left_sketch;pub use sketch::paper_schedule;pub use sketch::right_sketch;pub use sketch::RoundParams;pub use sketch::SketchMap;pub use spgemm::dense_matmul;pub use spgemm::spgemm_hash;pub use spgemm::try_dense_matmul_checked;pub use spgemm::try_spgemm_checked;pub use spgemm::try_spgemm_checked_with_accumulator;pub use spgemm::try_spgemm_hash;pub use spgemm::try_spgemm_hash_checked;pub use spgemm::try_spgemm_hash_checked_with_options;pub use spgemm::try_spgemm_hash_with_options;pub use spgemm::try_spgemm_semiring;pub use spgemm::PlusTimes;pub use spgemm::Semiring;pub use spgemm::SpGemmOptions;pub use spgemm::SpGemmStats;pub use synthetic::overlap_problem;pub use synthetic::sparse_output_problem;pub use synthetic::SyntheticProblem;
Modules§
- auto
- Automatic workload analysis and exact/sketch execution selection.
- dispatch
- Scalar-aware high-level exact/sketch dispatch. Scalar-aware high-level sparse multiplication dispatch.
- error
- Errors returned by fallible multiplication and adapter APIs.
- fingerprint
- Probabilistic residual fingerprints for recovered products.
- guv
- Explicit Guruswami–Umans–Vadhan recovery construction. Strongly-explicit Guruswami–Umans–Vadhan / Parvaresh–Vardy expander.
- interop
- Optional interoperability with sparse-matrix and graph ecosystems. Feature-gated adapters for ecosystem matrix and graph types.
- matrix
- Generic dense, CSR, and representation-independent matrix types.
- ops
- Canonical CSR transformations and checked element-wise operations. Canonical CSR transformations and checked element-wise operations.
- recovery
- Sparse-recovery backends and nested multiplication algorithms.
- rect
- Adaptive rectangular dense/sparse multiplication kernels.
- sketch
- Implicit sketch maps and the theoretical round schedule.
- spgemm
- Exact baseline sparse and dense multiplication kernels.
- synthetic
- Deterministic synthetic workloads for experiments and benchmarks.