# SpaSM : Sparse Solver Modulo $p$

SpaSM is a software library for sparse gaussian elimination modulo a small prime $p$. It can solve linear systems, compute the rank of sparse matrices, etc. (sometimes) much faster than anything else.

# Introduction

SpaSM is a software library devoted to sparse gaussian elimination modulo a small prime $p$. It is available under the General Public License Version 2 or later (GPLv2+). Get the code now!

It has been written by Charles Bouillaguet and Claire Delaplace to support our research on sparse gaussian elimination.

The algorithms in SpaSM are described in this paper.

# Features

The core of the library is an implementation of the GPLU algorithm, heavily inspired by CSparse, and adapted to the context of exact computation. On top of this, we designed a hybrid left-and-right looking algorithm. This allows several kind of useful operations on sparse matrices:

• LU and PLUQ factorization
• Rank computation
• Solution of linear systems
• Kernel basis
• Permutation to block triangular form
Finally, the library does I/O of matrices in SMS format, which makes it somewhat compatible with LinBox.

# Benchmarks

Here are a few data points comparing several sparse rank algorithms. SpaSM implements GPLU and a new hybrid Left-and-Right looking algorithm. LinBox implements a right-looking sparse gaussian elimination and the Wiedemann algorithm. All benchmark matrices are taken from Jean-Guillaume Dumas's Sparse Integer Matrices Collection.

This benchmark is a bit dishonest, because it does not show the cases where LinBox is actually faster :-)

Timings have been mesured on a desktop computer equipped with an Intel core i7-3770 CPU and 8GB of RAM.

#### GPLU

SpaSM can be up to 1000x faster.

Matrixrowscolumnsnon-zeroRight-Looking (s)Wiedemann (s)GPLU (s)
Margulies/wheel_601902 103723 6052 170 8147040668864
Homology/ch8-8.b5564 480376 3203 386 8825160209446
Mgn/M0,6-D11587 520122 8801 203 84272248650.4
BasisLIB/cont11_l58 93658 936179 55812155710.03
Grobner/c8_mat114 5625 7612 462 972271173
Smooshed/olivermatrix.278 661737 0041 494 5607534240.6

#### Left-Right Hybrid (GPLU finish)

A few hours before, a few seconds now. Mgn/M0,6-D9 is the 9th largest matrix of the collection. The hybrid algorithm usually compares favorably to the right-looking one.

FamilyMatrixrowscolumnsnon-zeroRight-looking (s)Wiedemann (s)Hybrid/GPLU (s)
GL7d14345688123471334038429790.1
Homology mk13.b5135135270270810810M.T.330441
shar_te2.b3200200200200800800M.T.3862?
Mgn/M0,6 649 800291 9601 066 320429790.1
7294 480861 9304 325 040225720 3970.8
8862 2901 395 8408 789 04020274133 6817.7
91 395 4801 274 6889 568 080MT154 31427.6
101 270 368616 3205 342 400???67 33642.7
11587 520122 8801 203 8407224 8640.5
G5 133456881234713340380.22vastly inferior0.1
143456881234713340380.520.2
153456881234713340381.50.5
163456881234713340384.21.1
1734568812347133403810.42.7
18345688123471334038276.2
Margulies kneser_10_4349 651330 751992 25292394490.1
flower_8_455 081125 361375 2683763537

#### Left-Right Hybrid (dense finish)

SpaSM dispatches the 3rd largest matrix of the collection in 10 minutes.

Matrixrowscolumnsnon-zeroWiedemann [1 core] (s)Hybrid/dense [4 cores] (s)
relat8345 68812 3471 334 0382442
relat99 746 232274 66738 955 420176 694630