On Solving Large Sparse Linear Systems arising from Linear Programming and Linear Regression

Venansius Baryamureeba

This Ph.D thesis in scientific computing is tailored towards solving the standard linear programming problem and the standard linear regression problem. 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 function discussed. 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

Contact: [email protected]

[DVI] [PS] [IP PAGE] [SEARCH AGAIN]