In this paper we compare various parallel preconditioners such as Point-SSOR (Symmetric Successive OverRelaxation), ILU(0) (Incomplete LU) in the Wavefront ordering, ILU(0) in the Multi-color ordering, Multi-Color Block SOR (Successive OverRelaxation), SPAI (SParse Approximate Inverse) and pARMS (Parallel Algebraic Recursive Multilevel Solver) for solving large sparse linear systems arising from two-dimensional PDE (Partial Differential Equation)s on structured grids. Point-SSOR is well-known, and ILU(0) is one of the most popular preconditioner, but it is inherently serial. ILU(0) in the Wavefront ordering maximizes the parallelism in the natural order, but the lengths of the wavefronts are often nonuniform. ILU(0) in the Multi-color ordering is a simple way of achieving a parallelism of the order N, where N is the order of the matrix, but its convergence rate often deteriorates as compared to that of natural ordering. We have chosen the Multi-Color Block SOR preconditioner combined with direct sparse matrix solver, since for the Laplacian matrix the SOR method is known to have a nondeteriorating rate of convergence when used with the Multi-Color ordering. By using block version we expect to minimize the interprocessor communications. SPAI computes the sparse approximate inverse directly by least squares method. Finally, ARMS is a preconditioner recursively exploiting the concept of independent sets and pARMS is the parallel version of ARMS. Experiments were conducted for the Finite Difference and Finite Element discretizations of five two-dimensional PDEs with large meshsizes up to a million on an IBM p595 machine with distributed memory. Our matrices are real positive, i.e., their real parts of the eigenvalues are positive. We have used GMRES(m) as our outer iterative method, so that the convergence of GMRES(m) for our test matrices are mathematically guaranteed. Interprocessor communications were done using MPI (Message Passing Interface) primitives. The results show that in general ILU(0) in the Multi-Color ordering and ILU(0) in the Wavefront ordering outperform the other methods but for symmetric and nearly symmetric 5-point matrices Multi-Color Block SOR gives the best performance, except for a few cases with a small number of processors.

Given a sparse linear system, A x = b, we can solve the equivalent system P A PT y = P b, x = PT y, where P is a permutation matrix. It has been known that, for example, when P is the RCMK (Reverse Cuthill-Mckee) ordering permutation, the convergence rate of the Krylov subspace method combined with the ILU-type preconditioner is often enhanced, especially if the matrix A is highly nonsymmetric. In this paper we offer a reordering heuristic for accelerating the solution of large sparse linear systems by the Krylov subspace methods with the ILUT preconditioner. It is the LRB (Line Red/Black) ordering based on the well-known 2-point Red-Black ordering. We show that for some model-like PDE (partial differential equation)s the LRB ordered FDM (Finite Difference Method)/FEM (Finite Element Method) discretization matrices require much less fill-ins in the ILUT factorizations than those of the Natural ordering and the RCMK ordering and hence, produces a more accurate preconditioner, if a high level of fill-in is used. It implies that the LRB ordering could outperform the other two orderings combined with the ILUT preconditioned Krylov subspace method if the level of fill-in is high enough. We compare the performance of our heuristic with that of the RCMK (Reverse Cuthill-McKee) ordering. Our test matrices are obtained from various standard discretizations of two-dimensional and three-dimensional model-like PDEs on structured grids by the FDM or the FEM. We claim that for the resulting matrices the performance of our reordering strategy for the Krylov subspace method combined with the ILUT preconditioner is superior to that of RCMK ordering, when the proper number of fill-in was used for the ILUT. Also, while the RCMK ordering is known to have little advantage over the Natural ordering in the case of symmetric matrices, the LRB ordering still can improve the convergence rate, even if the matrices are symmetric.