Question

Bonus: Implement the following algorithm in MATLAB and submit your solution as an m-file. Input: two n x n matrices A, B, where n = 2k for some k = 0,1,2,... Output: the product C = AB. . For k = 0, both A and B consist of only one number, and C is the product of these numbers. . For k > 0, split A, B into 4 blocks of size 2-1 x 2-1 as in A = (Au: A12), B = (Bu B12). • Call the algorithm recursively to find the following seven matrix products: I = (A11 + A22)(B11+ B22), II = (A21 + A22)B11, III = All(B12 - B22), IV = A22(B21 - B11), V = (Au + A12)B22, VI = (A21 - An)(B11 + B12), VII = (A12 - A22)(B21 + B22). • Construct C = ( ) as follows: Cu = I + IV - V+ VII, C12 = III +V, C21 = II + IV, C22 = I + III - II + VI.

Answer 1

MATLAB program is given below:

Copy and paste from below to create .m file.

%%%

clc

clear all

n=input('Enter the value of n')
A=rand(2^n)
B=rand(2^n)
if n==0
C=A*B
else
for i=1:2^(n-1)
for j=1:2^(n-1)
A11(i,j)=A(i,j);
end
end
A11
for i=1:2^(n-1)
for j=2^(n-1)+1:2^(n)
A12(i,j-2^(n-1))=A(i,j);
end
end
A12
for i=2^(n-1)+1:2^(n)
for j=1:2^(n-1)
A21(i-2^(n-1),j)=A(i,j);
end
end
A21
for i=2^(n-1)+1:2^(n)
for j=2^(n-1)+1:2^(n)
A22(i-2^(n-1),j-2^(n-1))=A(i,j);
end
end
A22

for i=1:2^(n-1)
for j=1:2^(n-1)
B11(i,j)=B(i,j);
end
end
B11
for i=1:2^(n-1)
for j=2^(n-1)+1:2^(n)
B12(i,j-2^(n-1))=B(i,j);
end
end
B12
for i=2^(n-1)+1:2^(n)
for j=1:2^(n-1)
B21(i-2^(n-1),j)=B(i,j);
end
end
B21
for i=2^(n-1)+1:2^(n)
for j=2^(n-1)+1:2^(n)
B22(i-2^(n-1),j-2^(n-1))=B(i,j);
end
end
B22
end

I=(A11+A22)*(B11+B22)
II=(A21+A22)*B11
III=A11*(B12-B22)
IV=A22*(B21-B11)
V=(A11+A12)*B22
VI=(A21-A11)*(B11+B12)
VII=(A12-A22)*(B21+B22)

C11=I+IV-V+VII
C12=III+V
C21=II+IV
C22=I+III-II+VI

C=[C11 C12; C21 C22]