Affordable Access

Access to the full text

On fast multiplication of a matrix by its transpose

Authors
  • Dumas, Jean-Guillaume
  • Pernet, Clement
  • Sedoglavic, Alexandre
Type
Preprint
Publication Date
Jun 19, 2020
Submission Date
Jan 13, 2020
Identifiers
DOI: 10.1145/3373207.3404021
Source
arXiv
License
Yellow
External links

Abstract

We present a non-commutative algorithm for the multiplication of a 2x2-block-matrix by its transpose using 5 block products (3 recursive calls and 2 general products) over C or any finite field.We use geometric considerations on the space of bilinear forms describing 2x2 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 schedules with low memory footprint that support a fast and memory efficient practical implementation over a finite field.To conclude, we show how to use our result in LDLT factorization.

Report this publication

Statistics

Seen <100 times