Matrix Multiplication Over Word-Size Modular Rings Using Approximate Formulas | Zendy

Brice Boyer | Zendy; JeanGuillaume Dumas | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Matrix Multiplication Over Word-Size Modular Rings Using Approximate Formulas

Author(s) -

Brice Boyer,

JeanGuillaume Dumas

Publication year - 2016

Publication title -

acm transactions on mathematical software

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.767

H-Index - 87

eISSN - 1557-7295

pISSN - 0098-3500

DOI - 10.1145/2829947

Subject(s) - strassen algorithm , matrix multiplication , modulo , mathematics , multiplication algorithm , multiplication (music) , rank (graph theory) , matrix (chemical analysis) , word (group theory) , arithmetic , combinatorics , discrete mathematics , algebra over a field , pure mathematics , binary number , physics , geometry , materials science , quantum mechanics , composite material , quantum

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/pZ. In addition, we show an implementation à la FFLAS--FFPACK, where p is a word-size modulo, that improves on state-of-the-art Z/pZ matrix multiplication implementations.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research