Skip to main content
main-content
Top

Hint

Swipe to navigate through the articles of this issue

04-03-2020 | Original Paper | Issue 1/2021

Numerical Algorithms 1/2021

Switching preconditioners using a hybrid approach for linear systems arising from interior point methods for linear programming

Journal:
Numerical Algorithms > Issue 1/2021
Authors:
Petra Maria Bartmeyer, Silvana Bocanegra, Aurelio Ribeiro Leite Oliveira
Important notes

Publisher’s note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Abstract

In general, interior point methods are successful in solving large-scale linear programming problems. Their effectiveness is determined by how fast they calculate each solution of a linear system. When solving large-scale linear systems, iterative methods are useful options since they require slightly more computational memory in each iteration and preserve the sparsity pattern of the matrix system. In this context, a common choice is the conjugate gradient method using a preconditioning strategy. Choosing a single preconditioner that fits well during all iterations of the optimization method is not an easy task, because the distribution of the eigenvalues of the system matrix may vary significantly from the first to the last iterations. In order to simplify this task, one can use different preconditioners in different iterations, in a hybrid preconditioner strategy. In the case of symmetric positive definite systems, the Controlled Cholesky Factorization achieves excellent performance for the first interior point iterations, whereas the Splitting preconditioner is very useful in the last iterations. However, since we apply a hybrid approach combining both preconditioners, it is necessary to decide when using each preconditioner. This paper addresses the critical issue of choosing between the two preconditioners of the hybrid strategy by using the condition number of the matrix system. The Ritz values obtained from the conjugate gradient method provide an approximation to the eigenvalues, which offers an estimate of the condition number. The main contribution of this research is a new heuristic to switching the preconditioners based on the estimated condition number. Numerical results for large-scale problems show that our choice to change the preconditioners adds both speed and robustness to a hybrid approach that combines the Controlled Cholesky Factorization and the Splitting preconditioner.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 58.000 Bücher
  • über 300 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Literature
About this article

Other articles of this Issue 1/2021

Numerical Algorithms 1/2021 Go to the issue

Premium Partner

    Image Credits