The Exact Non-commutative Algorithms
摘要
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.