New Preconditioners for KKT Systems of Network Flow Problems (Articolo in rivista)

Type
Label
  • New Preconditioners for KKT Systems of Network Flow Problems (Articolo in rivista) (literal)
Anno
  • 2004-01-01T00:00:00+01:00 (literal)
Alternative label
  • Frangioni, A.; Gentile, C. (2004)
    New Preconditioners for KKT Systems of Network Flow Problems
    in SIAM journal on optimization (Print)
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Frangioni, A.; Gentile, C. (literal)
Pagina inizio
  • 894 (literal)
Pagina fine
  • 913 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume
  • 14 (literal)
Rivista
Note
  • ISI Web of Science (WOS) (literal)
  • Scopus (literal)
  • Mathematical Reviews on the web (MathSciNet) (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Frangioni Antonio, Università di Pisa, Dipartimento di Informatica (literal)
Titolo
  • New Preconditioners for KKT Systems of Network Flow Problems (literal)
Abstract
  • We propose a new set of preconditioners for the iterative solution, via a Preconditioned Conjugate Gradient (PCG) method, of the KKT systems that must be solved at each iteration of an Interior Point (IP) algorithm for the solution of linear Min Cost Flow (MCF) problems. These preconditioners are based on the idea of extracting a proper triangulated subgraph of the original graph which strictly contains a spanning tree. We define a new class of triangulated graphs, called \emph{Brother-Connected Trees} (BCT), and discuss some fast heuristics for finding BCTs of ``large'' weight. Computational experience shows that the new preconditioners can complement tree preconditioners, outperforming them both in iterations count and in running time on some classes of graphs. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi
Insieme di parole chiave di
data.CNR.it