Matrix Multiplication: Difference between revisions
Jump to navigation
Jump to search
m (Ovidiu moved page Strassen's Algorithm for Matrix Multiplication to Matrix Multiplication without leaving a redirect) |
No edit summary |
||
| Line 1: | Line 1: | ||
=Internal= | =Internal= | ||
* [[Algorithms#X4slMN|Algorithms | Divide and Conquer]] | * [[Algorithms#X4slMN|Algorithms | Divide and Conquer]] | ||
=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>). | |||
=TODO= | =TODO= | ||
<font color=darkkhaki> | <font color=darkkhaki> | ||
Revision as of 19:31, 20 September 2021
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.