From Disjoint to Single Matrix Multiplication
摘要
The chapter is devoted to the problem of how to use the disjoint algorithms, which compute several separate matrix products simultaneously, to compute a single matrix product. The chapter is divided into two parts: for disjoint algorithms working on matrices of equal dimensionality, and the second part, showing how to use algorithms working on a set of matrix products of arbitrary dimension to obtain an algorithm that calculates a single matrix product. The most general summary result is the famous tau-theorem. Finally, we use it to determine the complexity of previously presented double and triple disjoint algorithms applied to single matrix multiplication.