This chapter deals with non-commutative exact algorithms. We start with the classical Strassen algorithm and show how it can be derived. Then we look at its variations. Next, we present two generalisations of the Strassen algorithm to an arbitrary dimension. We also look at the Diophantine equation method for constructing fast matrix multiplication algorithms. We then introduce the duality notion of fast matrix multiplication algorithms and describe the general methods for constructing fast algorithms. Next, we present classical trilinear identity algorithms for even-dimensional matrices. We then introduce the reader to the notion of disjoint matrix multiplication, which allows multiplying more than one matrix product at a time with less non-commutative multiplications than required by the definition.

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

The Exact Non-commutative Algorithms

  • Jerzy S. Respondek

摘要

This chapter deals with non-commutative exact algorithms. We start with the classical Strassen algorithm and show how it can be derived. Then we look at its variations. Next, we present two generalisations of the Strassen algorithm to an arbitrary dimension. We also look at the Diophantine equation method for constructing fast matrix multiplication algorithms. We then introduce the duality notion of fast matrix multiplication algorithms and describe the general methods for constructing fast algorithms. Next, we present classical trilinear identity algorithms for even-dimensional matrices. We then introduce the reader to the notion of disjoint matrix multiplication, which allows multiplying more than one matrix product at a time with less non-commutative multiplications than required by the definition.