Matrix Multiplication: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 7: Line 7:


<font size='-1'>
<font size='-1'>
       │ A B │      │ E F │
       │ A B │      │ E F │
  M =  │     │  N =  │     │   
  M =  │     │  N =  │     │   
       │ C D │      │ G H │
       │ C D │      │ G H │
</font>
</font>
In this case final result is obtained by multiplying the blocks as follows:
<font size='-1'>
          │ AE+BG AF+BH │
M x N =  │            │ 
          │ CE+DG CF+DH │
</font>
However, applying Mater Method to infer the time complexity of the recursive multiplication algorithm for a = 8 (we invoke recursively eight times: AE, BG, AF, BH, CE, DG, CF and DH), b = 2 (we multiply matrices twice as small, each matrix of size n/2 * n/2) and the combine step complexity is O(n<sup>2</sup>) so d = 2. a/b<sub>d</sup> is 8/2<sup>2</sup> = 2, so according to the Master Method, the complexity is bounded by O(n<sup>log<sub>b</sub>a<sup>)


=TODO=
=TODO=

Revision as of 19:49, 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 │

In this case final result is obtained by multiplying the blocks as follows:

         │ AE+BG AF+BH │
M x N =  │             │  
         │ CE+DG CF+DH │

However, applying Mater Method to infer the time complexity of the recursive multiplication algorithm for a = 8 (we invoke recursively eight times: AE, BG, AF, BH, CE, DG, CF and DH), b = 2 (we multiply matrices twice as small, each matrix of size n/2 * n/2) and the combine step complexity is O(n2) so d = 2. a/bd is 8/22 = 2, so according to the Master Method, the complexity is bounded by O(nlogba)

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