Skip to Main content Skip to Navigation
Conference papers

The M4RIE library for dense linear algebra over small fields with even characteristic

Martin R. Albrecht 1
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In this work, we present the M4RIE library which implements efficient algorithms for linear algebra with dense matrices over GF(2^e) for 2 <= 2 <= 10. As the name of the library indicates, it makes heavy use of the M4RI library both directly (i.e., by calling it) and indirectly (i.e., by using its concepts). We provide an open-source GPLv2+ C library for efficient linear algebra over GF(2^e) for e small. In this library we implemented an idea due to Bradshaw and Boothby which reduces matrix multiplication over GF(p^k) to a series of matrix multiplications over GF(p). Furthermore, we propose a caching technique - Newton-John tables - to avoid finite field multiplications which is inspired by Kronrod's method ("M4RM") for matrix multiplication over GF(2). Using these two techniques we provide asymptotically fast triangular solving with matrices (TRSM) and PLE-based Gaussian elimination. As a result, we are able to significantly improve upon the state of the art in dense linear algebra over GF(2^e) with 2 <= e <= 10.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/hal-01113282
Contributor : Martin Albrecht <>
Submitted on : Thursday, February 5, 2015 - 11:21:43 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Wednesday, May 6, 2015 - 10:11:33 AM

File

m4rie-paper.pdf
Files produced by the author(s)

Licence


Copyright

Identifiers

Citation

Martin R. Albrecht. The M4RIE library for dense linear algebra over small fields with even characteristic. ISSAC '12: Proceedings of the 2012 international symposium on Symbolic and algebraic computation, Jul 2012, Grenoble, France. pp.28 - 34, ⟨10.1145/2442829.2442838⟩. ⟨hal-01113282⟩

Share

Metrics

Record views

307

Files downloads

433