Faster matrix multiplication
A study to finding bounds on the rank of matrix multiplication tensors
O.M. de Heer (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Dion Gijswijt – Mentor (TU Delft - Discrete Mathematics and Optimization)
WTM Caspers – Graduation committee member (TU Delft - Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Matrix multiplication with the standard
algorithm has an algebraic complexity of O(n^3) for n x n matrices, but in 1969
Strassen found another algorithm for multiplying 2 x 2 matrices with which he
showed that matrix multiplication can be done with a complexity of O(n^2.81) by
applying his algorithm recursively for large matrices. We present a historical
overview of the best known bounds on the matrix multiplication exponent, with
the current best known bound of 2.371866 and methods, used to find new
algorithms for other matrix multiplications, such as alternating least squares
(ALS) and SAT solving. After this we present a novel method with which we found
a rank 23 decomposition of the <3,3,3> matrix multiplication tensor that
may be inequivalent to known decompositions. We also found decompositions for
<2,2,2>, <2,2,3>, <2,2,4>, <2,3,3> and <2,2,5>
that provide the same bounds as earlier found decompositions. Our method found
many decompositions for the smaller tensors but only one for the larger due to
time limits. The method is based on the alternating least squares method (ALS)
with the modification that we 'push' the coefficients towards integer (or
rational) numbers. After a number of iterations and rounding the result this
sometimes yields exact decompositions so that we can bound the matrix
multiplication exponent.