Matrix multiplication (hereafter referred t£ as_ MM) is a basic operation of
linear algebra, which has numerous applications to the theory and practice of compu-
computation. In particular, several important applications are due to the fact that MM
is a substantial part of several successful algorithms for other computational prob-
problems of linear algebra and combinatorics, such.as the solution of a system of linear
equations, matrix inversion, the evaluation of the determinant of a matrix, Boolean
MM, and the transitive closure of a graph. Moreover, the computational time
required for MM is the dominating part of the total computational time required for
all of those problems, that is, all such problems can be reduced to MM and can be
solved fast if MM is solved fast.