Class Description

MM: Problems reducible to matrix multiplication

The set of all problems reducible to matrix multiplication. That is, the set of problems ${\displaystyle P}$ that can be reduced to the multiplication of two square matrices can be reduced to ${\displaystyle P}$ in linear time.

Currently, the best known algorithm for multiplying two ${\displaystyle n\times n}$ matrices is the Coppersmith–Winograd_algorithm, which has a time complexity of ${\displaystyle O(n^{2.376})}$ [CW90]. Note that for the general problem, a lower bound of ${\displaystyle \Omega (n^{2})}$ is trivial from the number of elements being considered.

Linked From

No class.