Matrix Multiplication: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| Line 2: | Line 2: | ||
* [[Algorithms#X4slMN|Algorithms | Divide and Conquer]] | * [[Algorithms#X4slMN|Algorithms | Divide and Conquer]] | ||
=Overview= | =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(n<sup>3</sup>). | 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(n<sup>3</sup>). | ||
One may think that a divide and conquer recursive algorithm may help | |||
=TODO= | =TODO= | ||
<font color=darkkhaki> | <font color=darkkhaki> | ||
Revision as of 19:32, 20 September 2021
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.