Sparse matrix core: reusable matrix operations for PIOP (Spartan)

[wu-s-john]

Add a small, field-agnostic sparse matrix library under crates/arith.

This issue owns the reusable CSR representation and basic matrix operations required by the SHA relation in #17 and, later, the Spartan PIOP in #19. It does not own either relation or protocol.

Sources

This issue is normative for the matrix representation, operations, and arithmetic semantics.

The implementation on the sha256-constraints branch may be used as a reference:

crates/arith/src/matrix.rs

The existing codebase represents logical F_2 values as bool:

false = 0
true  = 1
addition = XOR
multiplication = AND

F128 is the extension field F_{2^128} and must not be used as a substitute for scalar F_2 values.

File layout

Keep the implementation in one source file:

crates/arith/
├── Cargo.toml
└── src/
    ├── lib.rs
    └── matrix.rs

If crates/arith has already landed through #17, extend that crate rather than creating another matrix crate.

The crate may use the workspace's existing num-traits dependency, but it must not depend on field, poly, piop, prover, or verifier crates.

CSR representation

Provide a representation equivalent to:

pub struct SparseMatrix<C> {
    pub num_rows: usize,
    pub num_cols: usize,
    pub row_offsets: Box<[u32]>,
    pub column_indices: Box<[u32]>,
    pub values: Box<[C]>,
}

Entries in row i occupy:

row_offsets[i] .. row_offsets[i + 1]

Provide checked construction from:

• raw CSR arrays
• iterators of rows containing (column, coefficient) entries

Construction and validation must enforce:

• row_offsets.len() == num_rows + 1
• the first row offset is zero
• row offsets are monotonic
• every row offset is within the nonzero arrays
• the terminal row offset equals the number of nonzeros
• column_indices.len() == values.len()
• every column index is less than num_cols
• the number of nonzeros fits the u32 offset representation

Row-entry order should be preserved. Sorting columns, combining duplicate entries, and removing explicit zero coefficients belong to relation builders.

Expose:

num_rows()
num_cols()
nnz()
validate()

Generic arithmetic

Reuse the existing Rust arithmetic traits:

use std::ops::{AddAssign, Mul};

use num_traits::Zero;

Do not introduce project-local multiplication, zero, semiring, or matrix-coefficient traits.

Matrix-vector multiplication

Provide checked multiplication for:

y = Mx

y[i] = sum_j M[i,j] * x[j].

Expose an API equivalent to:

pub fn try_multiply<Right, Output>(
    &self,
    right: &[Right],
) -> Result<Box<[Output]>, MatrixError>
where
    C: Copy + Mul<Right, Output = Output>,
    Right: Copy,
    Output: Zero + AddAssign;

The implementation must traverse CSR entries directly and run in:

O(num_rows + nnz(M))

Transpose multiplication

Provide checked operations for:

y = M^T x
output += M^T x

Expose APIs equivalent to:

pub fn try_transpose_multiply<Right, Output>(
    &self,
    right: &[Right],
) -> Result<Box<[Output]>, MatrixError>
where
    C: Copy + Mul<Right, Output = Output>,
    Right: Copy,
    Output: Zero + AddAssign;

pub fn try_transpose_accumulate<Right, Output>(
    &self,
    right: &[Right],
    output: &mut [Output],
) -> Result<(), MatrixError>
where
    C: Copy + Mul<Right, Output = Output>,
    Right: Copy,
    Output: AddAssign;

Transpose accumulation must preserve values already present in the destination.

Both operations must traverse CSR directly. A CSC representation is not required.

F_2 matrix operations

Because the codebase represents F_2 as bool, provide specialized Boolean operations:

impl SparseMatrix<bool> {
    pub fn try_multiply_bits(
        &self,
        bits: &[bool],
    ) -> Result<Box<[bool]>, MatrixError>;

    pub fn try_transpose_multiply_bits(
        &self,
        bits: &[bool],
    ) -> Result<Box<[bool]>, MatrixError>;

    pub fn try_transpose_accumulate_bits(
        &self,
        bits: &[bool],
        output: &mut [bool],
    ) -> Result<(), MatrixError>;
}

These operations use:

coefficient * value = coefficient AND value
accumulator + term  = accumulator XOR term
zero                = false

They are specialized because Rust's bool does not implement Mul, AddAssign, or num_traits::Zero.

Do not introduce a new F2 newtype as part of this issue.

Exact integer multiplication

Provide the unreduced operation required by the SHA integer relation:

A ∈ Z^(m×n)
h ∈ {0,1}^n

y[i] = sum_j A[i,j] h[j] ∈ Z.

Expose:

impl SparseMatrix<i64> {
    pub fn try_multiply_bits_exact(
        &self,
        bits: &[bool],
    ) -> Result<Box<[i128]>, MatrixError>;
}

This operation must:

• accumulate in i128
• preserve negative coefficients
• perform no field or modular reduction
• reject an incorrect bit-vector length
• replace relation-specific copies of this CSR traversal

With u32 nonzero offsets and i64 coefficients, a binary row sum has absolute value less than 2^95. A structurally valid matrix therefore cannot overflow i128. Document this bound.

This remains specialized because Rust does not provide, and this crate cannot implement, Mul<bool> for i64.

Bilinear evaluation

Provide direct sparse evaluation of:

left^T M right
    = sum_(i,j : M[i,j] != 0)
        left[i] * M[i,j] * right[j].

Expose an API equivalent to:

pub fn try_bilinear<Left, Right, Product, Output>(
    &self,
    left: &[Left],
    right: &[Right],
) -> Result<Output, MatrixError>
where
    C: Copy + Mul<Right, Output = Product>,
    Right: Copy,
    Left: Copy + Mul<Product, Output = Output>,
    Output: Zero + AddAssign;

Use the multiplication order:

left[i] * (M[i,j] * right[j]).

The implementation must run in O(nnz(M)) time without constructing M * right or allocating a dense matrix.

Constructing equality tables and interpreting the inputs as a matrix MLE evaluation belong to #19.

Errors

Use a typed MatrixError covering at least:

• incorrect row-offset count
• nonzero first row offset
• nonmonotonic row offsets
• row offsets outside the nonzero arrays
• incorrect terminal row offset
• mismatched value and column-index counts
• out-of-range column indices
• dimension overflow
• excessive nonzero count for u32 offsets
• matrix-vector input dimension mismatch
• transpose input dimension mismatch
• transpose output dimension mismatch
• bilinear left dimension mismatch
• bilinear right dimension mismatch

Checked public APIs must return errors rather than panic on malformed matrices or caller-controlled dimensions.

Expected complexity

Operation	Time	Additional space
CSR validation	O(num_rows + nnz)	O(1)
Matrix-vector multiplication	O(num_rows + nnz)	O(num_rows)
Transpose multiplication	O(num_cols + nnz)	O(num_cols)
Transpose accumulation	O(nnz)	O(1)
Bilinear evaluation	O(nnz)	O(1)
Exact binary multiplication	O(num_rows + nnz)	O(num_rows)

No production operation may allocate a dense matrix.

Out of scope

• Spartan or any other PIOP
• R1CS prover or verifier logic
• dense multilinear extensions
• equality-polynomial tables
• projection of integer coefficients into F_q
• wide accumulators or delayed field reduction
• dense, CSC, COO, or hash-map matrix representations
• a new scalar F2 type
• matrix commitments
• parallel, SIMD, or fused A/B/C kernels
• relation-specific canonicalization
• changes to poly/src/mle.rs
• changes to PRs Add PCS Crate #15 or feat(prover,verifier): the column fold #18

Validation

Done when all of the following hold:

• Valid CSR matrices round-trip through checked construction.

• Malformed offsets, mismatched arrays, and invalid columns are rejected.

• Generic forward multiplication matches an independent dense implementation.

• Boolean multiplication matches an independent AND/XOR implementation.

• Boolean transpose multiplication and accumulation use XOR semantics.

• Exact i64 × bool multiplication matches an independent i128 implementation.

• Exact multiplication covers negative coefficients and cancellation.

• Generic transpose multiplication matches an independent dense implementation.

• Transpose accumulation preserves existing destination values.

• Bilinear evaluation matches:

  • an independent dense implementation
  • dot(left, M * right)

• The adjoint identity holds on compatible randomized inputs:

  <u, Mv> = <M^T u, v>.
  

• Tests cover:

  • empty rows
  • zero-row matrices
  • zero-column matrices
  • rectangular matrices
  • all-zero matrices
  • dimension mismatches
  • duplicate column entries
  • negative integer coefficients

• Production operations traverse only CSR nonzeros.

• Production operations never allocate a dense matrix.

• No custom arithmetic traits are introduced.

• The workspace passes:

  cargo test --workspace --all-features
  cargo clippy --workspace --all-targets --all-features -- -D warnings
  cargo fmt --all --check
  

Dependencies

This issue has no dependency on the proof-system implementation issues.

It provides shared infrastructure consumed by:

• SHA-256 relation: witness synthesis and sparse M/A construction #17 for sparse SHA relation construction and exact evaluation
• Spartan PIOP: R1CS reduction and Eq-shaped F2Z handoff #19 for later R1CS matvec and sparse matrix-MLE evaluation

If matrix code is already present on the #17 implementation branch, consolidate it into this API rather than landing two representations.

Effort M.