Ticket #12177 (new enhancement)
Prime slicing for matrix multiplication
|Reported by:||SimonKing||Owned by:||jason, was|
|Component:||linear algebra||Keywords:||prime slicing, Karatsuba|
|Cc:||malb, burcin, robertwb, boothby||Work issues:|
Description (last modified by malb) (diff)
In Sage, matrix arithmetic over finite fields is fast in the following cases:
In all other cases, it sucks. There is the suggestion to use a wrapper of a fork of C-MeatAxe (#12103), but this would only work up to field size 255 and might have further disadvantages.
Martin Albrecht suggested to use "prime slicing" instead:
- Represent matrices over GF(p^n) by a list of n matrices over GF(p) (with Linbox as backend)
- Matrix multiplication over GF(p^n) is implemented by a series of multiplications over GF(p)
- Karatsuba type formulae reduce the number of "prime" multiplications involved.
On sage-devel, Martin gave a couple of references:
- Boothby and Bradshaw Bitslicing and the Method of Four Russians Over Larger Finite Fields
- Montgomery Five, Six, and Seven-Term Karatsuba-Like Formulae
On another occasion, Martin also pointed out how to compute echelon forms in that setting.
The purpose of this ticket is to make that idea real.
- addition, subtraction (easy)
- scalar multiplication (medium)
- row swaps, column swaps (easy)
- C = C + A*B (easy)
- fast randomize (for testing, easy)
- apply LAPACK permutations (easy)
- matrix windows (cheap submatrices, arder)
- TRSM lower left / TRSM upper left (medium)
- PLE (medium)
- Karatsuba-like for up to degree 10 (harder)
- Milestone changed from sage-4.8 to sage-feature