Skip to main content

Subsection 7.5.2 Summary

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*}
Definition 7.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).

login