## Unit7.5.2Summary

Let $A \in \mathbb R^{n \times n}$ be tridiagonal and SPD so that

\begin{equation*} A = \left( \begin{array}{c c c c c c c} \alpha_{0,0} \amp \alpha_{1,0} \amp \amp \amp \\ \alpha_{1,0} \amp \alpha_{1,1} \amp \alpha_{2,1} \amp \amp \\ \amp \ddots \amp \ddots \amp \ddots \amp \\ \amp \amp \alpha_{n-2,n-3} \amp \alpha_{n-2,n-2} \amp \alpha_{n-1,n-2} \\ \amp \amp \amp \alpha_{n-1,n-2} \amp \alpha_{n-1,n-1} \end{array} \right). \end{equation*}

Then its Cholesky factor is given by

\begin{equation*} \left( \begin{array}{c c c c c c c} \lambda_{0,0} \amp \amp \amp \amp \\ \lambda_{1,0} \amp \lambda_{1,1} \amp \amp \amp \\ \amp \ddots \amp \ddots \amp \amp \\ \amp \amp \lambda_{n-2,n-3} \amp \lambda_{n-2,n-2} \amp \\ \amp \amp \amp \lambda_{n-1,n-2} \amp \lambda_{n-1,n-1} \end{array} \right). \end{equation*}

An algorithm for computing it is given by

\begin{equation*} \begin{array}{l} {\bf for~} i = 0, \ldots, n-2 \\ ~~~ \alpha_{i,i} := \sqrt{ \alpha_{i,i} } \\ ~~~ \alpha_{i+1,i} := \alpha_{i+1,i} / \alpha_{i,i} \\ ~~~ \alpha_{i+1,i+1} := \alpha_{i+1,i+1} - \alpha_{i+1,i} \alpha_{i+1,i} \\ {\bf endfor} \\ \alpha_{n-1,n-1} := \sqrt{ \alpha_{n-1,n-1} } \\ \end{array} \end{equation*}

It requires $n$ square roots, $n-1$ divides, $n-1$ multiplies, and $n-1$ subtracts. An algorithm for overwriting $y$ with the solution to $A x = y$ given its Cholesky factor is given by

• Overwrite $y$ with the solution of $L z = y$ (forward substitution) is accomplished by the following algorithm (here $L$ has overwritten $A$):

\begin{equation*} \begin{array}{l} {\bf for~} i = 0, \ldots, n-2 \\ ~~~ \psi_i := \psi_i / \alpha_{i,i} \\ ~~~ \psi_{i+1} := \psi_{i+1} - \alpha_{i+1,i} \psi_i \\ {\bf endfor} \\ \psi_{n-1} := \psi_{n-1} / \alpha_{n-1,n-1} \end{array} \end{equation*}
• Overwriting $y$ with the solution of $L^T x = z \text{,}$ (where $z$ has overwritten $y$ (back substitution).

\begin{equation*} \begin{array}{l} {\bf for~} i = n-1, \ldots, 1 \\ ~~~ \psi_i := \psi_i / \alpha_{i,i} \\ ~~~ \psi_{i-1} := \psi_{i-1} - \alpha_{i,i-1} \psi_i \\ {\bf endfor} \\ \psi_{0} := \psi_{0} / \alpha_{0,0} \end{array} \end{equation*}
###### Definition7.5.2.1.

The half-band width of a symmetric matrix equals the number of subdiagonals beyond which all the matrix contains only zeroes. For example, a diagonal matrix has half-band width of zero and a tridiagonal matrix has a half-band width of one.

Nested dissection: a hierarchical partitioning of the graph that captures the sparsity of a matrix in an effort to reorder the rows and columns of that matrix so as to reduce fill-in (the overwriting of zeroes in the matrix with nonzeroes).

Splitting methods: The system of linear equations $A x = b \text{,}$ splitting methods view $A$ as $A = M - N$ and then, given an initial approximation $x^{(0)} \text{,}$ create a sequence of approximations, $x^{(k)}$ that under mild conditions converge to $x$ by solving

\begin{equation*} M x^{(k+1)} = N x^{(k)} + b \end{equation*}

or, equivalently, computing

\begin{equation*} x^{(k+1)} = M^{-1} ( N x^{(k)} + b ). \end{equation*}

This method converges to $x$ if for some norm $\| \cdots \|$

\begin{equation*} \| M^{-1} N \| \lt 1. \end{equation*}

Given $A = D - L - U$ where $-L \text{,}$ $D \text{,}$ and $-U$ equal the strictly lower triangular, diagonal, and strictly upper triangular parts of $A \text{,}$ commonly used splitting methods are

• Jacobi iteration: $A = \begin{array}[t]{c} \underbrace{ D } \\ M \end{array} - \begin{array}[t]{c} \underbrace{ ( L + U ) } \\ N \end{array}.$

• Gauss-Seidel iteration: $A = \begin{array}[t]{c} \underbrace{ D - L } \\ M \end{array} - \begin{array}[t]{c} \underbrace{ U } \\ N \end{array}.$

• Successive Over-Relaxation (SOR): $A = \begin{array}[t]{c} \underbrace{ \frac{1}{\omega} D - L } \\ M \end{array} - \begin{array}[t]{c} \underbrace{ \left( \frac{1-\omega}{\omega}D + U \right) } \\ N \end{array},$ where $\omega$ is the relaxation parameter.

• Symmetric Successive Over-Relaxation (SSOR).