`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.

`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.

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

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.

SpaSM can be up to 1000x faster.

Matrix | rows | columns | non-zero | Right-Looking (s) | Wiedemann (s) | GPLU (s) |
---|---|---|---|---|---|---|

Margulies/wheel_601 | 902 103 | 723 605 | 2 170 814 | 7040 | 66886 | 4 |

Homology/ch8-8.b5 | 564 480 | 376 320 | 3 386 882 | 5160 | 20944 | 6 |

Mgn/M0,6-D11 | 587 520 | 122 880 | 1 203 842 | 722 | 4865 | 0.4 |

BasisLIB/cont11_l | 58 936 | 58 936 | 179 558 | 12 | 15571 | 0.03 |

Grobner/c8_mat11 | 4 562 | 5 761 | 2 462 972 | 27 | 117 | 3 |

Smooshed/olivermatrix.2 | 78 661 | 737 004 | 1 494 560 | 75 | 3424 | 0.6 |

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.

Family | Matrix | rows | columns | non-zero | Right-looking (s) | Wiedemann (s) | Hybrid/GPLU (s) |
---|---|---|---|---|---|---|---|

GL7d | 14 | 345688 | 12347 | 1334038 | 42 | 979 | 0.1 |

Homology | mk13.b5 | 135135 | 270270 | 810810 | M.T. | 3304 | 41 |

shar_te2.b3 | 200200 | 200200 | 800800 | M.T. | 3862 | ? | |

Mgn/M0,6 | 6 | 49 800 | 291 960 | 1 066 320 | 42 | 979 | 0.1 |

7 | 294 480 | 861 930 | 4 325 040 | 2257 | 20 397 | 0.8 | |

8 | 862 290 | 1 395 840 | 8 789 040 | 20274 | 133 681 | 7.7 | |

9 | 1 395 480 | 1 274 688 | 9 568 080 | MT | 154 314 | 27.6 | |

10 | 1 270 368 | 616 320 | 5 342 400 | ??? | 67 336 | 42.7 | |

11 | 587 520 | 122 880 | 1 203 840 | 722 | 4 864 | 0.5 | |

G5 | 13 | 345688 | 12347 | 1334038 | 0.22 | vastly inferior | 0.1 |

14 | 345688 | 12347 | 1334038 | 0.52 | 0.2 | ||

15 | 345688 | 12347 | 1334038 | 1.5 | 0.5 | ||

16 | 345688 | 12347 | 1334038 | 4.2 | 1.1 | ||

17 | 345688 | 12347 | 1334038 | 10.4 | 2.7 | ||

18 | 345688 | 12347 | 1334038 | 27 | 6.2 | ||

Margulies | kneser_10_4 | 349 651 | 330 751 | 992 252 | 923 | 9449 | 0.1 |

flower_8_4 | 55 081 | 125 361 | 375 268 | 37 | 635 | 37 |

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

Matrix | rows | columns | non-zero | Wiedemann [1 core] (s) | Hybrid/dense [4 cores] (s) |
---|---|---|---|---|---|

relat8 | 345 688 | 12 347 | 1 334 038 | 244 | 2 |

relat9 | 9 746 232 | 274 667 | 38 955 420 | 176 694 | 630 |

Please contact Charles Bouillaguet if there are bugs, questions, comments.