View in EDS

Parallel computational issues of an interior point method for solving large bound-constrained quadratic programming problems

Saved in:
Bibliographic Details
Title: Parallel computational issues of an interior point method for solving large bound-constrained quadratic programming problems
Authors: D’Apuzzo, M.1,2 marco.dapuzzo@unina2.it, Marino, M.2,3
Source: Parallel Computing. Apr2003, Vol. 29 Issue 4, p467. 17p.
Subjects: Quadratic programming, Linear algebra
Abstract: This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning the solution of the linear system arising at each step of the considered algorithm, we use an iterative approach based on the conjugate gradient method and on a block diagonal preconditioning technique. Moreover, we apply an incomplete Cholesky factorization with limited memory into each block, in order to put together the high degree of parallelism of diagonal preconditioning techniques and the greater effectiveness of incomplete factorizations procedures. The goal is to obtain an efficient parallel interior point solver for general sparse problems. Results of computational experiments carried out on an IBM SP parallel system by using randomly generated very sparse problems without a particular structure are presented. Such results show that the considered inner iterative approach allows to obtain a constant CPU time reduction as the number of processors used increases. [Copyright &y& Elsevier]
Copyright of Parallel Computing is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:This paper deals with a parallel implementation of an interior point algorithm for solving sparse convex quadratic programs with bound constraints. The parallelism is introduced at the linear algebra level. Concerning the solution of the linear system arising at each step of the considered algorithm, we use an iterative approach based on the conjugate gradient method and on a block diagonal preconditioning technique. Moreover, we apply an incomplete Cholesky factorization with limited memory into each block, in order to put together the high degree of parallelism of diagonal preconditioning techniques and the greater effectiveness of incomplete factorizations procedures. The goal is to obtain an efficient parallel interior point solver for general sparse problems. Results of computational experiments carried out on an IBM SP parallel system by using randomly generated very sparse problems without a particular structure are presented. Such results show that the considered inner iterative approach allows to obtain a constant CPU time reduction as the number of processors used increases. [Copyright &y& Elsevier]
ISSN:01678191
DOI:10.1016/S0167-8191(03)00017-6