Matrix Multiplication: Difference between revisions
Jump to navigation
Jump to search
| Line 4: | Line 4: | ||
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>). | 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 | One may think that a [[Algorithms#Divide_and_Conquer|divide and conquer]] recursive algorithm could help, and the obvious divide and conquer algorithm would be to divide each matrix in equal blocks and perform recursive invocations multiplying the blocks: | ||
<font size='-1'> | |||
│ A B │ │ E F │ | |||
M = │ │ N = │ │ | |||
│ C D │ │ G H │ | |||
</font> | |||
=TODO= | =TODO= | ||
Revision as of 19:36, 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 could help, and the obvious divide and conquer algorithm would be to divide each matrix in equal blocks and perform recursive invocations multiplying the blocks:
│ A B │ │ E F │
M = │ │ N = │ │
│ C D │ │ G H │
TODO
- problem statement
- naïve recursive solution
- Strassen algorithm
Overview
The asymptotic complexity is Θ(nlg7).
TODO CLRS page 75.