Parallel point- and domain-oriented multilevel methods for elliptic PDE's on workstation networks (Q1919377)

The authors construct parallel multilevel block Gauss-Seidel-type iterative solvers for the semidefinite symmetric system \(L^Eu^E=f^E\) arizing from the Galerkin discretization of symmetric second-order elliptic variational problems by means of the multilevel ``basis'' (= generating system), where \(L^E = S^TL^BS\), \(f^E = S^Tf^B\), \(L^B\) is the nodal basis stiffness matrix, \(f^B\) is the nodal basis load vector, and \(S\) denotes the transformation from the nodal basis into the generating system. The levelwise ordering of the unknown results in level-block partitioning of \(L^E\). The well-known \(BPX\)-preconditioner can be written in the form \(BPX=S (D^E)^{-1}S^T\), where \(D^E= \text{diag} (L^E)\). Now, one easily observes that \(D^E\) is a good preconditioner for \(L^E\) because the (generalized) relative condition number \(\kappa ((D^E)^{-1} L^E)= \kappa (BPX L^B) = O(1)\). Therefore, the convergence rate of the Jacobi-preconditioned conjugate gradient method or even the Gauss-Seidel-iteration applied to \(L^Eu^E = f^E\) is independent of the discretization parameter. This holds for all possible Gauss-Seidel traversal orderings. The authors use this fact in order to change the traversal ordering in such a way that the number of setup steps depends only on the number of processors and not on the number of levels like for the \(BPX\)- and multigrid methods. The authors propose to use either a point-oriented ordering or a domain-oriented ordering. The numerical experiments show that the methods proposed are well suited for workstation clusters where the setup time plays an essential role.