Modified controlled Cholesky factorization for preconditioning linear systems from the interior-point method

The interior-point method solves large linear programming problems in a few iterations. Each iteration requires computing the solution to one or more linear systems. This constitutes the most expensive step of the method and reducing the time to solve these linear systems is a way of improving the m...

Full description

Saved in:
Bibliographic Details
Published in:Computational & applied mathematics 2021-06, Vol.40 (4), Article 154
Main Authors: Silva, Lino M., Oliveira, Aurelio R. L.
Format: Article
Language:English
Subjects:
Applications of Mathematics
Applied physics
Cholesky factorization
Computational mathematics
Computational Mathematics and Numerical Analysis
Conjugate gradient method
Factorization
Iterative methods
Linear programming
Linear systems
Mathematical analysis
Mathematical Applications in Computer Science
Mathematical Applications in the Physical Sciences
Mathematics
Mathematics and Statistics
Matrix methods
Preconditioning
Simplex method
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The interior-point method solves large linear programming problems in a few iterations. Each iteration requires computing the solution to one or more linear systems. This constitutes the most expensive step of the method and reducing the time to solve these linear systems is a way of improving the method’s performance. Iterative methods such as the preconditioned conjugate gradient method can be used to solve them. Incomplete Cholesky factorization can be used as a preconditioner to the problem. However, breakdowns may occur during incomplete factorizations and corrections on the diagonal may be required. This correction is accomplished by adding a positive number to diagonal elements of the linear system matrix and the factorization of the new matrix is restarted. In this work, we propose modifications to controlled Cholesky factorization to avoid or decrease the number of refactorizations of diagonally modified matrices. Computational results show that the proposed techniques can reduce the time needed for solving linear programming problems by the interior-point method.
ISSN:2238-3603
1807-0302
DOI:10.1007/s40314-021-01544-0