Optimization Online


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

Lukas Schork(L.Schork***at***ed.ac.uk)
Jacek Gondzio(J.Gondzio***at***ed.ac.uk)

Abstract: 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.

Keywords: sparse LU update, permutation to triangular form

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: Technical Report ERGO-17-002, University of Edinburgh

Download: [PDF]

Entry Submitted: 07/07/2017
Entry Accepted: 07/07/2017
Entry Last Modified: 07/07/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society