Opened 10 years ago

Last modified 5 years ago

## #12177 new enhancement

# Prime slicing for matrix multiplication — at Version 1

Reported by: | SimonKing | Owned by: | jason, was |
---|---|---|---|

Priority: | major | Milestone: | sage-feature |

Component: | linear algebra | Keywords: | prime slicing, Karatsuba |

Cc: | malb, burcin, robertwb, boothby | Merged in: | |

Authors: | Reviewers: | ||

Report Upstream: | N/A | Work issues: | |

Branch: | Commit: | ||

Dependencies: | Stopgaps: |

### Description (last modified by )

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.

**Note:**See TracTickets for help on using tickets.