17 June 2004

14:00

Prof Gilbert Strang

Abstract

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 (math.mit.edu/~persson/mesh). 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.