Permuting Spiked Matrices to Triangular Form and its Application to the Forrest-Tomlin Update

Technical Report ERGO-17-002

L. Schork and J. Gondzio

This paper is concerned with the problem of permuting a spiked matrix to triangular form. A spiked matrix results from changing one column or one row in a triangular matrix. In this paper we focus on changing one column in an upper triangular matrix. Spiked matrices arise in updating the LU factors of a matrix after a column change. The LU update methods of Bartels and Golub and Forrest and Tomlin use algebraic operations to transform a spiked matrix to triangular form. We present an LU update method which does the transformation by permutation alone whenever this is possible and falls back to the Forrest-Tomlin update otherwise.

Key words: sparse LU update, permutation to triangular form.

PDF ERGO-17-002.pdf.

Written: July 7, 2017.