On Solving Large Sparse Linear Systems arising from Linear
Programming and Linear Regression
This Ph.D thesis in scientific computing is tailored towards solving
the standard linear programming problem and the standard linear
First, we pose these problems as sequences of weighted linear systems.
We discuss a combination of a direct solver and an iterative solver
for solving these sequences of weighted linear systems. For this
mixed solver approach, a class of preconditioners based on low-rank
corrections is discussed and preconditioners constructed. The choice
of the low-rank correction matrix is based on derived (theoretical)
bounds on the eigenvalues of the preconditioned matrix.
In addition, for linear programming, we suggest a globally convergent
inexact interior point algorithm. Based on this algorithm, we state a
globally convergent mixed interior point algorithm that suits the
class of preconditioners mentioned above.
Furthermore, for the case of linear regression, we discuss another
class of preconditioners based on downdating a constant factorized
matrix at every iteration. Also a new convex weighting function for
linear regression is suggested and preconditioners based on this
For both linear programming and linear regression, we give numerical
results to demonstrate the effectiveness of our approaches in solving
problems arising from these areas of scientific computing.
Apart from linear programming and linear regression, the work in this
thesis can be extended to other related areas; for example electrical
networks, elliptic boundary value problems, and structural analysis.
Ph.D Thesis, March 2000, Department of Informatics, University of
Bergen, Post Box 7800, 5020 Bergen,Norway