id summary reporter owner description type status priority milestone component resolution keywords cc merged author reviewer upstream work_issues branch commit dependencies stopgaps
12177 Prime slicing for matrix multiplication SimonKing jason was "In Sage, matrix arithmetic over finite fields is fast in the following cases:
* Prime fields, using linbox (#4260) resp. `M4RI` over `GF(2)`
* `GF(2^e)`, using `M4RIE` (#9562)
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 [http://groups.google.com/group/sage-devel/browse_thread/thread/8a988a2f5d997a5a/ebcde393f8ef5240 sage-devel], Martin gave a couple of references:
* [http://www.google.com/url?sa=D&q=http://arxiv.org/abs/0901.1413&usg=AFQjCNFg5cUrXjBTqkon1V6n4Yl_CVQ9yA Boothby and Bradshaw] Bitslicing and the Method of Four Russians Over Larger Finite Fields
* [http://bit.ly/r5PVgv 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.
'''TODO'''
* 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)" enhancement new major sage-feature linear algebra prime slicing, Karatsuba malb burcin robertwb boothby N/A