A note on matrix reordering for linear system solutions by iterative methods in interior point methods. (English) Zbl 07914440
Grothe, Oliver (ed.) et al., Operations research proceedings 2022. Selected papers of the annual international conference of the German Operations Research Society (GOR), Karlsruhe, Germany, September 6–9, 2022. Cham: Springer. Lect. Notes Oper. Res., 79-85 (2023).
Summary: 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.
For the entire collection see [Zbl 1530.90007].
For the entire collection see [Zbl 1530.90007].
MSC:
| 90Cxx | Mathematical programming |
References:
| [1] | Silva, D., Velazco, M., & Oliveira, A. (2017). Influence of matrix reordering on the performance of iterative methods for solving linear systems arising from interior point methods for linear programming. Mathematical Methods of Operations Research, 85(1), 97-112. · Zbl 1362.90283 |
| [2] | Bocanegra, S., Campos, F., & Oliveira, A. (2007). Using a hybrid preconditioner for solving large-scale linear systems arising from interior point methods. Computational Optimization and Applications, 36, 149-167. · Zbl 1148.90350 |
| [3] | Velazco, M., Oliveira, A., & Campos, F. (2010). A note on hybrid preconditioners for large-scale normal equations arising from interior point methods. Optimization Methods and Software, 25(2), 321-332. · Zbl 1190.65055 |
| [4] | Benzi, M. (2002). Preconditioning techniques for large linear systems: A survey. Journal of Computational Physics, 182(2), 418-477. · Zbl 1015.65018 |
| [5] | George, A., & Liu, J. (1980). A fast implementation of the minimum degree algorithm using quotient graphs. ACM Transactions on Mathematical Software, \(6(23)\), 337-358. · Zbl 0467.65011 |
| [6] | George, A. (1973). Nested dissection of a regular finite element mesh. SIAM Journal on Numerical Analysis, 10(2), 345-363. · Zbl 0259.65087 |
| [7] | Czyzyk, J., Mehrotra, S., Wagner, M., & Wright, S. (1999). PCx an interior point code for linear programming. Optimization Methods and Software, 11(2), 397-430. · Zbl 0970.90118 |
| [8] | Karypis, G. (2015) METIS: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 5.0. http://glaros.dtc.umn.edu/gkhome/metis/metis/download |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
