Algorithm 4.2, which defines the operation of matrix multiplication for square matrices, is clearly . Since there are many algorithms that use matrix multiplication, often on relatively large matrices, this can have a serious effect on the speed of the programs that use these algorithms. For this reason, many algorithms that use matrix multiplication use various tricks which take advantage of some particular attribute of the specific matrices used by that algorithm. (We'll see an example of one such trick in section 4.4.)
However, for many years it was assumed that general matrix
multiplication was an intrinsically operation, so despite
the benefits that a faster general multiplication algorithm would
have, there was not a lot of research dedicated to finding one.
However, in 1969 Strassen discovered an
algorithm
. This may seem like a small
improvement (and in fact, it does not really translate into real
savings unless the matrices are large), but it was an astonishing
result that spurred a great deal of research in this area. To the
best of my knowledge, however, nobody has yet proven what the big-O of
the fastest possible general matrix multiplication algorithm
is.
Perhaps there are some useful and theoretically important
discoveries still to be made.