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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

From Disjoint to Single Matrix Multiplication

  • Jerzy S. Respondek

摘要

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.