\part{Numerical solutions to systems of equations}
- power method
\chapter{Power method}

It is possible to solve the eigenequation $\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$ analytically by the characteristic equation, however this can be computationally expensive since it requires calculating the determinant.

The \emph{power method} is a numerical method that converges to the normalized eigenvector with the largest eigenvalue.

\begin{algorithm}
\begin{algorithmic}
	\WHILE{ $ \| \mathbf{u}-\mathbf{v} \|  \leq \varepsilon $}
		\STATE $\mathbf{u} \gets \mathbf{v}$
		\STATE $\mathbf{v} \gets \frac{\mathbf{A}\mathbf{v}}{\| \mathbf{A}\mathbf{v}\|}$
	\ENDWHILE
\end{algorithmic}
\end{algorithm}

\chapter{Inverse power method}

Perhaps one wants the eigenvector associated with the smallest eigenvalue. Sincethe eigenequation $\mathbf{A}\mathbf{v}=\lambda \mathbf{v}$ can be written equivalently as $\mathbf{A}^{-1}\mathbf{v}=\frac{1}{\lambda}\mathbf{v}$, and the power method converges to the eigenvector with the largest eigenvalue, employing the power method on the form $\mathbf{A}^{-1}\mathbf{v}=\frac{1}{\lambda}\mathbf{v}$ returns the eigenvector with the largest $\frac{1}{\lambda}$, or equivalently, with the smallest $\lambda$!

This is called the \emph{inverse power method}.

\begin{algorithm}
\begin{algorithmic}
	\WHILE{$\| \mathbf{u}-\mathbf{v} \|  \leq \varepsilon$}
		\STATE $\mathbf{u} \gets \mathbf{v}$
		\STATE $\mathbf{v} \gets \frac{\mathbf{A}^{-1}\mathbf{v}}{\| \mathbf{A}^{-1}\mathbf{v}\|}$
	\ENDWHILE
\end{algorithmic}
\end{algorithm}

\chapter{QR iteration}
\begin{algorithm}
\begin{algorithmic}
	\WHILE{Change this}
		\STATE $\mathbf{A} := \mathbf{Q}\mathbf{R}$
		\STATE $\mathbf{A} \gets \mathbf{R}\mathbf{Q}$
	\ENDWHILE
\end{algorithmic}
\end{algorithm}

- QR iteration
- sparse matrix
A sparse matrix is an $n \times m$ array that has may zero entries. In such cases, there may be more memory efficientr structures like a COO where one stores the row, column and data of a matrix entry. Or a CSC which stores the data of each matrix entry ordered by coulmn, and uses an array of ranges to determine which section 
COO w



\begin{itemize}
	\item Row array
	\item Column array
	\item Data array
\end{itemize}




\begin{itemize}
	\item Row array 
	\item Data array (ordered by column)
	\item 'Column range' array
\end{itemize}

- Arnoldi iteration
\chapter{Arnoldi iteration}

Works by creating an orthonormal basis out of repeated applications of $\mathbf{A}$ on some random vector with the Gram-Schmidt process, creates a similar matrix, and then applies a QR decomposition to approximate eigenvalues.

\begin{algorithm}
\begin{algorithmic}
	\FOR{$\text{Change this}$}
		\STATE $\mathbf{q}_k \gets \mathbf{A}\mathbf{q}_{k-1} $
		\FOR{$\text{Change this}$}
			\STATE $\mathbf{q}_k \gets \mathbf{q}_{k}-(\mathbf{q}_{k}^{*} \mathbf{q}_{k})\mathbf{q}_{k}$
			\STATE $\mathbf{q}_{k+1} \gets \frac{\mathbf{q}_{k}}{\| \mathbf{q}_k \|}$
			\STATE $\mathbf{A} \gets \mathbf{R}\mathbf{Q}$
		\ENDFOR
	\ENDFOR
	\STATE $\text{Augment each }\mathbf{q}_{k} \text{ column-wise to create } \mathbf{H}$
	\STATE $\text{Perform QR decomposition on } \mathbf{H}$
\end{algorithmic}
\end{algorithm}

\chapter{Krylov subspaces}