Matrix Multiplication

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

Internal

Overview

The obvious algorithm for matrix multiplication in case of two matrices M (mxn) and N (nxp) 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).

One may think that a divide and conquer recursive algorithm may help

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