ISSN:
1573-2894
Schlagwort(e):
parallel computing
;
interior point methods
;
linear programming
;
multicommodity flow problems
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Notizen:
Abstract An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF00253804
Permalink