Opened 10 years ago

Last modified 5 years ago

#12177 new enhancement

Prime slicing for matrix multiplication — at Initial Version

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:

Status badges

Description

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 sage-devel, Martin gave a couple of references:

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.

Change History (0)

Note: See TracTickets for help on using tickets.