Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming

This study analyzes the influence of sparse matrix reordering on the solution of linear systems arising from interior point methods for linear programming. In particular, such linear systems are solved by the conjugate gradient method with a two-phase hybrid preconditioner that uses the controlled C...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical methods of operations research (Heidelberg, Germany) Germany), 2017-02, Vol.85 (1), p.97-112
Main Authors: Silva, Daniele, Velazco, Marta, Oliveira, Aurelio
Format: Article
Language:English
Subjects:
Business and Management
Calculus of Variations and Optimal Control
Optimization
Conjugate gradient method
Heuristic
Iterative methods
Linear programming
Linear systems
Mathematical analysis
Mathematical models
Mathematics
Mathematics and Statistics
Matrices (mathematics)
Matrix methods
Methods
Operations research
Operations Research/Decision Theory
Original Article
Studies
Variables
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:This study analyzes the influence of sparse matrix reordering on the solution of linear systems arising from interior point methods for linear programming. In particular, such linear systems are solved by the conjugate gradient method with a two-phase hybrid preconditioner that uses the controlled Cholesky factorization during the initial iterations and later adopts the splitting preconditioner. This approach yields satisfactory computational results for the solution of linear systems with symmetric positive-definite matrices. Three reordering heuristics are analyzed in this study: the reverse Cuthill–McKee heuristic, the Sloan algorithm, and the minimum degree heuristic. Through numerical experiments, it was observed that these heuristics can be advantageous in terms of accelerating the convergence of the conjugate gradient method and reducing the processing time.
ISSN:1432-2994
1432-5217
DOI:10.1007/s00186-017-0571-7