Question $3$

$60$ marks

The matrix $Ain{R}^{nn}$ has the form

where vec$(a),$vec$(b),$vec$(c)in{R}^n.$ The entries of vec$(a),$vec$(b),$ and vec$(c)$ are all assumed to be nonzero.

$($a$)$ Write a pseudo$-$code for computing the product of this matrix with a vector. That is$,$ given

vectors vec$(a),$vec$(b),$ and vec$(c)$ that describe the matrix A and given a vector $xin{R}^n,$ we want to have

an algorithm to compute the matrix$-$vector product vec$(y)=$Avec$(x)$ that avoids multiplying by$,$ and

adding, zeros. Your pseudo$-$code should have the following form:

Input: vector vec$(x)in{R}^n$; vectors vec$(a),$vec$(b),$vec$(c)in{R}^n$ that define matrix A according to definition $(1).$

Insert pseudo$-$code here

Output: vector vec$(y)in{R}^n$ such that vec$(y)=$Avec$(x)$

$($b$)$ Analyse the complexity of the algorithm from part $($b$).$ That is$,$ determine how many flops

are required to compute the product. In terms of "Big$-$Oh$"$ notation, what is the asymptotic

behaviour of your algorithm as $n$ increases? How is that different from ordinary matrix$-$vector

multiplication?

$($c$)$ Implement your pseudo$-$code following the starter code in the repository.

$($d$)$ Write a script that does the following:

it generates random vectors vec$(a),$vec$(b),$vec$(c),$vec$(x)$ of size $n$;

it calls your matrix$-$vector multiplication function and measures and stores the wall time

it takes to complete;

it computes the matrix$-$vector product using the built$-$in function $o+$ and measures and

stores the wall time it takes to complete;

it repeats steps $1-3$ for matrix sizes $n=2^k,$ starting from $k=2.$

it plots the wall times for each method as a function of $n$ on the appropriate scale to

verify the order of complexity you found at $($b$)$;

for comparison, it plots lines corresponding to $n$ and $n^2.$

Make sure your script uses matrices large enough to clearly see the scaling $($order of complex$-$

ity$).$ Follow the starter code in the repository. Save the plot that your script produces

and include it in your LaTeX$/$PDF document.

$[$circ$\_$prod$\_$starter$\_$code.py$]$

import numpy as np

def circ$\_$prod$($a$,$b$,$c$,$x$)$:

$...$

for i in range$(...)$:

y$[$i$]=$

return y

$[$run$\_$circ$\_$starter$\_$code.py$]$

import numpy as np

import matplotlib.pyplot as plt

from time import time

from circ$\_$prod import $*$

wtimes $=$

for k in range$(...)$:

n $=$

a $=$ np$.$random.rand$($n$,1)$

b $=$ np$.$random.rand$($n$,1)$

c $=$ np$.$random.rand$($n$,1)$

x $=$ np$.$random.rand$($n$,1)$

start $=$

y$0=$ circ$\_$prod$($a$,$b$,$c$,$x$)$

elapsed$0=$

wtimes$[...]=$

A $=$

for i in range$(...)$:

A$[$i$,$i$]=$

for i in range$(...)$:

A$[$i$,$i$+1]=$

A$[$i$+1,$i$]=$

A$[0,$n$-1]=$

A$[$n$-1,0]=$

start $=$

y$1=$ A @ x

elapsed$1=$

wtimes$[...]=$

plt$....($wtimes$[$:$,0],$wtimes$[$:$,1],\text{'}-*$k$\text{'})$

plt$....($wtimes$[$:$,0],$wtimes$[$:$,2],\text{'}-*$b$\text{'})$

plt$....(...)$

plt$....(...)$

plt$.$show$()$

$[$circ$\_$prod$\_$test.py$]$

import numpy as np

from memory$\_$profiler import memory$\_$usage

from circ$\_$prod import $*$

def test$\_$circ$\_$prod$()$:

n $=10000$

a $=$ np$.$random.rand$($n$,1)$

b $=$ np$.$random.rand$($n$,1)$

c $=$ np$.$random.rand$($n$,1)$

x $=$ np$.$random.rand$($n$,1)$

mem$\_$usage, y $=$ memory$\_$usage$($proc$=($circ$\_$prod,$($a$,$b$,$c$,$x$)),$retval$=$True,max$\_$usage$=$True$)$

sparse $=$ mem$\_$usage $<mtext\; id="EditorElement\_364195"></mtext><mn\; id="EditorElement\_364196">7</mn><mn\; id="EditorElement\_364197">0</mn><mn\; id="EditorElement\_364198">.</mn><mn\; id="EditorElement\_364199">0</mn>$

n $=100$

a $=$ np$.$random.rand$($n$,1)$

b $=$ np$.$random.rand$($n$,1)$

c $=$ np$.$random.rand$($n$,1)$

x $=$ np$.$random.rand$($n$,1)$

y$0=$ circ$\_$prod$($a$,$b$,$c$,$x$)$

A $=$ np$.$zeros$(($n$,$n$))$

for i in range$($n$)$:

A$[$i$,$i$]=$ a$[$i$]$

for i in range$($n$-1)$:

A$[$i$,$i$+1]=$ c$[$i$]$

A$[$i$+1,$i$]=$ b$[$i$+1]$

A$[0,$n$-1]=$ b$[0]$

A$[$n$-1,0]=$ c$[$n$-1]$

y$1=$ A @ x

correct $=$ np$.$linalg.norm$($y$0-$y$1,2)<mtext\; id="EditorElement\_364594"></mtext><mn\; id="EditorElement\_364595">1</mn>$e$-10$

assert sparse and correct