Multifrontal parallel distributed symmetric and unsymmetric solvers (Q1574349)

The paper deals with the multifrontal direct methods for the solution of both symmetric and unsymmetric systems of sparse linear algebraic equations based on the \(LU\) factorization described for instance by \textit{P. R. Amestoy} et al. [Int. J. Supercomputer Appl. 3, 41-59 (1989)]. In both cases, three subsequent phases are applied. The analysis phase produces both an ordering and an assembly tree. The numerical factorization phase results in a dense (frontal) submatrix assembled at each node of the tree using data from the original matrix and the children of the node. Pivots can be selected within a submatrix of the frontal matrix and performed eliminations. The resulting factors are stored for use in the solution phase. The Schur complement (the contribution block) is passed to the parent node for assembly at that node. In the unsymmetric case, threshold pivoting is used to maintain numerical stability so that it is possible that the pivots selected in the analysis phase are unsuitable. It may result in data structures different from those forecast by the analysis. This implies the need to allow dynamic scheduling. A new parallel asynchronous algorithm with dynamic scheduling is presented to overcome this problem. Dynamic scheduling is required also for symmetric case to solve problems that are not positive definite. The main algorithmic choices are discussed. Both implementation issues and the performance of the \(LDL^T\) and \(LU\) factorizations are included. The efficiency of the method illustrate extensive numerical experiments performed on an IBM SP2 on the set of both symmetric and unsymmetric test problems.