Parallel point- and domain-oriented multilevel methods for elliptic PDE's on workstation networks
type: Item
instance of: scholarly article
title: Parallel point- and domain-oriented multilevel methods for elliptic PDE's on workstation networks
zbMATH Open document ID: 0858.65122
DOI: 10.1016/0377-0427(95)00195-6
author: T. Neunhoeffer
author: Michael Griebel
published in: Journal of Computational and Applied Mathematics
publication date: 1997-03-11T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65N55
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65Y10
Mathematics Subject Classification ID: 35J25
Mathematics Subject Classification ID: 65Y05
Mathematics Subject Classification ID: 65N30
zbMATH DE Number: 908327
zbMATH Keywords: workstation networks
zbMATH Keywords: finite element
zbMATH Keywords: multilevel preconditioning
zbMATH Keywords: parallel algorithms
zbMATH Keywords: \(BPX\)-preconditioner
zbMATH Keywords: multilevel block Gauss-Seidel-type iterative solvers
zbMATH Keywords: semidefinite symmetric system
zbMATH Keywords: Galerkin discretization
zbMATH Keywords: second-order elliptic variational problems
zbMATH Keywords: condition number
zbMATH Keywords: convergence
zbMATH Keywords: Jacobi-preconditioned conjugate gradient method
zbMATH Keywords: multigrid methods
zbMATH Keywords: numerical experiments
reviewed by: Ulrich Langer
MaRDI profile type: Publication
full work available at URL: 0377-0427(95)00195-6
OpenAlex ID: W1990786953
cites work: Q5203615
cites work: Nested Dissection of a Regular Finite Element Mesh
cites work: Q3139619
cites work: Multilevel Algorithms Considered as Iterative Methods on Semidefinite Systems
cites work: Q4840187
cites work: Parallel Domain-Oriented Multilevel Methods
cites work: On the abstract theory of additive and multiplicative Schwarz algorithms
cites work: Multigrid methods on parallel computers—A survey of recent developments
cites work: Iterative Methods by Space Decomposition and Subspace Correction
cites work: Multilevel Schwarz methods
description: scientific article; zbMATH DE number 908327