MINRES-QLP and its Application to Radial Basis Function Interpolation

CG, SYMMLQ, and MINRES are Krylov subspace methods for solving symmetric systems of linear equations. When these methods are applied to an incompatible system (that is, a singular symmetric least-squares problem), CG could break down and SYMMLQ's solution could explode, while MINRES would give a least-squares solution but not necessarily the minimum-length (pseudoinverse) solution. This understanding motivates us to design a MINRES-like algorithm to compute minimum-length solutions to singular symmetric systems.

MINRES uses QR factors of the tridiagonal matrix from the Lanczos process (where R is upper-tridiagonal). MINRES-QLP uses a QLP decomposition (where rotations on the right reduce R to lower-tridiagonal form). On ill-conditioned systems (singular or not), MINRES-QLP can give more accurate solutions than MINRES. We derive preconditioned MINRES-QLP, new stopping rules, and better estimates of the solution and residual norms, the matrix norm, and the condition number.

In the second part of our talk, we apply MINRES-QLP with and without two-sided preconditioning to Gaussian radial basis function (RBF) interpolation problems; the root-mean-square error curves against the shape parameter in our examples are smooth and do not show the Runge phenomenon often observed. We attribute the results to the inherent regularization properties of MINRES-QLP. A challenge of RBF interpolation with scattered data is to use non-standard kernels. MINRES-QLP is a natural choice of solver in RBF interpolation with non-positive definite functions. We will demonstrate with numerical examples.

The first part of this talk is joint work with Michael Saunders and Chris Paige.

Event Topic:

Computational Mathematics & Statistics