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.
Technical Report ERGO-17-002, University of Edinburgh