Excellence research internship, LJK
How few multiplications does a bilinear map need?
Multiplying two polynomials, or two matrices, costs a number of multiplications. That number is not fixed by the problem: choosing a different basis can lower it, and Strassen doing 2x2 matrix multiplication in seven instead of eight is the famous case. This internship searched for such decompositions over finite fields.
The two strands
Bilinear rank over finite fields
Given a bilinear map, find another that spans the same space and needs fewer multiplications. Implemented in Python and Julia over the automorphisms of the map.
Sparsifying matrices
Multiplications are not the only cost. The additions are set by how many nonzero entries the operators carry, and a change of basis can reduce those too.
What it reached
A heuristic search over alternative bases, on polynomial multiplication over finite fields.
| Map | Naive | Reached | Saved |
|---|---|---|---|
| 5x5 over GF(2) | 25 | 14 | 44% |
| four benchmark maps | 37% to 44% |
The search is a heuristic, so those are upper bounds: it says a map needs no more than that many multiplications, and it does not prove them optimal. Saying which of the two a number is turned out to be the whole of the next question.
Where the work went
The problem was picked up again independently after the internship and rewritten in C++20, this time to decide rather than to search: to prove that no smaller decomposition exists rather than to find a smaller one.
On the same 5x5 map over GF(2) that this internship took to 14 products, that work settles the rank at exactly 13, ruling out 12 by exhaustion over 146 402 553 nodes.
The code, as it was delivered
This repository holds the internship exactly as handed in: the Python and Julia implementations of both strands, and a PDF for each explaining the mathematics behind it. Nothing has been added to the work itself.