48 lines
2.2 KiB
TeX
48 lines
2.2 KiB
TeX
\section*{Problem 6}
|
|
|
|
\subsection*{a)}
|
|
% Use Gaussian elimination, and then use backwards substitution to solve the equation
|
|
Renaming the sub-, main-, and supdiagonal of matrix $\boldsymbol{A}$
|
|
\begin{align*}
|
|
\vec{a} &= [a_{2}, a_{3}, ..., a_{n-1}, a_{n}] \\
|
|
\vec{b} &= [b_{1}, b_{2}, b_{3}, ..., b_{n-1}, b_{n}] \\
|
|
\vec{c} &= [c_{1}, c_{2}, c_{3}, ..., c_{n-1}] \\
|
|
\end{align*}
|
|
|
|
Following Thomas algorithm for gaussian elimination, we first perform a forward sweep followed by a backward sweep to obtain $\vec{v}$
|
|
\begin{algorithm}[H]
|
|
\caption{General algorithm}\label{algo:general}
|
|
\begin{algorithmic}
|
|
\Procedure{Forward sweep}{$\vec{a}$, $\vec{b}$, $\vec{c}$}
|
|
\State $n \leftarrow$ length of $\vec{b}$
|
|
\State $\vec{\hat{b}}$, $\vec{\hat{g}} \leftarrow$ vectors of length $n$.
|
|
\State $\hat{b}_{1} \leftarrow b_{1}$ \Comment{Handle first element in main diagonal outside loop}
|
|
\State $\hat{g}_{1} \leftarrow g_{1}$
|
|
\For{$i = 2, 3, ..., n$}
|
|
\State $d \leftarrow \frac{a_{i}}{\hat{b}_{i-1}}$ \Comment{Calculating common expression}
|
|
\State $\hat{b}_{i} \leftarrow b_{i} - d \cdot c_{i-1}$
|
|
\State $\hat{g}_{i} \leftarrow g_{i} - d \cdot \hat{g}_{i-1}$
|
|
\EndFor
|
|
\Return $\vec{\hat{b}}$, $\vec{\hat{g}}$
|
|
\EndProcedure
|
|
|
|
\Procedure{Backward sweep}{$\vec{\hat{b}}$, $\vec{\hat{g}}$}
|
|
\State $n \leftarrow$ length of $\vec{\hat{b}}$
|
|
\State $\vec{v} \leftarrow$ vector of length $n$.
|
|
\State $v_{n} \leftarrow \frac{\hat{g}_{n}}{\hat{b}_{n}}$
|
|
\For{$i = n-1, n-2, ..., 1$}
|
|
\State $v_{i} \leftarrow \frac{\hat{g}_{i} - c_{i} \cdot v_{i+1}}{\hat{b}_{i}}$
|
|
\EndFor
|
|
\Return $\vec{v}$
|
|
\EndProcedure
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
|
|
\subsection*{b)}
|
|
% Figure out FLOPs
|
|
Counting the number of FLOPs for the general algorithm by looking at one procedure at a time.
|
|
For every iteration of i in forward sweep we have 1 division, 2 multiplications, and 2 subtractions, resulting in $5(n-1)$ FLOPs.
|
|
For backward sweep we have 1 division, and for every iteration of i we have 1 subtraction, 1 multiplication, and 1 division, resulting in $3(n-1)+1$ FLOPs.
|
|
Total FLOPs for the general algorithm is $8(n-1)+1$.
|