SpaSM is a software library devoted to sparse gaussian elimination modulo a small prime p. It is available under the General Public License Version 3 or later (GPLv3+).

This is "research-quality" software. While we try to make sure that it actually works, we cannot make any promises.

The core of the library is a multithreaded function that computes the row echelon form of a sparse matrix modulo a word-sized prime. This enables several of useful computations on sparse matrices modulo p:

• Basis of the row space
• Basis of the kernel
• Reduced Row Echelon form
• Rank

In addition, SpaSM contains code to compute the Dulmage-Mendelson decomposition (permutation of a matrice to block triangular form) and several other useful functions.

The following algorithms algorithms are used in SpaSM:

• Gilbert-Peierls sparse triangular solving with sparse right-hand side
• Faugère-Lachartre pivot selection
• Improved greedy pivot selection.

Initial versions of SpaSM were heavily influence by Tim Davis's CSparse.

Spasm does I/O of matrices in SMS format, which makes it somewhat compatible with LinBox. It is also capable of reading the MatrixMarket format, which is arguably better.

A set of demonstration programs is provided (see the tools/ folder). They can be used to compute the rank, the RREF, a kernel basis, or a Dumlage-Mendelson decomposition of a sparse matrix.

In brief: make

This requires cmake. The executables can be found in build/tools.

SpaSM relies on two third-party libraries, which are required at compile-time:

• Givaro
• FFLAS-FFPACK

SpaSM uses OpenMP to exploit multicore machines.

All SpaSM demonstration scripts read a matrix in SMS format on the standard input.

For instance, these commands (run inside the build/tools/ folder) will compute the rank of several large matrices in a few seconds:

curl http://hpac.imag.fr/Matrices/Margulies/kneser_10_4_1.sms.gz | gunzip - | ./rank
curl http://hpac.imag.fr/Matrices/Homology/mk13.b5.135135x270270.sms.gz | gunzip - | ./rank
curl http://hpac.imag.fr/Matrices/G5/IG5-17.sms.gz | gunzip - | ./rank

It would be necessary to disable greedy pivot search for this one:

curl http://hpac.imag.fr/Matrices/Mgn/M0,6.data/M0,6-D9.sms.gz | gunzip - | ./rank

When matrices have many empty rows/columns, they can/have to be removed with the stack utility:

curl http://hpac.imag.fr/Matrices/Relat/relat8.sms.gz | gunzip - | ./stack | ./rank
curl http://hpac.imag.fr/Matrices/Relat/relat9.sms.gz | gunzip - | ./stack | ./rank

Finding good pivots is crucial for the performance of any kind of sparse elimination procedure. The pivot-finding code is still a bit naïve. Sometimes it will find much more pivots, much faster, if the matrices are flipped around a vertical axis with the vertical_swap utility:

curl http://hpac.imag.fr/Matrices/GL7d/GL7d14.sms.gz | gunzip - | ./vertical_swap | ./rank --sparse-threshold 0.01
...
curl http://hpac.imag.fr/Matrices/GL7d/GL7d22.sms.gz | gunzip - | ./vertical_swap | ./rank --sparse-threshold 0.01

If by any luck your research depends on the SpaSM library, please consider citing the project as

@manual{spasm,
title = {{SpaSM}: a Sparse direct Solver Modulo $p$},
author = {The SpaSM group},
edition = {v1.3},
year = {2023},
note = {\url{http://github.com/cbouilla/spasm}}
}

Please email charles.bouillaguet@lip6.fr for any questions.