Fast multiplication of a matrix by its transpose

English

Séminaire AMAC: CASC

16/01/2020 - 09:30 Jean-Guillaume Dumas (LJK)

We present a non-commutative algorithm for the multiplication of a
${{2}\\times{2}}$-block-matrix by its transpose over~$\\mathbb{C}$ or
any finite field using~$5$ block products ($3$ recursive calls and $2$
non-symmetric products).
We use geometric considerations on the space of bilinear forms
describing~${{2}\\times{2}}$ matrix products to obtain this algorithm
and we show how to reduce the number of involved additions.
The resulting algorithm for arbitrary dimensions is a reduction of
multiplication of a matrix by its transpose to general matrix product,
improving by a constant factor previously known reductions.
Finally we propose space efficient schedules that enable us to provide
a fast and memory efficient practical implementation for this
operation over a finite field.