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
- Rank
- (Reduced) Row Echelon Form of
A*Q, for some permutation matrix Q
In addition, SpaSM is capable of computing a full PLUQ factorization, but this is slower and requires more memory than simple echelonization. This enables:
- Solution of linear systems
- Extraction of a square submatrix of maximal rank
- Production of rank certificates
SpaSM works with all odd 32-bit prime moduli. While it would be possible to work with p = 2, this would require non-trivial tweaks to the code.
Finally, 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
- Dense linear algebra mod p
- Linear-size rank certificates
Initial versions of SpaSM were heavily influence by Tim Davis's CSparse.
Spasm does I/O of matrices in either the :
- SMS format --- which makes it somewhat compatible with LinBox.
- MatrixMarket format, with kind
matrix coordinate integer general. (The actual input format is autodetected).
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 and pkg-config. The executables can be found in build/tools.
SpaSM relies on two third-party libraries, which are required at compile-time:
Under Debian linux or ubuntu, installing the fflas-ffpack package is sufficient to compile.
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 https://hpac.imag.fr/Matrices/Margulies/kneser_10_4_1.sms.gz | gunzip - | ./rank
curl https://hpac.imag.fr/Matrices/Homology/mk13.b5.135135x270270.sms.gz | gunzip - | ./rank
curl https://hpac.imag.fr/Matrices/G5/IG5-17.sms.gz | gunzip - | ./rank
It would be necessary to disable greedy pivot search for this one:
curl https://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 https://hpac.imag.fr/Matrices/Relat/relat8.sms.gz | gunzip - | ./stack | ./rank
curl https://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 https://hpac.imag.fr/Matrices/GL7d/GL7d14.sms.gz | gunzip - | ./vertical_swap | ./rank --dense-threshold 0.01
...
curl https://hpac.imag.fr/Matrices/GL7d/GL7d22.sms.gz | gunzip - | ./vertical_swap | ./rank --dense-threshold 0.01
Sparse Gaussian elimination is more an art than a science. In some cases, it will inevitably fail (the matrix will fill and the process will grind to a halt).
However, with some expertise, it may be possible to deal with potentially larger problems than what the auto-pilot is capable of. Don't hesitate to get in touch.
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 = {Charles Bouillaguet},
edition = {v1.3},
year = {2023},
note = {\url{http://github.com/cbouilla/spasm}}
}
Please email charles.bouillaguet@lip6.fr for any questions.