Matrix Multiplication: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(31 intermediate revisions by the same user not shown)
Line 1: Line 1:
=Internal=
=Internal=
* [[Algorithms#X4slMN|Algorithms | Divide and Conquer]]
* [[Recursive_Algorithms#Divide_and_Conquer|Divide and Conquer Algorithms]]
* [[Karatsuba_Multiplication#Overview|Karatsuba Multiplication]]
 
=Overview=
=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(n<sup>3</sup>).
The straightforward iterative 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. Note that while usually we use "n" to denote the input size, here we use "n" to denote the matrix dimension, so the input size in this case is O(n<sup>2</sup>). In this case the obvious algorithm for multiplication is O(n<sup>3</sup>). That matches the intuition as the straightforward iterative algorithm is a triple nested loop over n.


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:
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'>
<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>


=TODO=
In this case final result is obtained by multiplying the blocks as follows:
<font color=darkkhaki>
 
* problem statement
<font size='-1'>
* naïve recursive solution
          │ AE+BG AF+BH │
* Strassen algorithm
M x N =  │            │ 
          │ CE+DG CF+DH │
</font>
</font>


=Overview=
However, applying [[Master_Method#Overview|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 - none of the products re-occur, they are distinct), 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<sup>d</sup> is 8/2<sup>2</sup> = 2, so according to the [[Master_Method#Case_3|Case 3 of the master method]], the complexity is bounded by O(n<sup>log<sub>b</sub>a</sup>) = O(n<sup>3</sup>), the same as the straightforward iterative method.
 
An improvement to this upper bound is provided by the [[#Strassen|Strassen method]], which cleverly proposes only 7 recursive calls.
 
=<span id='Strassen'></span>Strassen's Algorithm for Matrix Multiplication=
 
The Strassen algorithm recursively computes the products of smaller (n/2) matrices, but it'll only be 7 of them:
 
P<sub>1</sub>=A(F-H), P<sub>2</sub>=(A+B)H, P<sub>3</sub>=(C+D)E, P<sub>4</sub>=D(G-E), P<sub>5</sub>=(A+D)(E+H), P<sub>6</sub>=(B-D)(G+H), P<sub>7</sub>=(A-C)(E+F).


The asymptotic complexity is Θ(n<sup>lg7</sup>).
In the combine phase, it'll combine the results of the recursive calls, using only addition and subtraction (O(n<sup>2</sup>)):


<font size='-1'>
          │ AE+BG AF+BH │    │ P<sub>5</sub>+P<sub>4</sub>-P<sub>2</sub>+P<sub>6</sub>  P<sub>1</sub>+P<sub>2</sub>      │
M x N =  │            │  =  │                          │
          │ CE+DG CF+DH │    │ P<sub>3</sub>+P<sub>4</sub>        P<sub>1</sub>+P<sub>5</sub>-P<sub>3</sub>-P<sub>7</sub> │     
</font>
This is the same type of optimization applied in the case of [[Karatsuba_Multiplication#Overview|Karatsuba integer multiplication algorithm]].


<font color=darkgray>TODO [[CLRS]] page 75.</font>
More details on Strassen multiplication in [[CLRS]], page 75.
==Strassen's Algorithm Time Complexity==
Applying the Master Method for a = 7 (7 sub-problems), b = 2 (the size of the subproblem is half of the size of the initial problem) and the combine phase complexity is O(n<sup>2</sup>) so d = 2, a/b<sup>d</sup> is bigger then 1, so according to the [[Master_Method#Case_3|Case 3 of the master method]], the asymptotic complexity is Θ(n<sup>log<sub>2</sub>7</sup>) = Θ(n<sup>log7</sup>).


=<span id='Strassen'></span>Strassen's Algorithm for Matrix Multiplication=
The key insight was to find a way to reduce the number of recursive calls, in the same way [[Karatsuba_Multiplication|Karatsuba method]] of multiplying to n-size integers takes advantage of Gauss' trick to perform only 3 recursive calls instead of 4.

Latest revision as of 19:12, 9 November 2021

Internal

Overview

The straightforward iterative 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. Note that while usually we use "n" to denote the input size, here we use "n" to denote the matrix dimension, so the input size in this case is O(n2). In this case the obvious algorithm for multiplication is O(n3). That matches the intuition as the straightforward iterative algorithm is a triple nested loop over n.

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 - none of the products re-occur, they are distinct), 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 Case 3 of the master method, the complexity is bounded by O(nlogba) = O(n3), the same as the straightforward iterative method.

An improvement to this upper bound is provided by the Strassen method, which cleverly proposes only 7 recursive calls.

Strassen's Algorithm for Matrix Multiplication

The Strassen algorithm recursively computes the products of smaller (n/2) matrices, but it'll only be 7 of them:

P1=A(F-H), P2=(A+B)H, P3=(C+D)E, P4=D(G-E), P5=(A+D)(E+H), P6=(B-D)(G+H), P7=(A-C)(E+F).

In the combine phase, it'll combine the results of the recursive calls, using only addition and subtraction (O(n2)):

         │ AE+BG AF+BH │     │ P5+P4-P2+P6   P1+P2       │
M x N =  │             │  =  │                          │ 
         │ CE+DG CF+DH │     │ P3+P4         P1+P5-P3-P7

This is the same type of optimization applied in the case of Karatsuba integer multiplication algorithm.

More details on Strassen multiplication in CLRS, page 75.

Strassen's Algorithm Time Complexity

Applying the Master Method for a = 7 (7 sub-problems), b = 2 (the size of the subproblem is half of the size of the initial problem) and the combine phase complexity is O(n2) so d = 2, a/bd is bigger then 1, so according to the Case 3 of the master method, the asymptotic complexity is Θ(nlog27) = Θ(nlog7).

The key insight was to find a way to reduce the number of recursive calls, in the same way Karatsuba method of multiplying to n-size integers takes advantage of Gauss' trick to perform only 3 recursive calls instead of 4.