Maintaining LU factors of a general sparse matrix (Q1822448)

This clearly written paper describes a set of procedures which carry out the following major functions: Factor: To factorize a real \(m\times n\) sparse matrix \(A\) as \(LU\) where \(L\) is lower triangular and \(U\) is upper trapezoidal. Solve: For a given \(m\)-vector \(b\), use the \(LU\) factors to find an \(n\)- vector to satisfy \(Ax=b.\) Update: Modify \(L\) and \(U\) to obtain a new factorization when \(A\) is altered in a variety of ways. The procedures have been implemented in a set of Fortran routines named LUSOL. In the introduction the authors give examples of the areas in which the results are useful, these include the simplex method of LP and the reduced gradient method for linearly constrained optimization. Fundamental concepts and results are given in Section 2, together with comments on pivotal strategy and error analysis. This is followed by programming details and storage methods. The factorization method is the main topic in the next sections and is described as an Algol type of language. In particular the authors examine Markowitz's pivoting strategy for LU factorization. There is a discussion of the solution of sets of linear equations whose matrices are upper or lower triangular. Seven update procedures are described and include for example the replacement of a column (due to Bartels and Golub), or the addition of a row or column. The paper closes with some computational results in an LP test problem. There is a comprehensive list of references.