Generating good meshes and inverting good matrices

17 June 2004
Prof Gilbert Strang
An essential first step in many problems of numerical analysis and computer graphics is to cover a region with a reasonably regular mesh. We describe a short MATLAB code that begins with a "distance function" to describe the region: $d(x)$ is the distance to the boundary (with d < 0 inside the region). The algorithm decides the location of nodes and the choice of edges. At each iteration the mesh becomes a truss (with forces in the edges that move the nodes). Then the Delaunay algorithm resets the topology (the choice of edges). The input includes a size function $h(x)$ to vary the desired meshlengths over the region. \\ \\ The code is adaptable and public ( It extends directly to $n$ dimensions. The 2D meshes are remarkably regular. In higher dimensions it is difficult to avoid "slivers". The theory is not complete. \\ \\ We look for the "right proof" of a known result about the inverse of a tridiagonal matrix $T$: Every 2 by 2 submatrix on and above the diagonal of inv($T$), or on and below the diagonal, has determinant = zero. This is the case $p = 1, k = 1$ of a general result for (band + low rank) matrices: All submatrices $B$ above the $p$th superdiagonal of $T$ have rank($B$) < $k$ if and only if all submatrices $C$ above the $p$th subdiagonal of inv($T$) have rank($C$) < $p+k$. \\ \\ A quick proof uses the Nullity Theorem. The complementary subspaces $Ba$ and $C$ have the same nullity. These full matrices inv($T$) appear in integral equations and in the boundary element method. The large low rank submatrices allow fast multiplication. The theory of decay away from the main diagonal could extend to include the property of low rank.
  • Computational Mathematics and Applications Seminar