Scalability aspects of parallel multigrid

This paper summarizes theoretical and practical investigations into the effect of parallelization by grid-partitioning on the performance of multigrid methods for the solution of partial differential equations on general two-dimensional domains. Particular emphasis will be placed on the algorithmic scalability for MIMD distributed memory systems. Experimental results for two Navier-Stokes test problems, presented in the last section of the paper, show that the theoretically predicted dependency of the combined numerical and parallel efficiencies of multigrid methods on the number of processors employed is in fact very weak. This leads to the conclusion that multigrid is an appropriate candidate for solving partial differential equations on massively parallel machines.     

Convergence analysis of geometrical multigrid methods for solving data-sparse boundary element equations

The convergence analysis of multigrid methods for boundary element equations arising from negative-order pseudo-differential operators is quite different from the usual finite element multigrid analysis for elliptic partial differential equations. In this paper, we study the convergence of geometrical multigrid methods for solving large-scale, data-sparse boundary element equations. In particular, we investigate multigrid methods for \(\mathcal{H}\)-matrices arising from the adaptive cross approximation to the single layer potential operator.     

Filtering algebraic multigrid and adaptive strategies

Solving linear systems arising from partial differential equations, multigrid and multilevel methods have proven optimal complexity and efficiency properties. Due to shortcomings of geometric approaches, algebraic multigrid methods have been developed. One example is the filtering algebraic multigrid method introduced by C. Wagner. This paper proposes a variant of Wagner’s method with substantially improved robustness properties. It is shown, how the class of filtering multigrid methods can be integrated into an adaptive, self-correcting framework. Numerical experiments, which are performed for a class of scaled operators, underline the results.     

A mixed strategy of combining evolutionary algorithms with multigrid methods

Multigrid methods have been proven to be an efficient approach in accelerating the convergence rate of numerical algorithms for solving partial differential equations. This paper investigates whether multigrid methods are helpful to accelerate the convergence rate of evolutionary algorithms for solving global optimization problems. A novel multigrid evolutionary algorithm is proposed and its convergence is proven. The algorithm is tested on a set of 13 well-known benchmark functions. Experiment results demonstrate that multigrid methods can accelerate the convergence rate of evolutionary algorithms and improve their performance.     

On monotone including nonlinear multigrid methods and applications

In recent years, some work has been devoted to construct multigrid methods for solving nonlinear systems which compute monotone including convergent sequences of sub- and supersolutions. Mainly with regard to the numerical solution of quasilinear partial differential equations we improve and generalize some of the existing results. In this paper we show that the monotone enclosure of the multigrid method follows from the monotone enclosure of the smoother. The theoretical results are confirmed by examples of realistic problems.     

Formulation and multigrid solution of Cauchy-Riemann optimal control problems

The formulation of optimal control problems governed by Cauchy-Riemann equations is presented. A distributed control mechanism through divergence and curl sources is considered with the boundary conditions of mixed type. A Lagrange multiplier framework is introduced to characterize the solution to Cauchy-Riemann optimal control problems as the solution of an optimality system of four first-order partial differential equations and two optimality conditions. To solve the optimality system, staggered grids and multigrid methods are investigated. It results that staggered grids provide a natural collocation of the optimization variables and second-order accurate solutions are obtained. The proposed multigrid scheme is based on a coarsening by a factor of three that results in a nested hierarchy of staggered grids. On these grids a distributed-Gauss-Seidel and gradient-based smoothing scheme is employed. Results of numerical experiments validate the proposed optimal control formulation and demonstrate the effectiveness of the staggered-grids multigrid solution procedure.     

Image analysis using multigrid relaxation methods

Image analysis problems, posed mathematically as variational principles or as partial differential equations, are amenable to numerical solution by relaxation algorithms that are local, iterative, and often parallel. Although they are well suited structurally for implementation on massively parallel, locally interconnected computational architectures, such distributed algorithms are seriously handi capped by an inherent inefficiency at propagating constraints between widely separated processing elements. Hence, they converge extremely slowly when confronted by the large representations of early vision. Application of multigrid methods can overcome this drawback, as we showed in previous work on 3-D surface reconstruction. In this paper, we develop multiresolution iterative algorithms for computing lightness, shape-from-shading, and optical flow, and we examine the efficiency of these algorithms using synthetic image inputs. The multigrid methodology that we describe is broadly applicable in early vision. Notably, it is an appealing strategy to use in conjunction with regularization analysis for the efficient solution of a wide range of ill-posed image analysis problems.     

The auxiliary space method and optimal multigrid preconditioning techniques for unstructured grids

An abstract framework ofauxiliary space method is proposed and, as an application, an optimal multigrid technique is developed for general unstructured grids. The auxiliary space method is a (nonnested) two level preconditioning technique based on a simple relaxation scheme (smoother) and an auxiliary space (that may be roughly understood as a nonnested coarser space). An optimal multigrid preconditioner is then obtained for a discretized partial differential operator defined on an unstructured grid by using an auxiliary space defined on a more structured grid in which a furthernested multigrid method can be naturally applied. This new technique makes it possible to apply multigrid methods to general unstructured grids without too much more programming effort than traditional solution methods. Some simple examples are also given to illustrate the abstract theory and for instance the Morley finite element space is used as an auxiliary space to construct a preconditioner for Argyris element for biharmonic equations. Some numerical results are also given to demonstrate the efficiency of using structured grid for auxiliary space to precondition unstructured grids.     

On the numerical modeling of convection-diffusion problems by finite element multigrid preconditioning methods

During the last decades, multigrid methods have been extensively used in order to solve large scale linear systems derived from the discretization of partial differential equations using the finite difference method. The effectiveness of the multigrid method can be also exploited by using the finite element method. Finite Element Approximate Inverses in conjunction with Richardon’s iterative method could be used as smoothers in the multigrid method. Thus, a new class of smoothers based on approximate inverses can be derived. Effectiveness of explicit approximate inverses relies in the fact that they are close approximants to the inverse of the coefficient matrix and are fast to compute in parallel. Furthermore, the proposed class of finite element approximate inverses in conjunction with the explicit preconditioned Richardson method yield improved results against the classic smoothers such as Jacobi method. Moreover, a dynamic relaxation scheme is proposed based on the Dynamic Over/Under Relaxation (DOUR) algorithm. Furthermore, results for multigrid preconditioned Krylov subspace methods, such as GMRES(res), IDR(s) and BiCGSTAB based on approximate inverse smoothing and a dynamic relaxation technique are presented for the steady-state convection-diffusion equation.     

An EXCMG accelerated multiscale multigrid computation for 3D Poisson equation

Multiscale multigrid (MSMG) method is an effective computational framework for efficiently computing high accuracy solutions for elliptic partial differential equations. In the current MSMG method, compared to the CPU cost on computing sixth-order solutions by applying extrapolation and other techniques on two fourth-order solutions from different scales grids, much more CPU time is spent on computing fourth-order solutions themselves on coarse and fine grids, particularly for high-dimensional problems. Here we propose to embed extrapolation cascadic multigrid (EXCMG) method into the MSMG framework to accelerate the whole process. Numerical results on 3D Poisson equations show that the new EXCMG–MSMG method is more efficient than the existing MSMG method and the EXCMG method for sixth-order solution computation.     

Nested multigrid methods for time-periodic,parabolic optimal control problems

We present a nested multigrid method to optimize time-periodic, parabolic, partial differential equations (PDE). We consider a quadratic tracking objective with a linear parabolic PDE constraint. The first order optimality conditions, given by a coupled system of boundary value problems can be rewritten as an Fredholm integral equation of the second kind, which is solved by a multigrid of the second kind. The evaluation of the integral operator consists of solving sequentially a boundary value problem for respectively the state and the adjoints. Both problems are solved efficiently by a time-periodic space-time multigrid method.     

自顶向下聚集型代数多重网格预条件的边权选择

针对基于图划分的自顶向下聚集型代数多重网格预条件,考察了利用METIS软件包进行多重网格构建的方法,并就该软件包只能处理整型权重,不能处理实型权重的问题,提出了一种将实型边权转化为整型边权的有效方法。之后将这种转化方法应用到METIS图划分软件中的边权选择,并用其给出了对自顶向下聚集型代数多重网格预条件的一种改进算法。通过对二维与三维模型偏微分方程离散所得稀疏线性方程组的数值实验表明,带边权的改进型算法大大提高了多重网格预条件共轭斜量法的迭代效率,特别是对各向异性问题,改进效果更加显著。     

A real-time multigrid finite hexahedra method for elasticity simulation using CUDA

We present a multigrid approach for simulating elastic deformable objects in real time on recent NVIDIA GPU architectures. To accurately simulate large deformations we consider the co-rotated strain formulation. Our method is based on a finite element discretization of the deformable object using hexahedra. It draws upon recent work on multigrid schemes for the efficient numerical solution of partial differential equations on such discretizations. Due to the regular shape of the numerical stencil induced by the hexahedral regime, and since we use matrix-free formulations of all multigrid steps, computations and data layout can be restructured to avoid execution divergence of parallel running threads and to enable coalescing of memory accesses into single memory transactions. This enables to effectively exploit the GPU’s parallel processing units and high memory bandwidth via the CUDA parallel programming API. We demonstrate performance gains of up to a factor of 27 and 4 compared to a highly optimized CPU implementation on a single CPU core and 8 CPU cores, respectively. For hexahedral models consisting of as many as 269,000 elements our approach achieves physics-based simulation at 11 time steps per second.     

Parallelism in multigrid methods: How much is too much?

Multigrid methods are powerful techniques to accelerate the solution of computationally-intensive problems arising in a broad range of applications. Used in conjunction with iterative processes for solving partial differential equations, multigrid methods speed up iterative methods by moving the computation from the original mesh covering the problem domain through a series of coarser meshes. But this hierarchical structure leaves domain-parallel versions of the standard multigrid algorithms with a deficiency of parallelism on coarser grids. To compensate, several parallel multigrid strategies with more parallelism, but also more work, have been designed. We examine these parallel strategies and compare them to simpler standard algorithms to try to determine which techniques are more efficient and practical. We consider three parallel multigrid strategies: (1) domain-parallel versions of the standard V-cycle and F-cycle algorithms; (2) a multiple coarse grid algorithm, proposed by Fredrickson and McBryan, which generates several coarse grids for each fine grid; and (3) two Rosendale algorithm, which allow computation on all grids simultaneously. We study an elliptic model problem on simple domains, discretized with finite difference techniques on block-structured meshes in two or three dimensions with up to 10⁶ or 10⁹ points, respectively. We analyze performance using three models of parallel computation: the PRAM and two bridging models. The bridging models reflect the salient characteristics of two kinds of parallel computers: SIMD fine-grain computers, which contain a large number of small (bitserial) processors, and SPMD medium-grain computers, which have a more modest number of powerful (single chip) processors. Our analysis suggests that the standard algorithms are substantially more efficient than algorithms utilizing either parallel strategy. Both parallel strategies need too much extra work to compensate for their extra parallelism. They require a highly impractical number of processors to be competitive with simpler, standard algorithms. The analysis also suggests that the F-cycle, with the appropriate optimization techniques, is more efficient than the V-cycle under a broad range of problem, implementation, and machine characteristics, despite the fact that it exhibits even less parallelism than the V-cycle. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR-8920505, and the Office of Naval Research, Contract No. N0014-91-J-1463.     

An explicit Chebyshev pseudospectral multigrid method for incompressible Navier-Stokes equations

The two-dimensional steady incompressible Navier-Stokes equations in the form of primitive variables have been solved by Chebyshev pseudospectral method. The pressure and velocities are coupled by artificial compressibility method and the NS equations are solved by pseudotime method with an explicit four-step Runge-Kutta integrator. In order to reduce the computational time cost, we propose the spectral multigrid algorithm in full approximation storage (FAS) scheme and implement it through V-cycle multigrid and full multigrid (FMG) strategies. Four iterative methods are designed including the single grid method; the full single grid method; the V-cycle multigrid method and the FMG method. The accuracy and efficiency of the numerical methods are validated by three test problems: the modified one-dimensional Burgers equation; the Taylor vortices and the two-dimensional lid driven cavity flow. The computational results fit well with the exact or benchmark solutions. The spectral accuracy can be maintained by the single grid method as well as the multigrid ones, while the time cost is greatly reduced by the latter. For the lid driven cavity flow problem, the FMG is proved to be the most efficient one among the four iterative methods. A speedup of nearly two orders of magnitude can be achieved by the three-level multigrid method and at least one order of magnitude by the two-level multigrid method.     

On efficient multigrid software for elliptic problems on rectangular domains

Emphasis has been laid on software development concerning ‘non-standard’ multigrid techniques as introduced by Foerster, Stüben and Trottenberg¹. The advantages of these methods result in very efficient code for the solution of elliptic problems. In comparison with fast direct methods, the multigrid solver MGOO is as good as direct solvers for model equations on rectangular domains, even better in special cases, and more generally applicable (variable coefficients).     

Monotonicity preserving multigrid time stepping schemes for conservation laws

In this paper, we propose monotonicity preserving and total variation diminishing (TVD) multigrid methods for solving scalar conservation laws. We generalize the upwind-biased residual restriction and interpolation operators for solving linear wave equations to nonlinear conservation laws. The idea is to define nonlinear restriction and interpolation based on local Riemann solutions. Theoretical analyses have been provided to analyze the monotonicity preserving and TVD properties of the resulting multigrid time stepping schemes. Numerical results are given to verify the theoretical results and demonstrate the effectiveness of the proposed schemes. Two dimensional extension is also discussed.     

Multigrid methods with space–time concurrency

Computing and Visualization in Science - We consider the comparison of multigrid methods for parabolic partial differential equations that allow space–time concurrency. With current trends in...     

A multigrid solver for Stokes control problems

Multigrid solvers for distributed optimal control problems constrained by Stokes equations are presented. The distributed velocity tracking problem is considered with Dirichlet boundary conditions. The optimality system of the control problem that results from a Lagrange multiplier framework, forms a linear system connecting the state, adjoint, and control variables. We investigate multigrid methods on staggered grids. A coarsening by a factor of three is introduced that results in a nested hierarchy of staggered grids and simplified the intergrid transfer operators. On these grids a distributive Gauss–Seidel smoothing scheme is employed. Numerical experiments are performed to validate the effectiveness and efficiency of the proposed multigrid staggered grid framework.     

An adaptive multilevel multigrid formulation for Cartesian hierarchical grid methods

A Cartesian grid method with adaptive mesh refinement and multigrid acceleration is presented for the compressible Navier-Stokes equations. Cut cells are used to represent boundaries on the Cartesian grid, while ghost cells are introduced to facilitate the implementation of boundary conditions. A cell-tree data structure is used to organize the grid cells in a hierarchical manner. Cells of all refinement levels are present in this data structure such that grid level changes as they are required in a multigrid context do not have to be carried out explicitly. Adaptive mesh refinement is introduced using phenomenon-based sensors. The application of the multilevel method in conjunction with the Cartesian cut-cell method to problems with curved boundaries is described in detail. A 5-step Runge-Kutta multigrid scheme with local time stepping is used for steady problems and also for the inner integration within a dual time-stepping method for unsteady problems. The inefficiency of customary multigrid methods on Cartesian grids with embedded boundaries requires a new multilevel concept for this application, which is introduced in this paper. This new concept is based on the following novelties: a formulation of a multigrid method for Cartesian hierarchical grid methods, the concept of averaged control volumes, and a mesh adaptation strategy allowing to directly control the number of refined and coarsened cells.