Paper Info
Title
On fast multiplication of a matrix by its transpose
Abstract
We present a non-commutative algorithm for the multiplication of a 2 × 2-block-matrix by its transpose using 5 block products (3 recursive calls and 2 general products) over C or any field of prime characteristic. We use geometric considerations on the space of bilinear forms describing 2 × 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 schedules with low memory footprint that support a fast and memory efficient practical implementation over a prime field. To conclude, we show how to use our result in L · D · LT factorization.
Year
DOI
Venue
2020
10.1145/3373207.3404021
ISSAC '20: International Symposium on Symbolic and Algebraic Computation Kalamata Greece July, 2020
DocType
ISBN
Citations 
Conference
978-1-4503-7100-1
0
PageRank 
References 
Authors
0.34
0
3
Name
Order
Citations
PageRank
Jean-Guillaume Dumas142868.48
Clément Pernet224339.00
Sedoglavic Alexandre300.34