Back to Search
Start Over
Matrix multiplication over word-size modular rings using approximate formulae
- Source :
- ACM Transactions on Mathematical Software, ACM Transactions on Mathematical Software, 2016, 42 (3-20), ⟨10.1145/2829947⟩, ACM Transactions on Mathematical Software, Association for Computing Machinery, 2016, 42 (3-20), ⟨10.1145/2829947⟩
- Publication Year :
- 2016
- Publisher :
- HAL CCSD, 2016.
-
Abstract
- Bini-Capovani-Lotti-Romani approximate formula (or border rank) for matrix multiplication achieves a better complexity than Strassen’s matrix multiplication formula. In this article, we show a novel way to use the approximate formula in the special case where the ring is Z / p Z . In addition, we show an implementation à la FFLAS--FFPACK, where p is a word-size modulo, that improves on state-of-the-art Z / p Z matrix multiplication implementations.
- Subjects :
- Discrete mathematics
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Multiplication algorithm
Ring (mathematics)
Strassen-Winograd's algorithm
Rank (linear algebra)
Applied Mathematics
Modulo
010102 general mathematics
matrix multiplication
Bini's approximate bilinear algorithm
010103 numerical & computational mathematics
01 natural sciences
Matrix multiplication
Algebra
efficient implementation
exact linear algebra
symbolic-numeric computing
Strassen algorithm
Diagonal matrix
0101 mathematics
memory placement and scheduling
Software
Coppersmith–Winograd algorithm
Mathematics
Subjects
Details
- Language :
- English
- ISSN :
- 00983500
- Database :
- OpenAIRE
- Journal :
- ACM Transactions on Mathematical Software, ACM Transactions on Mathematical Software, 2016, 42 (3-20), ⟨10.1145/2829947⟩, ACM Transactions on Mathematical Software, Association for Computing Machinery, 2016, 42 (3-20), ⟨10.1145/2829947⟩
- Accession number :
- edsair.doi.dedup.....a20b1e43de3430317d6d5c9909a20e29
- Full Text :
- https://doi.org/10.1145/2829947⟩