"LU Factorizations in the Limit of Infinitesimal Rids"

Naveen Somasunderam, UCSB ECE Ph.D. Defense

July 4th (Sunday), 9:00pm
Building 406, Room 216

Differential and Integral operators can be given discrete equivalents by discretizing their domain for example by finite difference schemes or quadrature methods. The solution to these equations then requires computing the $LU$ factorization of the discrete operators. In this thesis we look at the limit of $LU$ factorizations of discrete differential and integral operators as the discretization size goes to zero (that is the matrices grow in size to infinity).

We first conjecture the existence of such limits for scalar tridiagonal matrices. In particular, we show that the Schur complements that arise from Gaussian elimination have point-wise limits on the grid.

In the second part of this thesis we look at the constant coefficient Laplacian in two and three dimensions. It is proven that the final Schur complement of the discretized Laplacian converges in the induced two norm to a known fixed point as the grid grows in every direction.

This result is subsequently used to show that the Schur complements exhibit off-diagonal blocks with low rank.

Finally, we also present conjectures on the Cholesky factorization of the variable coefficient Laplacian on the unit square. Moreover, we also analyze the class of matrices know as Diagonal plus semiseparable matrices which arise naturally in the theory, and correspond to discrete Integral kernels.

One of the many practical implications of this theory is that knowing such limits may permit us to construct fast solvers for the underlying equations. These issues are under investigation.

Hosted by: Prof. Shiv Chandrasekaran