LJKA.M.A.C: CASC Seminar

On Thursday January 16 2020 at 9h30 in waiting for a room

Seminary of JeanGuillaume DUMAS (LJK)

Fast multiplication of a matrix by its transpose

Summary

We present a noncommutative algorithm for the multiplication of a
${{2}\\times{2}}$blockmatrix by its transpose over~$\\mathbb{C}$ or
any finite field using~$5$ block products ($3$ recursive calls and $2$
nonsymmetric 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.
