Using the two algorithms to Python code:

Algorithm $2$ Forward substitution to solve Lx $=$ b$,$ where L is lower triangular

for i $=1,2,...,$ n do

xi $$ bi

for j $=1,2,...,$ i $1$ do

xi $$ xi $$ Lij xj

end for

xi $$ xi$/$Lii $$ Not necessary if L is unit lower triangular.

end for

Algorithm $3$ Backward substitution to solve U x $=$ b$,$ where U is upper triangular

for i $=$ n$,$ n $1,...,1$ do

xi $$ bi

for j $=$ i $+1,$ i $+2,...,$ n do

xi $$ xi $$ Uij xj

end for

xi $$ xi$/$Uii

end for

The input is the file with matrix in COO format, the functions below are used to tranform it to CSR format:

def load$\_$as$\_$csr$($filename$)$:

# Read m$,$ n$,$ and nnz from the file

m$,$ n$,$ nnz $=$ np$.$genfromtxt$($filename$,$ max$\_$rows$=1,$ dtype$=$None$)$

# Read the data as a list of tuples $[($i$,$j$,$v$),...]$

data $=$ np$.$genfromtxt$($filename$,$ skip$\_$header$=1,$ dtype$=$None$)$

# Allocate arrays

I $=$ np$.$zeros$($m $+1,$ dtype$=$int$)$

J $=$ np$.$zeros$($nnz$,$ dtype$=$int$)$

V $=$ np$.$zeros$($nnz$)$

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

i $=$ data$[$k$][0]$

I$[$i$+1]+=1$

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

I$[$i$+1]+=$ I$[$i$]$

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

i$,$ j$,$ v $=$ data$[$k$]$

idx $=$ I$[$i$]$

I$[$i$]+=1$

J$[$idx$]=$ j

V$[$idx$]=$ v

for i in reversed$($range$($m$))$:

I$[$i$+1]=$ I$[$i$]$

I$[0]=0$

return I, J$,$ V

def num$\_$rows$($A$)$:

return len$($A$[0])-1$

def matvec$($A$,$ v$)$:

I, J$,$ V $=$ A

m $=$ num$\_$rows$($A$)$

w $=$ np$.$zeros$($m$)$

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

begin $=$ I$[$i$]$

end $=$ I$[$i$+1]$

for idx in range$($begin$,$ end$)$:

j $=$ J$[$idx$]$

w$[$i$]+=$ V$[$idx$]*$v$[$j$]$

return w

Finish these two functions please:

Write functions tril$\_$solve and triu$\_$solve that take a matrix A in CSR format $($as a tuple of three arrays, the output of load$\_$as$\_$csr$)$ and a right$-$hand side vector b $,$ and returns the solution to Lx$=$b and Ux$=$b where L and U are the lower and upper triangular parts of A respectively.

def tril$\_$solve$($A$,$ b$)$:

I, J$,$ V $=$ A

x $=$ np$.$zeros$($len$($b$))$

# Perform lower$-$triangular solve $($forward substitution$)$

return x

def triu$\_$solve$($A$,$ b$)$:

I, J$,$ V $=$ A

x $=$ np$.$zeros$($len$($b$))$

# Perform upper$-$triangular solve $($backward substitution$)$

return x

Example of how the input file look like:

$161674$

$07-0\mathrm{.}0865112$

$08-0\mathrm{.}0114965$

$06-0\mathrm{.}64942$

$05-1\mathrm{.}25134$

$003\mathrm{.}98189$

$16-0\mathrm{.}171279$

$12-0\mathrm{.}18625$

$115-0\mathrm{.}614682$

$117\mathrm{.}61259$

$21-0\mathrm{.}18625$

$24-0\mathrm{.}0288556$

$210-6\mathrm{.}60903$

$229\mathrm{.}37045$

$28-2\mathrm{.}04836$

$26-0\mathrm{.}388906$

$339\mathrm{.}57473$

$42-0\mathrm{.}0288556$

$410-0\mathrm{.}357678$

$412-0\mathrm{.}319544$

$413-1\mathrm{.}00507$

$48-0\mathrm{.}489719$

$443\mathrm{.}77272$

$59-0\mathrm{.}0234982$

$57-7\mathrm{.}24611$

$513-0\mathrm{.}20906$

$514-0\mathrm{.}214743$

$50-1\mathrm{.}25134$

$559\mathrm{.}50564$

$61-0\mathrm{.}171279$

$615-50\mathrm{.}7619$

$62-0\mathrm{.}388906$

$68-0\mathrm{.}26047$

$6652\mathrm{.}7065$

$60-0\mathrm{.}64942$

$713-0\mathrm{.}916151$

$...$