Performance of the Algebraic Multilevel Iteration Method on massively parallel computer architectures

Maya G. Neytcheva Faculty of Mathematics and Informatics Catholic University, Toernooiveld, 6525 ED Nijmegen, The Netherlands

                             e-mail: neytchevsci.kun.nl

This presentation shows our viewpoint about criteria to advocate a numerical solution method to be efficient on a parallel computer architecture. It focuses on the efficient massively parallel implementation of a class of multilevel methods, namely, the Algebraic Multilevel Iteration (AMLI) methods. The AMLI methods fit into the general framework of block-incomplete factorizations used to construct a preconditioner to a given matrix. Here, the full block factorized or multiplicative form of these methods is considered, originally derived in [1] and [2]. To sketch the method, when applied to linear selfadjoint second order elliptic partial differential equations, let Ax = b be an algebraic system derived by finite differences or finite elements from the differential equation. AMLI is a recursive procedure for constructing a preconditioner M for A which replaces the solution of a system with the preconditioning matrix by a sequence of subproblems to be solved on some hierarchy of levels. The levels are algebraically defined and may or may not be related to levels of consecutive grid refinements of the discretized problem. In general the levels are based on a certain decomposition of the matrix graph −Ω(N, S) of A = [a_{ij}]_{i,j=1}^{n} where N is the corresponding set of nodes (vertices) and S is the set of edges (i, j), such that (i, j) ∈ S if and only if a_{ij} ≠ 0. A matrix A^{(k)} is associated with each level k. The preconditioner M is implicitly defined, based on a two-by-two block partitioning of the matrices A^{(k)}, for example, as follows:

M^{(k+1)} = [\begin{matrix}B_{11}^{(k+1)^{−1}} & 0 \\ A_{21}^{(k+1)} & I \end{matrix}] [\begin{matrix}I & B_{11}^{(k+1)}A_{12}^{(k+1)} \\ 0 & S̃^{(k)} \end{matrix}] for k = k_{0}, k_{0} + 1, … ℓ−1,

where M^{(k_{0})} = A^{(k_{0})}. B_{11}^{(k+1)} is a proper approximation of the inverse of A_{11}^{(k+1)} and S̃^{(k)} = A^{(k)} [I − P_{ν_{k}}(M^{(k)^{−1}}A^{(k)})]^{−1} is a matrix polynomial of degree ν_{k} which can vary with the level number. One action of M^{−1} ≡ M^{(ℓ)}^{−1} on a vector requires only matrix × vector operations and acts recursively on the different levels depending on the degree of P_{ν}(t). This matrix polynomial is the means to achieve the desired spectral equivalence of the preconditioner with the original matrix. As it was shown in [3], it is sufficient to use a polynomial of degree higher that one only on some levels. However, as it turns out, P (t) = 1 − t (referred to as the V -cycle) is to be recommended in practice.

Although proven to possess (nearly) optimal order of computational complexity and rate of convergence, similarly to other multilevel methods, when implemented straightforwardly on massively parallel computer architectures, the AMLI methods suffer from idleness of processors and dominating communication overhead when performing on the coarser levels. Recently (see for example [4]) it was shown that there is a very simple remedy to cure simultaneously both above mentioned drawbacks. The idea is to choose the coarsest level k_{0} as fine as possible and solve the remaining system using some other solution method. The coarsest level number k_{0} can be computed as a function of the total number of levels ℓ and the cost to solve a system with A^{(k_{0})} by some chosen solution method in such a way that both the optimal computational complexity and (nearly) optimal rate of convergence will be preserved. At the same time, due to the fact that k_{0} is close to ℓ (for example, for the V - cycle k_{0} = ⌈\frac{2}{3}ℓ⌉ for 2-D probems and k_{0} = ⌈\frac{3}{4}ℓ⌉ for 3-D probems) the number of degrees of freedom n_{k_{0}} is large enough to avoid idleness of the processing elements and the distances to communicate over are kept short which keeps the amount of the required communications bounded. The modification is referred to as the short AMLI method. Being a V -cycle algorithm, the latter method is not of optimal order of computational complexity, since the number of iterations grows, although slowly, with increasing problem size. This growth can be cured to any order arbitrarily close to the optimal order using some polynomial acceleration as in [2] or using the same type of method as a coarse solver.

The short AMLI has been successfully implemented and tested on various computer architectures, such as the CM-2, CM-5, CRAY Y-MP C98 and CRAY T3D. Numerical results for a 3-D model problem on the CRAY T3D are included.

References

[1] O. Axelsson and P. Vassilevski, Algebraic Multilevel Preconditioning Methods I, Numer. Math., 56 (1989), 157-177.

[2] O. Axelsson and P. Vassilevski, Algebraic Multilevel Preconditioning Methods II, SIAM J. Numer. Anal., 27 (1990), 1569-1590.

[3] P. Vassilevski, Hybrid V -cycle Algebraic Multilevel Preconditioners, Math. Comp., 58 (1992), 489-512.

[4] O. Axelsson, M. Neytcheva, Parallel implementations of the Algebraic Multilevel Iteration Method. In J.G. Lewis (ed.), Proceedings of the Fifth SIAM Conference on Applied Linear Algebra, SIAM Philadelphia, 1994, 372-376.