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:

Status badges

Description (last modified by SimonKing)

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:

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 (1)

comment:1 Changed 10 years ago by SimonKing

  • Description modified (diff)
Note: See TracTickets for help on using tickets.