Approximate matrix factorisations for sparse updates

Michael Drexler

SC/CM, Gates 2B, Stanford University, Stanford CA 94305-9025


Abstract

The application of Newton's Method to solve non-linear systems often leads to sparse updates of the Jacobian matrix. Despite being sparse, the update is usually not of a low enough rank to qualify for the use of generic low-rank techniques, such as methods related to the Sherman-Morrison formula. It is however possible to exploit the sparsity in direct methods by viewing the update as a perturbation to an existing factorisation and analysing its propagation. This results in an approximate factorisation that can be used for preconditioning at lower cost and with usually better results than an incomplete factorisation. For some matrices with special structure, it is even possible to apply the technique to the original factorisation by iterating a characteristic recursion for the columns of the matrix. As an example, we will introduce the technique for the Cholesky factorisation of matrices arising from discretising the two-dimensional Laplace operator. We will then consider the LU factorisation of a general matrix and discuss when approximate factorisations might be applied effectively. It is our belief that the combination of a preconditioning approximate factorisation and an iterative linear solver is in many cases the method of choice for the solution of the Jacobian system in Newton's Method.