NEW PARALLEL ALGORITHMS FOR DIRECT SOLUTION OF SPARSE LINEAR-SYSTEMS - PART II - NONSYMMETRICAL COEFFICIENT MATRIX

In Part I of this paper, we proposed a new parallel bidirectional algo rithm, based on Cholesky factorization, for the solution of sparse sym metric system of linear equations. In this paper, we propose a new par allel bidirectional algorithm, based on LU factorization, for the solu tion of general sparse system of linear equations having non-symmetric coefficient matrix. As with the sparse symmetric systems, the numeric al factorization phase of our algorithm is carried out in such a manne r that the entire back substitution component of the substitution phas e is replaced by a single step division. However, due to absence of sy mmetry, important differences arise in the ordering technique, the sym bolic factorization phase, and message passing during numerical factor ization phase. The bidirectional substitution phase for solving genera l sparse systems is the same as that for sparse symmetric systems. The effectiveness of our algorithm is demonstrated by comparing it with t he existing parallel algorithm, based on LU factorization, using exten sive simulation studies.