Matrix Multiplication

Matrix multiplication

Let A and B be $n\times n$ matrices, where $n=2^k$ . Each of C's $n^2$ entries requires n multiplications, giving $W(n)=O(n^3)$ .

A simple divide-and-conquer strategy partitions the matrices into blocks.

\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix} \begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix} = \begin{pmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{pmatrix}

Here:

\begin{aligned} C_{11}&=A_{11}B_{11}+A_{12}B_{21}\\ C_{12}&=A_{11}B_{12}+A_{12}B_{22}\\ C_{21}&=A_{21}B_{11}+A_{22}B_{21}\\ C_{22}&=A_{21}B_{12}+A_{22}B_{22} \end{aligned}

The original problem becomes eight subproblems, with recurrence:

W(n)=\begin{cases}1&n=1\\8W(n/2)+cn^2&n>1\end{cases}

Solving gives:

W(n)=O(n^3)

Simple division does not lower the order, but reducing the number of subproblems can improve matrix multiplication.

QUESTION

Which expression gives block C₁₂?

Strassen matrix multiplication

Let $M_1,M_2,\ldots,M_7$ be seven matrix-product subproblems:

\begin{aligned} M_1&=A_{11}(B_{12}-B_{22})\\ M_2&=(A_{11}+A_{12})B_{22}\\ M_3&=(A_{21}+A_{22})B_{11}\\ M_4&=A_{22}(B_{21}-B_{11})\\ M_5&=(A_{11}+A_{22})(B_{11}+B_{22})\\ M_6&=(A_{12}-A_{22})(B_{21}+B_{22})\\ M_7&=(A_{11}-A_{21})(B_{11}+B_{12}) \end{aligned}

Combine these intermediate matrices to obtain the result:

\begin{aligned} C_{11}&=M_5+M_4-M_2+M_6\\ C_{12}&=M_1+M_2\\ C_{21}&=M_3+M_4\\ C_{22}&=M_5+M_1-M_3-M_7 \end{aligned}

Seven subproblems and eighteen matrix additions or subtractions give:

W(n)=\begin{cases}1&n=1\\7W(n/2)+18(n/2)^2&n>1\end{cases}

Solving gives:

W(n)=O(n^{\log_2 7})\approx O(n^{2.8075})

The Coppersmith–Winograd algorithm improved the matrix-multiplication upper bound to $O(n^{2.376})$ ; subsequent research has improved this bound further. Matrix multiplication is used in scientific computing, graphics, and data mining. Regression, clustering, principal component analysis, and decision trees frequently involve large matrix operations.

Historical result and subsequent improvement: the Coppersmith–Winograd paper and later matrix multiplication research.

PRO EXCLUSIVEGo further with Pro

Unlock the complete interactive lab, deeper explanations, and curated reference answers.

Unlock Pro access

QUESTION

Why does Strassen improve the asymptotic order?

QUESTION

May M₁=A₁₁(B₁₂−B₂₂) always be reordered to (B₁₂−B₂₂)A₁₁?

Given A=[[2,1],[3,4]] and B=[[5,2],[1,3]], use the lesson’s Strassen formulas to compute AB on paper, preserving multiplication order.

Compute M₁ through M₇.
Combine C₁₁, C₁₂, C₂₁, C₂₂ from the intermediate results.
Check with ordinary multiplication and compare product counts.

Matrix Multiplication