Computing Smith Forms Modulo 2 of Sparse Matrices Faster Than Matrix Multiplication

Q: What problem does the paper solve for matrices modulo p^2?

It computes the Smith normal form multiplicities for a matrix over R = Z/p^2Z, focusing on the counts of invariant factors equal to p and 0 without constructing expensive dense structures.

Q: How is the input matrix represented when it is sparse or structured?

The matrix is accessed as a black box: for any vector x in R^n, the algorithm can compute A x using a number of ring operations proportional to the available sparsity or structure.

Q: What is the main algorithmic idea used to achieve faster complexity?

The method splits off the unit part modulo p after fast rank-profile preconditioning, reducing the remaining task to solving a Schur-complement-like system whose residue is divisible by p and can be handled via structured, sparse block techniques and Hensel lifting.

Jul 16, 2026

Upload by Levi

Computing the Smith normal form over R = Z/p^2Z, the document studies sparse or structured matrices given only through a black-box action. For a prime p, every matrix has Smith factors with three possible multiplicities, and the work focuses on determining the counts of invariant factors equal to 1, p, and 0 efficiently. A randomized Monte Carlo algorithm is presented, using block-Wiedemann-style iterations and structured preconditioners, achieving expected R-operation complexity below the best dense baseline via fast multiplication exponents.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages19

Reading Time48 min

Introduction

Smith normal form background and applications

Prior work and remaining challenge

Goal and algorithmic approach

Matrix decomposition and Schur complement strategy

Computing multiplicities via efficient solves

Computing Smith Forms Modulo 􀁰 2 of Sparse Matrices Faster Than Matrix Multiplication Mark Giesbrecht Cheriton School of Computer Science, Faculty of Mathematics, University of Waterloo, Canada [mwg@uwaterloo.ca](mwg@uwaterloo.ca) arXiv :2607 .05800v 1 [ cs . SC] 7 Jul 2026 Abstract. Let 􀀿 be a prime and R = Z/􀀿2Z the ring of integers modulo 􀀿2 . Any 􀀖 ∈ R􀀽×􀀽 is unimodularly equivalent to its Smith form 􀀨 = diag 􀀀, . . . , 1, 􀀿, . . . , 􀀿 , 0, . . . , 0􀀁 ∈ R􀀽×􀀽 , {z } | {z } | {z } 􀁁0 􀁁1 􀁁2 i.e., there exist 􀀪, 􀀫 ∈ R􀀽×􀀽 such that 􀀪 􀀖􀀫 = 􀀨, with det 􀀪, det 􀀫 ∈ R∗ (where R∗ is the set of units in R, elements not equivalent to 0 mod 􀀿) . Our goal in this paper is to determine 􀁁0, 􀁁 1, 􀁁 2 quickly when 􀀖 is sparse or structured. By “sparse” we mean 􀀖 is gi˜ ven by a black box such that for any 􀁅 ∈ R􀀽×1 we can compute 􀁅 ↦→ 􀀖􀁅 with 􀀤 (􀀽) operations in R, which captures having few nonzero elements or a multiplicative structure (e.g., Hankel or Toeplitz matrices) . We present a randomized algorithm which requires an expected number of 􀀤˜ 􀀐􀀽3−1/( 􀁬−1) 􀀑 operations in R to compute the Smith form, where 􀁬 is the exponent of dense matrix multiplication. Usin˜ g standard cubic matrix multiplication (􀁬 = 3) our algorithm thus requires 􀀤 (􀀽2.5 ) operations in R, while using the current asymptotic˜ally fastest matrix multiplication, with 􀁬 < 2. 371339, our algorithm requires 􀀤 (􀀽2.270786 ) operations in R. Our algorithm is probabilistic of the Monte Carlo type, meaning it fails on any invocation with controllably small probability. We employ iterative block-Wiedemann-style matrix techniques and structured preconditioners. To our knowledge, this is the first algorith˜m to compute the modular Smith Normal Form modulo 􀀿2 requiring fewer than 􀀤 (􀀽􀁬 ) operations in R, i.e., faster than any dense algorithm. Keywords: Smith normal form · sparse linear algebra · black-box matrices · block Wiedemann algorithm · local rings · matrix multiplication complexity 1 Introduction The Smith normal form (SNF), introduced by Smith (1861), diagonalizes matrices over Z and has applications in diophantine analysis (Chou and Collins, 1982), integer programming (Hu, 1969), combinatorics (Stanley, 2016), determining the structure of abelian To appear, Computer Algebra in Scientific Computation (CASC) conference, August 31– September 4, 2026, Bath, UK 2 M. Giesbrecht groups (Newman, 1972) and class groups (Hafner and McCurley, 1989), in control system theory (Kailath, 1980), and especially computing simplicial homology (Dumas et al., 2003) . To deal with large instances of these problems we must exploit sparsity in the matrix (see, e.g., Giusti et al. (2016) in an application to neural data) . This remains challenging. The problem of computing the Smith form of a sparse matrix over a principal ideal ring presents several challenges. The mathematics goes back to Kaplansky (1949) . One approach is to simply compute the SNF over Z and then reduce the result modulo the power of the prime ideal. The algorithm of Eberly et al. (2007) for SNF of a sparse matrix over ˜Z could be used, which reduces the cost using standard matrix arithmetic over Z to 􀀤 (􀀽2.66 ) bit operations, but does not seem directly amenable to asymptotic speedup. The best known algorithm f˜or any matrix over any Z/(􀀳), for any 􀀳 ∈ Z, is by Storjohann (1996) and requires 􀀤 (􀀽􀁬 ) operations mod 􀀳, and is not sensitive to sparsity. The “valence” algorithm of Dumas et al. (2003) uses a hybrid of a “global”method over Z and a (dense) 􀀿 -adic elimination method for selected primes 􀀿 . Our method here may be useful as a subroutine in this approach. We will address a simple but important case here to attempt to break through this barrier: integer matrices modulo 􀀿2 for a prime 􀀿 . For matrices over R = Z/􀀿2Z, there are only three possible Smith factors, and the SNF has shape 􀀨 = diag 􀀀, . . . , 1, 􀀿, . . . , 􀀿 , 0, . . . , 0􀀁 = diag 􀀀 1􀁁0 , 􀀿 􀁁1 , 0􀁁2 􀀁

FAQs

What problem does the paper solve for matrices modulo p^2?

It computes the Smith normal form multiplicities for a matrix over R = Z/p^2Z, focusing on the counts of invariant factors equal to p and 0 without constructing expensive dense structures.

How is the input matrix represented when it is sparse or structured?

The matrix is accessed as a black box: for any vector x in R^n, the algorithm can compute A x using a number of ring operations proportional to the available sparsity or structure.

What is the main algorithmic idea used to achieve faster complexity?

The method splits off the unit part modulo p after fast rank-profile preconditioning, reducing the remaining task to solving a Schur-complement-like system whose residue is divisible by p and can be handled via structured, sparse block techniques and Hensel lifting.

Jul 16, 2026

Upload by Levi