Question

How many operations are needed to multiply two \(32 \times 32\) matrices using the algorithm referred to in Example 5?

Short answer

Thus, the required result is 95,722.

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply Recurrence Relation

$$\begin{gathered} f\left(n\right)=7f(n/2)+\frac{15n^2}{4} \\ f\left(1\right)=1 \end{gathered}$$

The result from example 5 (mentioned in the exercise prompt):

$$\begin{gathered} f\left(n\right)=7f(n/2)+\frac{15n^2}{4} \\ f\left(1\right)=1 \end{gathered}$$

Given two \(32 \times 32\) matrices and thus in this case $n=32$: repeatedly apply the recurrence relation with n = 32 :

$$\begin{gathered} f\left(32\right)=7f\left(16\right)+\frac{15·{32}^2}{4}n \\ f\left(32\right)=7f\left(16\right)+3840n \\ f\left(32\right)=7\left(7f\left(8\right)+\frac{15·{16}^2}{4}\right)+3810n \\ f\left(32\right)=7\left(7\int \left(8\right)+960\right)+3810n \\ f\left(32\right)=7\left(7\left[7f\left(4\right)+\frac{15·8^2}{4}\right]+960\right)+3810n \\ f\left(32\right)=7\left(7\right[7f\left(4\right)+240]+960)+3810n \end{gathered}$$