Question

For \(2 \times 2\) matrices, the complexity of matrix multiplication can be determined using the algorithm described below where the number of arithmetic operations (additions, subtractions, and multiplications) are one measure of complexity. Let \(A=\) \(\left(\begin{array}{ll}a_{11} & a_{12} \\ a_{21} & a_{22}\end{array}\right)\) and \(B=\left(\begin{array}{ll}b_{11} & b_{12} \\\ b_{21} & b_{22}\end{array}\right) .\) Calculate $$\begin{array}{l} m_{1}=\left(a_{11}+a_{22}\right)\left(b_{11}+b_{22}\right) \\ m_{5}=\left(a_{21}+a_{22}\right) b_{11} \\ m_{2}=\left(a_{11}-a_{22}\right)\left(b_{21}+b_{22}\right) \\ m_{6}=a_{11}\left(b_{12}-b_{22}\right) \\ m_{3}=\left(a_{11}-a_{21}\right)\left(b_{11}+b_{12}\right) \\ m_{7}=a_{22}\left(b_{21}-b_{11}\right) \\ m_{4}=\left(a_{11}+a_{12}\right) b_{11} \end{array}$$ $$\text { Now, let } C=\left(\begin{array}{ll}c_{11} & c_{12} \\\c_{21} & c_{22}\end{array}\right) \text { where }$$ $$\begin{aligned}c_{11} &=m_{1}+m_{2}-m_{4}+m_{7} \\\c_{12} &=m_{4}+m_{6} \\\c_{21} &=m_{5}+m_{7} \\\c_{22} &=m_{1}-m_{3}-m_{5}+m_{6}\end{aligned}$$ $$\text { (a) Use the algorithm described to find the matrix product for }$$ $$ \left(\begin{array}{ll} 3 & 5 \\ 4 & 8\end{array}\right) \quad\left(\begin{array}{ll}2 & 7 \\\5 & 9\end{array}\right)$$ (b) For matrices of size \(2^{r} \times 2^{r}\), partition them into \(2^{r-1} \times 2^{r-1}\) submatrices, and use the procedure shown for \(2 \times 2\) matrices to compute the product. Carry out this process for the following matrices: $$\left(\begin{array}{llll}3 & 5 & 2 & 5 \\\4 & 8 & 7 & 3 \\\4 & 6 & 9 & 9 \\\3 & 6 & 9 & 7\end{array}\right) \quad\left(\begin{array}{llll}2 & 7 & 3 & 5 \\\5 & 9 & 4 & 6 \\\3 & 5 & 9 & 8 \\\5 & 3 & 2 & 1\end{array}\right)$$ (c) Show that matrix multiplication using this algorithm satisfies the recurrence relation $$f_{r}=7 f_{r-1}+18 \cdot 2^{r-2} \text { for } r \geq 1$$ Solve this recurrence. How does this result compare with the classical method of multiplying matrices?

Short answer

The product of the given 2x2 matrices is \(\begin{pmatrix} 59 & 10 \\ 48 & 100 \end{pmatrix}\). Recurrence relation shows Strassen's is more efficient than classical for large matrices.

Step-by-step solution

Calculate each m-value for given 2x2 matrices

Given matrices:\[A = \begin{pmatrix} 3 & 5 \ 4 & 8 \end{pmatrix}, B = \begin{pmatrix} 2 & 7 \ 5 & 9 \end{pmatrix}\]Now, calculate each m-value:- \(m_1 = (3+8)(2+9) = 11 \times 11 = 121\)- \(m_2 = (3-8)(5+9) = -5 \times 14 = -70\)- \(m_3 = (3-4)(2+7) = -1 \times 9 = -9\)- \(m_4 = (3+5) \times 2 = 8 \times 2 = 16\)- \(m_5 = (4+8) \times 2 = 12 \times 2 = 24\)- \(m_6 = 3 \times (7-9) = 3 \times -2 = -6\)- \(m_7 = 8 \times (5-2) = 8 \times 3 = 24\)

Form the resulting matrix C

Using the calculated m-values, find the elements of matrix \(C\):- \(c_{11} = m_1 + m_2 - m_4 + m_7 = 121 - 70 - 16 + 24 = 59\)- \(c_{12} = m_4 + m_6 = 16 - 6 = 10\)- \(c_{21} = m_5 + m_7 = 24 + 24 = 48\)- \(c_{22} = m_1 - m_3 - m_5 + m_6 = 121 + 9 - 24 - 6 = 100\)Thus, \[C = \begin{pmatrix} 59 & 10 \ 48 & 100 \end{pmatrix}\]

Partition 4x4 matrices into 2x2 submatrices

For the given 4x4 matrices, partition them into 2x2 submatrices:\[A = \begin{pmatrix} \begin{pmatrix} 3 & 5 \ 4 & 8 \end{pmatrix} & \begin{pmatrix} 2 & 5 \ 7 & 3 \end{pmatrix} \\begin{pmatrix} 4 & 6 \ 3 & 6 \end{pmatrix} & \begin{pmatrix} 9 & 9 \ 9 & 7 \end{pmatrix} \end{pmatrix}\]\[B = \begin{pmatrix} \begin{pmatrix} 2 & 7 \ 5 & 9 \end{pmatrix} & \begin{pmatrix} 3 & 5 \ 4 & 6 \end{pmatrix} \\begin{pmatrix} 3 & 5 \ 5 & 3 \end{pmatrix} & \begin{pmatrix} 9 & 8 \ 2 & 1 \end{pmatrix} \end{pmatrix}\] Treat each sub-block as a 2x2 matrix and use the same algorithm as Step 1 and Step 2 for each pair of matrices to compute their product.

Solve the recurrence relation

The recurrence relation given is:\[f_r = 7f_{r-1} + 18 \cdot 2^{r-2}\]To solve it, assume a solution of the form \(f_r = A \cdot 7^r + B\), substitute into the relation, and solve for constants A and B.

Compare algorithm complexity with classical method

Classical matrix multiplication for \(2^r \times 2^r\) matrices requires \(2^{3r}\) operations. Strassen algorithm with complexity represented by the recurrence \(f_r\) given is more efficient in terms of fewer multiplications as r grows, specifically reducing multiplications from 8 to 7 in stepwise comparison.

Key concepts

Algorithm Complexity

Algorithm complexity is a way to measure the efficiency of an algorithm in terms of time, space, or other resources needed to complete a task.
In the context of matrix multiplication, we often focus on the number of arithmetic operations required to multiply two matrices. Classic matrix multiplication of two matrices each containing elements in a size of \(2^r \times 2^r\) involves \(2^{3r}\) operations because each element in the resulting matrix is the sum of the products of pairs of elements from each row of the first matrix and each column of the second.
This means the algorithm is cubic in nature regarding the input size.
As the number of rows and columns increases, the number of operations increases drastically, making it less efficient for larger matrices.

• Classic complexity: \(O(n^3)\).
• Strassen's Algorithm complexity: \(O(n^{ ext{log}_27}) \approx O(n^{2.81})\).

Considering algorithm complexity guides developers to choose better algorithms for large data, which results in time savings and improved performance overall.

Recurrence Relation

A recurrence relation is an equation or inequality that describes a function in terms of its value at smaller inputs. It often appears when the function is defined in terms of recursion or dynamic programming.
In the context of the Strassen algorithm for matrix multiplication, a recurrence relation helps express the complexity of the algorithm as it processes larger matrices by breaking them into smaller ones.
The recurrence relation involved in the Strassen algorithm for \(2^r \times 2^r\) matrices is given by\[f_r = 7f_{r-1} + 18 \cdot 2^{r-2}\]

• Each recursion level involves 7 multiplications instead of 8.
• As \(r\) increases, this reduction filters through, lowering the total number of arithmetic operations.

The relation shows how the number of operations grows based on previous operations, portraying how the Strassen algorithm surpasses classical methods as matrix size increases.
Solving this particular recurrence relation allows us to find a closed-form expression for the number of operations, highlighting the algorithm's efficiency advantage for larger matrices.

Strassen Algorithm

The Strassen algorithm revolutionized matrix multiplication by reducing the number of necessary multiplication operations.
Developed by Volker Strassen, it reduces the traditional requirement from 8 down to 7 multiplications for a \(2 \times 2\) matrix.
While traditional addition and subtraction operations increase slightly—due to more interspersed calculations—the significant reduction in multiplications makes it more efficient for larger matrices.
This method is especially useful when dealing with large matrices since it reduces the complexity from \(O(n^3)\) to approximately \(O(n^{2.81})\).

• Utilizes divide and conquer strategy.
• Splits matrices into submatrices, applying recursive multiplication.

By leveraging smaller matrix multiplications efficiently, Strassen's method showcases a clever use of partial results, exemplifying algorithmic innovation that saves on computation time.
Although it might be less efficient for very small matrices due to overhead, the savings become apparent as matrix sizes grow.