Matrix Multiplication

From NovaOrdis Knowledge Base
Revision as of 19:31, 20 September 2021 by Ovidiu (talk | contribs)
Jump to navigation Jump to search

Internal

Overview

The obvious algorithm for matrix multiplication in case of two matrices M and N is m * n * p. For simplicity, we assume the matrices are square, with the number of rows and columns equal to n. In this case the obvious algorithm for multiplication is O(n3).

TODO

  • problem statement
  • naïve recursive solution
  • Strassen algorithm

Overview

The asymptotic complexity is Θ(nlg7).


TODO CLRS page 75.

Strassen's Algorithm for Matrix Multiplication