A locally optimized reordering algorithm and its application to a parallel sparse linear system solver (Q1343678)

A coarse-grain parallel solver for systems of linear algebraic equations with general sparse matrices by Gaussian elimination is discussed. Before the factorization two other steps are performed. A reordering algorithm is used during the first step in order to obtain a perfumed matrix with as many zero elements under the main diagonal as possible. During the second step the reordered matrix is partitioned into blocks for asynchronous parallel processing. A straightforward implementation of the reordering algorithm results in \(O(n^ 2)\) operations. By using binary trees this cost can be reduced to \(O(NZ\cdot \log n)\), where \(NZ\) is the number of non-zero elements in the matrix and \(n\) is its order. The results of some numerical experiments on parallel computers are performed.