{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "80ed71c1", "metadata": { "tags": [ "remove-cell" ] }, "outputs": [ { "name": "stderr", "output_type": "stream", "text": [ "┌ Info: verify download of index files...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:139\n", "┌ Info: reading database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:23\n", "┌ Info: adding metadata...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:67\n", "┌ Info: adding svd data...\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:69\n", "┌ Info: writing database\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/download.jl:74\n", "┌ Info: used remote sites are sparse.tamu.edu with MAT index and math.nist.gov with HTML index\n", "└ @ MatrixDepot /Users/driscoll/.julia/packages/MatrixDepot/GEDc3/src/MatrixDepot.jl:141\n" ] } ], "source": [ "using FundamentalsNumericalComputation\n", "FNC.init_format()" ] }, { "cell_type": "markdown", "id": "d5ede285", "metadata": {}, "source": [ "(section-krylov-precond)=\n", "# Preconditioning\n", "\n", "An important aspect of MINRES and CG (and, by extension, GMRES) is that the convergence of a Krylov method can be expected to deteriorate as the condition number of the matrix increases. Even moderately large condition numbers can make the convergence impractically slow. Therefore it's common for these methods to be used with a technique to reduce the relevant condition number.\n", "\n", "```{index} GMRES; preconditioning in, ! preconditioning\n", "```\n", "\n", "::::{proof:definition} Preconditioning\n", "Given a linear system $\\mathbf{A}\\mathbf{x}=\\mathbf{b}$, a **preconditioner** is a matrix $\\mathbf{M}$ or equivalent linear transformation that modifies the system to be\n", "\n", ":::{math}\n", ":label: precond\n", "(\\mathbf{M}^{-1} \\mathbf{A}) \\mathbf{x} = \\mathbf{M}^{-1}\\mathbf{b}.\n", ":::\n", "::::\n", " \n", "More specifically, {eq}`precond` is known as *left preconditioning*, but it is the simplest and most common type.\n", "\n", "As usual, we do not want to actually compute $\\mathbf{M}^{-1}$ for a given $\\mathbf{M}$. Instead, we have a linear system with the matrix $\\mathbf{M}^{-1}\\mathbf{A}$. In a Krylov method, the operation \"let $\\mathbf{v}=\\mathbf{A}\\mathbf{u}$\" becomes a two-step process:\n", "\n", "1. Set $\\mathbf{y}=\\mathbf{A}\\mathbf{u}$.\n", "2. Solve $\\mathbf{M}\\mathbf{v}=\\mathbf{y}$ for $\\mathbf{v}$.\n", "\n", "```{index} sparse matrix, LU factorization\n", "```\n", "\n", "As an implementation detail, it is common to provide the Krylov solver with code that does step 2; if the matrix $\\mathbf{M}$ is given, the default is to use sparse factorization. \n", "\n", "There are competing objectives in the choice of $\\mathbf{M}$. On one hand, we want $\\mathbf{M}^{-1}\\mathbf{A}\\approx \\mathbf{I}$ in some sense because that makes {eq}`precond` easy to solve by Krylov iteration. Hence $\\mathbf{M}\\approx \\mathbf{A}$. On the other hand, we desire that solving the system $\\mathbf{M}\\mathbf{v}=\\mathbf{y}$ be relatively fast. \n", "\n", ":::{proof:observation}\n", "Good preconditioning is a matter of finding an easily inverted (i.e., quickly solvable) approximation of the original matrix. \n", ":::\n", "\n", "## Diagonal preconditioning\n", "\n", "One of the simplest choices for the preconditioner $\\mathbf{M}$ is a diagonal matrix. This definitely meets the requirement of being fast to invert: the solution of $\\mathbf{M}\\mathbf{v}=\\mathbf{y}$ is just $v_i=y_i/M_{ii}$. The only question is whether it can be chosen in such a way that $\\mathbf{M}^{-1}\\mathbf{A}$ is much more amenable to Krylov iterations than $\\mathbf{A}$ is. This may be the case when the rows of $\\mathbf{A}$ differ greatly in scale, or when $\\mathbf{A}$ is diagonally dominant (see {eq}`diag-dominant`).\n", "\n", "(demo-precond-diagonal)=\n", ":::{proof:demo}\n", ":::\n", "\n", "```{raw} html\n", "