ABSTRACT
Multiplying matrices is an important problem from both the theoretical and the practical point of view. Determining the arithmetic complexity of this problem, that is, the minimum number of arithmetic operations sufficient for computing an n × n matrix product, is still an open issue. Other important computational problems like computing the inverse of a nonsingular matrix, solving a linear system, computing the determinant, or more generally the coefficients of the characteristic polynomial of a matrix have a complexity related to that of matrix multiplication. Certain combinatorial problems, like the all pair shortest distance problem of a digraph, are strictly related to matrix multiplication. This chapter deals with fast algorithms for multiplication of unstructured matrices. Fast algorithms for structured matrix computations are presented in Chapter 48.
