Highly Parallel Direct Solvers for Sparse Linear Systems

点击翻译按钮获取中文摘要

Direct methods for solving sparse linear systems are because of their generality and robustness. For linear systems arising in certain applications, such as linear programming and some engineering applications, they are the only feasible methods for numerical factorization. This project is developing a scalable parallel direct solver for solving sparse symmetric-positive definite(SPD) systems of linear equations, and is investigating its utility and effectiveness in the context of linear programming problems and least square problems. A highly parallel formulation of the factorization phase of the direct solver for SPD systems has been developed. This is being extended to the other three phases (ordering, symbolic factorization and triangular system solving) of a complete scalable parallel direct solver. Parallel formulations are being investigated on a variety of hardware platforms, including traditional MPPs such as CM5 and Cray T3D, as well as clusters of DEC and IBM workstations. The parallel algorithms are being implemented in a portable form using a programming library that supports collective communication, and will be made available to researchers and practitioners elsewhere.