An algebraic multigrid method for high order time-discretizations of the div-grad and the curl-curl equations

We present an algebraic multigrid algorithm for fully coupled implicit Runge–Kutta and Boundary Value Method time-discretizations of the div-grad and curl-curl equations. The algorithm uses a blocksmoother and a multigrid hierarchy derived from the hierarchy built by any algebraic multigrid algorithm for the stationary version of the problem. By a theoretical analysis and numerical experiments, we show that the convergence is similar to or better than the convergence of the scalar algebraic multigrid algorithm on which it is based. The algorithm benefits from several possibilities for implementation optimization. This results in a computational complexity which, for a modest number of stages, scales almost linearly as a function of the number of variables.     

Multigrid method for nonlinear integral equations

In this paper, we introduce a multigrid method for solving the nonliear Urysohn integral equation. The algorithm is derived from a discrete resolvent equation which approximates the continuous resolvent equation of the nonlinear Urysohn integral equation. The algorithm is mathematically equivalent to Atkinson’s adaptive twogrid iteration. But the two are different computationally. We show the convergence of the algorithm and its equivalence to Atkinson’s adaptive twogrid iteration. In our numerical example, we compare our algorithm to other multigrid methods for solving the nonliear Urysohn integral equation including the nonlinear multigrid method introduced by Hackbush.     

Comparison of Fast Iterative Methods for Symmetric Systems

The multigrid method is compared to ICCG/MICCG methods for solvingsymmetric systems of linear equations arising from approximationsto differential equations with jump discontinuities in the coefficients.An optimal multigrid algorithm for these types of problems isdeveloped. It includes pattern relaxation and acceleration.Optimization of ICCG/MICCG algorithms is investigated. Thisincludes the effect of adding extra (up to ten) bands to theapproximate factorization and of different grid ordering schemes.Numerical results are presented comparing the scalar work ofthe algorithms. For large problems the multigrid algorithm issuperior. The optimal multigrid scheme can be highly vectorized.     

Single-level multigrid

A single-level multigrid algorithm is developed in which coarse-grid correction is performed on the fine grid. This negates the need for coarse grid storage allocation resulting in easy programmability. The algorithm differs from unigrid in that it mimics multigrid V(0, v) cycles which effectively overcomes the inefficiency of the unigrid technique. The single-level algorithm is therefore both easy to program and efficient. It is illustrated by two numerical examples and compared with unigrid and conventional multigrid.     

Multigrid applications to three-dimensional elliptic coordinate generation

The multigrid algorithm was applied to solve the coupled set of elliptic quasilinear partial differential equations associated with three-dimensional coordinate generation. The results indicate that the multigrid scheme is more than twice as fast as conventional relaxation schemes on moderate-size grids. Convergence factors of order 0.90 per work unit were achieved on 36,000-point grids. The paper covers the form of transformation, develops the set of generation equations, and gives details on the multigrid approach used. Included are a development of the full-approximation storage scheme, details of the smoothing-rate analysis, and a section devoted to rational programming techniques applicable to the multigrid algorithm.     

Uniform Convergence of Multigrid V-Cycle on Adaptively Refined Finite Element Meshes for Elliptic Problems with Discontinuous Coefficients

The multigrid V-cycle methods for adaptive finite element discretizations of two-dimensional elliptic problems with discontinuous coefficients are considered. Under the conditions that the coefficient is quasi-monotone up to a constant and the meshes are locally refined by using the newest vertex bisection algorithm, some uniform convergence results are proved for the standard multigrid V-cycle algorithm with Gauss-Seidel relaxations performed only on new nodes and their immediate neighbours. The multigrid V-cycle algorithm uses $\mathcal{O}(N)$ operations per iteration and is optimal.     

Modification of algebraic multigrid for effective GPGPU-based solution of nonstationary hydrodynamics problems

We present modification of algebraic multigrid algorithm for effective GPGPU-based solution of nonstationary hydrodynamics problems. The modification is easy to implement and allows us to reduce number of times when the multigrid setup is performed, thus saving up to 50% of computation time with respect to unmodified algorithm.     

A Cascadic Multigrid Algorithm for Computing the Fiedler Vector of Graph Laplacians

In this paper, we develop a cascadic multigrid algorithm for fast computation of the Fiedler vector of a graph Laplacian, namely, the eigenvector corresponding to the second smallest eigenvalue. This vector has been found to have applications in fields such as graph partitioning and graph drawing. The algorithm is a purely algebraic approach based on a heavy edge coarsening scheme and pointwise smoothing for refinement. To gain theoretical insight, we also consider the related cascadic multigrid method in the geometric setting for elliptic eigenvalue problems and show its uniform convergence under certain assumptions. Numerical tests are presented for computing the Fiedler vector of several practical graphs, and numerical results show the efficiency and optimality of our proposed cascadic multigrid algorithm.     

Fourier-Laplace analysis of the multigrid waveform relaxation method for hyperbolic equations

The multigrid waveform relaxation (WR) algorithm has been fairly studied and implemented for parabolic equations. It has been found that the performance of the multigrid WR method for a parabolic equation is practically the same as that of multigrid iteration for the associated steady state elliptic equation. However, the properties of the multigrid WR method for hyperbolic problems are relatively unknown. This paper studies the multigrid acceleration to the WR iteration for hyperbolic problems, with a focus on the convergence comparison between the multigrid WR iteration and the multigrid iteration for the corresponding steady state equations. Using a Fourier-Laplace analysis in two case studies, it is found that the multigrid performance on hyperbolic problems no longer shares the close resemblance in convergence factors between the WR iteration for parabolic equations and the iteration for the associated steady state equations.     

WEB-Spline–Based Multigrid Methods for the Stationary Stokes Problem

We discuss a multigrid technique in solving a large system of linear algebraic equations arising in the approximation of Stokes equations by a new strategy based on weighted extended B-spline (WEB-spline) methods. Three types of WEB-spline–based Stokes elements satisfying the inf-sup condition are considered. First for a linear-constant type of Stokes element, we give the detailed multigrid algorithm and its convergence proof. The convergence proof of the multigrid algorithm for a bubble-stabilized WEB-spline–based Stokes element is dealt with separately. Multigrid method in the case of bubble-condensed variational form is simplified using the techniques from the bubble-stabilized case.     

多重网格法和自适应算法的组合及其对非线性Schrdinger方程的应用

在解非线性的进化型偏微分方程时,为了数值计算的稳定性常常采用无条件稳定的隐式差分格式.这样会引起两个问题:一是要解线性甚至非线性的代数方程组,这是费时间的;另一是在解代数方程组时,迭代法的收敛性依赖于时间步长,特别是非线性迭代的收敛性会对时间步长加以严格的限制.     

MORTAR型旋转Q_1元的多重网格方法

本文讨论了mortar型旋转Q_1元的多重网格方法.证明了W循环的多重网格法是最优的,即收敛率与网格尺寸及层数无关.同时给出了一种可变的V循环多重网格算法,得到了一个条件数一致有界的预条件子.最后,数值试验验证了我们的理论结果.     

The analysis of multigrid algorithms for cell centered finite difference methods

In this paper, we examine multigrid algorithms for cell centered finite difference approximations of second order elliptic boundary value problems. The cell centered application gives rise to one of the simplest non-variational multigrid algorithms. We shall provide an analysis which guarantees that the W-cycle and variable V-cycle multigrid algorithms converge with a rate of iterative convergence which can be bounded independently of the number of multilevel spaces. In contrast, the natural variational multigrid algorithm converges much more slowly.     

Multigrid transfers for nonsymmetric systems based on Schur complements and Galerkin projections

A framework is proposed for constructing algebraic multigrid transfer operators suitable for nonsymmetric positive definite linear systems. This framework follows a Schur complement perspective as this is suitable for both symmetric and nonsymmetric systems. In particular, a connection between algebraic multigrid and approximate block factorizations is explored. This connection demonstrates that the convergence rate of a two‐level model multigrid iteration is completely governed by how well the coarse discretization approximates a Schur complement operator. The new grid transfer algorithm is then based on computing a Schur complement but restricting the solution space of the corresponding grid transfers in a Galerkin‐style so that a far less expensive approximation is obtained. The final algorithm corresponds to a Richardson‐type iteration that is used to improve a simple initial prolongator or a simple initial restrictor. Numerical results are presented illustrating the performance of the resulting algebraic multigrid method on highly nonsymmetric systems. Copyright © 2013 John Wiley & Sons, Ltd.     

A Rayleigh quotient minimization algorithm based on algebraic multigrid

This paper presents a new algebraic extension of the Rayleigh quotient multigrid (RQMG) minimization algorithm to compute the smallest eigenpairs of a symmetric positive definite pencil ( A , M ). Earlier versions of RQMG minimize the Rayleigh quotient over a hierarchy of geometric grids. We replace the geometric mesh information with the algebraic information defined by an algebraic multigrid preconditioner. At each level, we minimize the Rayleigh quotient with a block preconditioned algorithm. Numerical experiments illustrate the efficiency of this new algorithm to compute several eigenpairs. Copyright © 2007 John Wiley & Sons, Ltd.     

Some numerical experiments with multigrid methods on Shishkin meshes

Piecewise uniform meshes introduced by Shishkin, are a very useful tool to construct robust and efficient numerical methods to approximate the solution of singularly perturbed problems. For small values of the diffusion coefficient, the step size ratios, in this kind of grids, can be very large. In this case, standard multigrid methods are not convergent. To avoid this troublesome, in this paper we propose a modified multigrid algorithm, which works fine on Shishkin meshes. We show some numerical experiments confirming that the proposed multigrid method is convergent, and it has similar properties that standard multigrid for classical elliptic problems.     

Accelerated multigrid high accuracy solution of the convection-diffusion equation with high Reynolds number

A fourth-order compact finite difference scheme is employed with the multigrid algorithm to obtain highly accurate numerical solution of the convection-diffusion equation with very high Reynolds number and variable coefficients. The multigrid solution process is accelerated by a minimal residual smoothing (MRS) technique. Numerical experiments are employed to show that the proposed multigrid solver is stable and yields accurate solution for high Reynolds number problems. We also show that the MRS acceleration procedure is efficient and the acceleration cost is negligible. © 1997 John Wiley & Sons, Inc.     

Multigrid for the mortar element method for P1 nonconforming element

In this paper, a multigrid algorithm is presented for the mortar element method for P1 nonconforming element. Based on the theory developed by Bramble, Pasciak, Xu in [5], we prove that the W-cycle multigrid is optimal, i.e. the convergence rate is independent of the mesh size and mesh level. Meanwhile, a variable V-cycle multigrid preconditioner is constructed, which results in a preconditioned system with uniformly bounded condition number. Received May 11, 1999 / Revised version received April 1, 2000 / Published online October 16, 2000     

双参数Morley有限元多重网格法

1、引言 多重网格方法是求解偏微分方程的高效快速算法,在实际中得到广泛应用．[2][6]中考察了Morley元的多重网格方法,并用于双调和方程问题。     

A new method based on SOM network to generate coarse meshes for overlapping unstructured multigrid algorithm

A new method to generate coarse meshes for overlapping unstructured multigrid algorithm based on self-organizing map (SOM) neural network is presented in this paper. The application of SOM neural network can overcome some limitations of conventional methods and which is designed to pursuit the best structure relation between fine and coarse unstructured meshes with the object to ensure robust convergence for overlapping unstructured multigrid algorithm. Besides, this method can automate the generation of unstructured meshes and is suitable for both two and three dimensions conditions.