[prev] [prev-tail] [tail] [up]

#### 4.3 Smoothers and coarsest-level solvers

The smoothers implemented in MLD2P4 include the Jacobi and block-Jacobi methods, a hybrid version of the forward and backward Gauss-Seidel methods, and the additive Schwarz (AS) ones (see, e.g., [21, 22]).

The hybrid Gauss-Seidel version is considered because the original Gauss-Seidel method is inherently sequential. At each iteration of the hybrid version, each parallel process uses the most recent values of its own local variables and the values of the non-local variables computed at the previous iteration, obtained by exchanging data with other processes before the beginning of the current iteration.

In the AS methods, the index space Ωk is divided into m k subsets Ωik of size nk,i, possibly overlapping. For each i we consider the restriction operator Rik ∈ ℝnk,i×nk that maps a vector xk to the vector x ik made of the components of xk with indices in Ω ik, and the prolongation operator P ik = (R ik)T . These operators are then used to build Aik = R ikAkP ik, which is the restriction of Ak to the index space Ω ik. The classical AS preconditioner M ASk is defined as

where Aik is supposed to be nonsingular. We observe that an approximate inverse of Aik is usually considered instead of (A ik)-1. The setup of M ASk during the multilevel build phase involves

- the definition of the index subspaces Ωik and of the corresponding operators Rik (and P ik);
- the computation of the submatrices Aik;
- the computation of their inverses (usually approximated through some form of incomplete factorization).

The computation of zk = M ASkwk, with wk ∈ ℝnk, during the multilevel application phase, requires

- the restriction of wk to the subspaces ℝnk,i, i.e. w ik = R ikwk;
- the computation of the vectors zik = (A ik)-1w ik;
- the prolongation and the sum of the previous vectors, i.e. zk = ∑ i=1mkP ikz ik.

Variants of the classical AS method, which use modifications of the restriction and prolongation operators, are also implemented in MLD2P4. Among them, the Restricted AS (RAS) preconditioner usually outperforms the classical AS preconditioner in terms of convergence rate and of computation and communication time on parallel distributed-memory computers, and is therefore the most widely used among the AS preconditioners [6].

Direct solvers based on sparse LU factorizations, implemented in the third-party libraries reported in Section 3.2, can be applied as coarsest-level solvers by MLD2P4. Native inexact solvers based on incomplete LU factorizations, as well as Jacobi, hybrid (forward) Gauss-Seidel, and block Jacobi preconditioners are also available. Direct solvers usually lead to more effective preconditioners in terms of algorithmic scalability; however, this does not guarantee parallel efficiency.

[prev] [prev-tail] [front] [up]