{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "952969f6", "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": "233450a7", "metadata": {}, "source": [ "(section-linsys-structure)=\n", "# Exploiting matrix structure\n", "\n", "A common situation in computation is that a problem has certain properties or structure that can be used to get a faster or more accurate solution. There are many properties of a matrix that can affect LU factorization. For example, an $n \\times n$ matrix $A$ is **diagonally dominant** if\n", "\n", "```{math}\n", " :label: diag-dominant\n", " |A_{ii}| > \\sum_{\\substack{j=1\\\\ j \\neq i}}^{n} |A_{ij}| \\hskip 0.25in \\text{for each } i=1,\\ldots,n.\n", "```\n", "\n", "It turns out that a diagonally dominant matrix is guaranteed to be invertible, and row pivoting is not required for stability.\n", "\n", "We next consider three important types of matrices that cause the LU factorization to be specialized in some important way.\n", "\n", "## Banded matrices\n", "\n", "```{index} ! bandwidth of a matrix, ! tridiagonal matrix\n", "```\n", "\n", "::::{proof:definition} Bandwidth\n", "A matrix $\\mathbf{A}$ has **upper bandwidth** $b_u$ if $j-i > b_u$ implies $A_{ij}=0$, and **lower bandwidth** $b_\\ell$ if $i-j > b_\\ell$ implies $A_{ij}=0$. We say the total **bandwidth** is $b_u+b_\\ell+1$. When $b_u=b_\\ell=1$, we have the important case of a **tridiagonal matrix**. \n", "::::\n", "\n", "\n", "(demo-structure-banded)=\n", "```{proof:demo}\n", "```\n", "\n", "```{raw} html\n", "