In this assignment you will investigate how multiprocessing in Python can speedup matrix multiplication. Recall if

$A$ is an $mn$ matrix and $B$ is an $np$ matrix, given by

$A=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \text{c}\text{d}\text{o}\text{t}\text{s}& a_{1n}\\ a_{21}& a_{22}& \text{c}\text{d}\text{o}\text{t}\text{s}& a_{2n}\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ a_{m1}& a_{m2}& \text{c}\text{d}\text{o}\text{t}\text{s}& a_{mn}\end{array}\right],B=\left[\begin{array}{cccc}{b}_{11}& b_{12}& \text{c}\text{d}\text{o}\text{t}\text{s}& b_{1p}\\ b_{21}& b_{22}& \text{c}\text{d}\text{o}\text{t}\text{s}& b_{2p}\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ b_{n1}& b_{n2}& \text{c}\text{d}\text{o}\text{t}\text{s}& b_{np}\end{array}\right]$

then the matrix product $C$ is the $mp$ matrix

$C=\left[\begin{array}{cccc}{c}_{11}& c_{12}& \text{c}\text{d}\text{o}\text{t}\text{s}& c_{1p}\\ c_{21}& c_{22}& \text{c}\text{d}\text{o}\text{t}\text{s}& c_{2p}\\ \text{v}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}& \text{d}\text{d}\text{o}\text{t}\text{s}& \text{v}\text{d}\text{o}\text{t}\text{s}\\ c_{m1}& c_{m2}& \text{c}\text{d}\text{o}\text{t}\text{s}& c_{mp}\end{array}\right]$

where each element of $C$ is the inner product

$c_{ij}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+$cdots$+a_{in}{b}_{nj}={\displaystyle \underset{k=1}{\overset{n}{}}}{a}_{ik}{b}_{kj}$

for $i=1,$dots,$m$ and $j=1,$dots,$p.$

The computational complexity of the classic algorithm is therefore $O(n^3),$

$c=np*zeros((m,p))$

for $iin$ range$(m)$:

for $jin$ range $(p)$ :

sum $=0\mathrm{.}0$

for $kin$ range$(n)$:

sum $+=A[i,k]**B[k,j]$

$c[i,j]=$ sum

Based on the

mp$.$py code demonstrated in class, develop a Python code $.$py file using Sublime Text $($or other

editor$)$ to serially multiply two matrices using the classic algorithm and report elapsed runtime. Then implement a

parallel approach using the Python multiprocessing Pool.map$()$ facility. Observe each entry $c_{i,j}$ is an inner

product that can be computed independently by a separate thread. Report elapsed runtime of your parallel

implementation. Do not include the pool construction in the timing $($i$.$e$.,$ do not include time to execute

statement pool $=$ mp$.$Pool$($processes$=$threads$)).$

Choose your own values for $m,n,$ and $p.$ Initialize matrices A and $B$ with random values using

$A=np*r$ andom $*$ rand $(m,n)$

$B=np*r$ andom. rand $(n,p)$

Add an assert statement to verify the serially computed $C$ matrix is equal to the parallelly computed $C$ matrix.

Finally, answer the question: for what value of $mp$ does your parallel implementation outperform your

serial?

Code In Python