|
|
(9 intermediate revisions by the same user not shown) |
Line 1: |
Line 1: |
− | '''Strassen algorithm for a symmetric matrix:'''
| + | === Theorem for the Strassen algorithm === |
| + | Computing the [[w:Matrix multiplication|<span class="wikipedia">matrix product</span>]] <math>AA^T</math> shortens the original [[w:Execution_(computing)#Runtime|<span class="wikipedia">runtime</span>]] <math>T(n) = \mathcal{O}(n^{(_2 7)})</math> of the [[w:Strassen algorithm|<span class="wikipedia">Strassen algorithm</span>]] roughly by <math>\tilde{3}</math> for sufficiently big <math>n := 2^k, k \in \mathbb{N}^*</math> and the [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> due to the [[w:geometric series|<span class="wikipedia">geometric series</span>]] and |
| | | |
− | For a [[w:Symmetric matrix|<span class="wikipedia">symmetric matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where <math>2^k := n, k \in \mathbb{N}^*</math>, the [[w:Runtime (program lifecycle phase)|<span class="wikipedia">runtime</span>]] <math>T_s(n)</math> of the [[w:Strassen algorithm|<span class="wikipedia">Strassen algorithm</span>]] for the [[w:Matrix multiplication|<span class="wikipedia">matrix product</span>]] <math>A^2</math> is about half that of the original algorithm in <math>\mathcal{O}(n^{(_2 7)})</math>.
| + | <div style="text-align:center;"><math>A := |
− | | |
− | '''Proof:''' For <math>A :=
| |
− | \begin{pmatrix}
| |
− | A_{11} & A_{12} \\
| |
− | A_{12}^T & A_{22}
| |
− | \end{pmatrix}</math>, it holds that <math>A^TA =
| |
− | \begin{pmatrix}
| |
− | A_{11}A_{11}+A_{12}A_{12}^T & A_{11}A_{12}+A_{12}A_{22} \\
| |
− | A_{12}^TA_{11}+A_{22}A_{12}^T & A_{12}^TA_{12}+A_{22}A_{22}
| |
− | \end{pmatrix}</math> and <math>T_s(2n) = 3T_s(n) + 2n^{(_2 7)}</math>. Thus <math>T_s(n) = 3T_s(n/2) + 2(n/2)^{(_2 7)}</math> and <math>T_s(n/2) = 3T_s(n/4) + 2(n/4)^{(_2 7)}</math>.
| |
− | | |
− | The [[w:Geometric series|<span class="wikipedia">geometric series</span>]] yields because of <math>T_s(1) = 1</math>: <math>T_s(n) = 27T_s(n/8) + 2/7n^{(_2 7)}(1+3/7 + (3/7)^2 + ...) = 3^{(_2n)} + 2/7n^{(_2 7)} (1-(3/7)^{(_2n)})/(1-3/7)</math> <math>= n^{(_2 3)} + \hat{2}(n^{(_2 7)}-n^{(_2 3)}) = \hat{2} (n^{(_2 3)} + n^{(_2 7)})</math>.<math>\square</math>
| |
− | | |
− | '''Strassen algorithm for a square matrix:'''
| |
− | | |
− | For a square [[w:Matrix (mathematics)|<span class="wikipedia">matrix</span>]] <math>A \in \mathbb{C}^{n \times n}</math> where <math>2^k := n, k \in \mathbb{N}^*</math>, the runtime <math>T_q(n)</math> of the Strassen algorithm is for the matrix product <math>A^TA</math> about <math>4/7</math> that of the original algorithm in <math>\mathcal{O}(n^{(_2 7)})</math>.
| |
− | | |
− | '''Proof:''' For <math>A :=
| |
| \begin{pmatrix} | | \begin{pmatrix} |
| A_{11} & A_{12} \\ | | A_{11} & A_{12} \\ |
| A_{21} & A_{22} | | A_{21} & A_{22} |
− | \end{pmatrix}</math>, it holds that <math>A^TA = | + | \end{pmatrix}</math> as well as <math>AA^T = |
− | \begin{pmatrix}
| |
− | A_{11}^TA_{11}+A_{21}^TA_{21} & A_{11}^TA_{12}+A_{21}^TA_{22} \\
| |
− | A_{12}^TA_{11}+A_{22}^TA_{21} & A_{12}^TA_{12}+A_{22}^TA_{22}
| |
− | \end{pmatrix}</math> such that <math>T_q(2n) = 4T_s(n) + 2n^{(_2 7)}</math> and <math>T_q(n) = 4T_s(n/2) + 2/7n^{(_2 7)} = 2/3n^{(_2 3)} + 4/7n^{(_2 7)}</math>.<math>\square</math>
| |
− | | |
− | '''Theorem (decomposition method):'''
| |
− | | |
− | For <math>A, B, D, E \in \mathbb{C}^{n \times n}</math> where <math>2^k := n, k \in \mathbb{N}^*</math>, the runtime is <math>T_z(n) = \mathcal{O}(n^{(2^6)})</math> for the matrix product <math>QR</math> if <math>A</math> has also the following form of <math>B</math>:
| |
− | | |
− | '''Proof:''' For <math>B :=
| |
− | \begin{pmatrix}
| |
− | B_{11} & B_{12} \\
| |
− | B_{12} & B_{22}
| |
− | \end{pmatrix}</math>, it holds that <math>AB =
| |
− | \begin{pmatrix}
| |
− | A_{11}B_{11}+A_{12}B_{12} & A_{11}B_{12}+A_{12}B_{22} \\
| |
− | A_{12}B_{11}+A_{22}B_{12} & A_{12}B_{12}+A_{22}B_{22}
| |
− | \end{pmatrix} =: C</math>. Putting
| |
− | | |
− | : <math>M_{1} := A_{12} \cdot (B_{11} + B_{12})</math>
| |
− | : <math>M_{2} := A_{12} \cdot (B_{12} + B_{22})</math>
| |
− | : <math>M_{3} := A_{22} \cdot (B_{12} + B_{22})</math>
| |
− | : <math>M_{4} := (A_{11} - A_{12})\cdot B_{11}</math>
| |
− | : <math>M_{5} := (A_{11} - A_{12})\cdot B_{12}</math>
| |
− | : <math>M_{6} := (A_{12} - A_{22})\cdot B_{22}</math>
| |
− | | |
− | implies
| |
− | | |
− | : <math>C_{11} = M_{1} + M_{4}</math>
| |
− | : <math>C_{12} = M_{2} + M_{5}</math>
| |
− | : <math>C_{21} = M_{1} - C_{22} + M_{3}</math>
| |
− | : <math>C_{22} = M_{2} - M_{6} .</math>
| |
− | | |
− | Let <math>D</math> have the following form of <math>E</math>:
| |
− | | |
− | For <math>E :=
| |
− | \begin{pmatrix}
| |
− | E_{11} & E_{12} \\
| |
− | E_{21} & E_{11}
| |
− | \end{pmatrix}</math>, it holds that <math>DE =
| |
− | \begin{pmatrix}
| |
− | D_{11}E_{11}+D_{12}E_{21} & D_{11}E_{12}+D_{12}E_{11} \\
| |
− | D_{21}E_{11}+D_{11}E_{21} & D_{21}E_{12}+D_{11}E_{11}
| |
− | \end{pmatrix} =: F</math>. Putting
| |
− | | |
− | : <math>N_{1} := D_{11} \cdot (E_{11} + E_{12})</math>
| |
− | : <math>N_{2} := D_{21} \cdot (E_{11} + E_{12})</math>
| |
− | : <math>N_{3} := D_{12} \cdot (E_{11} - E_{21})</math>
| |
− | : <math>N_{4} := (D_{11} - D_{12})\cdot E_{11}</math>
| |
− | : <math>N_{5} := (D_{11} - D_{21})\cdot E_{11}</math>
| |
− | : <math>N_{6} := (D_{11} + D_{12})\cdot E_{21}</math>
| |
− | | |
− | implies
| |
− | | |
− | : <math>F_{11} = N_{3} + N_{4}</math>
| |
− | : <math>F_{12} = N_{1} - N_{4}</math>
| |
− | : <math>F_{21} = F_{11} - N_{5} + N_{6}</math>
| |
− | : <math>F_{22} = N_{2} + N_{5} .</math>
| |
− | | |
− | Then it holds for <math>D</math> and <math>B</math>:
| |
− | | |
− | <math>DB =
| |
− | \begin{pmatrix}
| |
− | D_{11}B_{11}+D_{12}B_{12} & D_{11}B_{12}+D_{12}B_{22} \\
| |
− | D_{21}B_{11}+D_{11}B_{12} & D_{21}B_{12}+D_{11}B_{22}
| |
− | \end{pmatrix} =: G</math>. Putting
| |
− | | |
− | : <math>O_{1} := D_{12} \cdot (B_{12} + B_{22})</math>
| |
− | : <math>O_{2} := D_{11} \cdot (B_{12} + B_{22})</math>
| |
− | : <math>O_{3} := D_{21} \cdot (B_{11} + B_{12})</math>
| |
− | : <math>O_{4} := (D_{11} - D_{12})\cdot B_{22}</math>
| |
− | : <math>O_{5} := (D_{11} - D_{21})\cdot B_{12}</math>
| |
− | : <math>O_{6} := (D_{11} - D_{21})\cdot B_{11}</math>
| |
− | | |
− | implies
| |
− | | |
− | : <math>G_{11} = O_{1} - G_{12} + G_{21} + O_{6}</math>
| |
− | : <math>G_{12} = O_{2} - O_{4}</math>
| |
− | : <math>G_{21} = O_{3} + O_{5}</math>
| |
− | : <math>G_{22} = O_{2} - O_{5} .</math>
| |
− | | |
− | Then it holds for <math>A</math> and <math>E</math>:
| |
− | | |
− | <math>AE =
| |
| \begin{pmatrix} | | \begin{pmatrix} |
− | A_{11}E_{11}+A_{12}E_{21} & A_{11}E_{12}+A_{12}E_{11} \\ | + | A_{11}A_{11}^T+A_{12}A_{12}^T & A_{11}A_{21}^T+A_{12}A_{22}^T \\ |
− | A_{12}E_{11}+A_{22}E_{21} & A_{12}E_{12}+A_{22}E_{11} | + | A_{21}A_{11}^T+A_{22}A_{12}^T & A_{21}A_{21}^T+A_{22}A_{22}^T |
− | \end{pmatrix} =: H</math>. Putting
| + | \end{pmatrix}.\square</math></div> |
− | | |
− | : <math>P_{1} := A_{12} \cdot (E_{11} - E_{21})</math>
| |
− | : <math>P_{2} := A_{11} \cdot (E_{11} - E_{12})</math>
| |
− | : <math>P_{3} := A_{22} \cdot (E_{11} - E_{21})</math>
| |
− | : <math>P_{4} := (A_{11} + A_{12})\cdot E_{11}</math>
| |
− | : <math>P_{5} := (A_{11} + A_{12})\cdot E_{12}</math>
| |
− | : <math>P_{6} := (A_{12} + A_{22})\cdot E_{21}</math>
| |
− | | |
− | implies
| |
− | | |
− | : <math>H_{11} = P_{4} - P_{1}</math>
| |
− | : <math>H_{12} = P_{4} - P_{2}</math>
| |
− | : <math>H_{21} = P_{1} + P_{6}</math>
| |
− | : <math>H_{22} = H_{21} - H_{12} + P_{3} + P_{5} .</math>
| |
− | | |
− | Since <math>QR</math> may be decomposed as follows, the claim is true:
| |
| | | |
− | : <math>QR=\left(\left(\begin{matrix}Q_{11}&Q_{12}\\Q_{21}&Q_{11}\\\end{matrix}\right)-\left(\begin{matrix}0&0\\0&{Q_{11}-Q}_{22}\\\end{matrix}\right)\right)\left(\left(\begin{matrix}R_{22}&R_{12}\\R_{21}&R_{22}\\\end{matrix}\right)-\left(\begin{matrix}{R_{22}-R}_{11}&0\\0&0\\\end{matrix}\right)\right).\square</math>
| |
| == See also == | | == See also == |
| [[List of mathematical symbols]] | | [[List of mathematical symbols]] |