Fast multiplication of a matrix by its transpose
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.