How to multiply matrices faster (Q799337)

The monograph, consisting of fourty minimally interconnected sections, is divided into three main parts. Part 1 describes historically all major asymptotically fast algorithms used for \(n\times n\) matrix multiplication (MM): Strassen's algorithm, bilinear algorithms, trilinear aggregating, APA-algorithms (any precision approximation algorithms denoted as \(\lambda\) -algorithms), disjoint MM. Asymptotically fast algorithms for MM with exponent 2.496 are derived. Part 2 presents the reduction of the solution of some combinatorial and algebraic problems to MM and their consequent acceleration employing bit-time and bit-space concepts. The Boolean MM, the all pair shortest distance problem on a digraph, the solution of a system of linear equations, matrix inversion, the evaluation of the determinant of a matrix are considered. Bit-time and bit-space estimates, a close relation of bit-time and bit-space to the values of condition numbers together with their estimates are derived. A bit-complexity classification is given. Part 3 deals with bilinear algorithms and \(\lambda\) -algorithms of the currently least ranks and \(\lambda\) -ranks, commutative quadratic algorithms, general arithmetical algorithms and \(\lambda\) -algorithms for \(n\times n\) MM for small and moderate n. Some well-known linear lower bounds on the complexity of algorithms of different classes are derived. New extension of the class of arithmetical \(\lambda\) -algorithms for the evaluation of a set of rational expressions is considered. The book is an essentially self- contained and clearly written high level research exposition covering mostly the progress in MM since 1978 which has not been covered in such extent in other books up-to-date.