A Note on Matrix Reordering for Linear System Solutions by Iterative Methods in Interior Point Methods

W. Rodrigues, Marta Velazco () and A. R. L. Oliveira
Additional contact information
W. Rodrigues: UNIFACCAMP
Marta Velazco: UNIFACCAMP
A. R. L. Oliveira: IMECC-UNICAMP

Chapter Chapter 10 in Operations Research Proceedings 2022, 2023, pp 79-85 from Springer

Abstract: Abstract The linear systems arising from interior point methods (IPM) for linear programming are solved using the preconditioned conjugate gradient method (PCG). Two preconditioners are adopted: the controlled Cholesky factorization (CCF) of the normal equations system and the splitting preconditioner. The CCF performance depends upon the previous reordering of the linear programming constraint matrix rows. A comparison among two different reordering methods is performed in order to verify the most suitable one for this approach. Variants of nested dissection (ND) and the minimum degree (MD) are among the considered heuristics. Computational experiments with large-scale linear programming problems from several collection sets are performed.

Keywords: Linear programming; Interior point methods; Preconditioner; Reordering; Nested dissection (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:lnopch:978-3-031-24907-5_10

Ordering information: This item can be ordered from
http://www.springer.com/9783031249075

DOI: 10.1007/978-3-031-24907-5_10

Access Statistics for this chapter

More chapters in Lecture Notes in Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().