Fourier Analysis of Multigrid for a Model Two-Dimensional Convection-Diffusion Equation

We present a Fourier analysis of multigrid for the two-dimensional discrete convection-diffusion equation. For constant coefficient problems with grid-aligned flow and semi-periodic boundary conditions, we show that the two-grid iteration matrix can be reduced via a set of orthogonal transformations to a matrix containing individual 4×4 blocks. This enables a trivial computation of the norm of the iteration matrix demonstrating rapid convergence in the case of both small and large mesh Peclet numbers, where the streamline-diffusion discretisation is used in the latter case. We also demonstrate that these results are strongly correlated with the properties of the iteration matrix arising from Dirichlet boundary conditions. AMS subject classification (2000) 65F10, 65N22, 65N30, 65N55     

An Improvement of Multigrid Methods Using Multiple Grids on Each Layer for Parallel Computing

Multigrid methods are widely used and well studied for linear solvers and preconditioners of Krylov subspace methods. The multigrid method is one of the most powerful approaches for solving large scale linear systems;however, it may show low parallel efficiency on coarse grids. There are several kinds of research on this issue. In this paper, we intend to overcome this difficulty by proposing a novel multigrid algorithm that has multiple grids on each layer.Numerical results indicate that the proposed method shows a better convergence rate compared with the existing multigrid method.     

A Multigrid Scheme for Elliptic Constrained Optimal Control Problems

A multigrid scheme for the solution of constrained optimal control problems discretized by finite differences is presented. This scheme is based on a new relaxation procedure that satisfies the given constraints pointwise on the computational grid. In applications, the cases of distributed and boundary control problems with box constraints are considered. The efficient and robust computational performance of the present multigrid scheme allows to investigate bang-bang control problems.AMS Subject Classification: 49J20, 65N06, 65N12, 65N55Supported in part by the SFB 03 “Optimization and Control”     

Cascadic Multigrid for Finite Volume Methods for Elliptic Problems

In this paper, some effective cascadic multigrid methods are proposed for solving the large scale symmetric or nonsymmetric algebraic systems arising from the finite volume methods for second order elliptic problems. It is shown that these algorithms are optimal in both accuracy and computational complexity. Numerical experiments are reported to support our theory.     

Parallel coarse‐grid selection

Algebraic multigrid (AMG) is a powerful linear solver with attractive parallel properties. A parallel AMG method depends on efficient, parallel implementations of the coarse‐grid selection algorithms and the restriction and prolongation operator construction algorithms. In the effort to effectively and quickly select the coarse grid, a number of parallel coarsening algorithms have been developed. This paper examines the behaviour of these algorithms in depth by studying the results of several numerical experiments. In addition, new parallel coarse‐grid selection algorithms are introduced and tested. Copyright © 2007 John Wiley & Sons, Ltd.     

Multigrid method for coupled semilinear elliptic equation

This paper introduces a kind of multigrid finite element method for the coupled semilinear elliptic equations. Instead of the common way of directly solving the coupled semilinear elliptic problems on some fine spaces, the presented method transforms the solution of the coupled semilinear elliptic problem into a series of solutions of the corresponding decoupled linear boundary value problems on the sequence of multilevel finite element spaces and some coupled semilinear elliptic problems on a very low dimensional space. The decoupled linearized boundary value problems can be solved by some multigrid iterations efficiently. The optimal error estimate and optimal computational work are proved theoretically and demonstrated numerically. Moreover, the requirement of bounded second‐order derivatives of the nonlinear term in the existing multigrid method is reduced to a Lipschitz continuous condition in the proposed method.     

A Black-Box Multigrid Preconditioner for the Biharmonic Equation

We examine the convergence characteristics of a preconditioned Krylov subspace solver applied to the linear systems arising from low-order mixed finite element approximation of the biharmonic problem. The key feature of our approach is that the preconditioning can be realized using any “black-box” multigrid solver designed for the discrete Dirichlet Laplacian operator. This leads to preconditioned systems having an eigenvalue distribution consisting of a tightly clustered set together with a small number of outliers. Numerical results show that the performance of the methodology is competitive with that of specialized fast iteration methods that have been developed in the context of biharmonic problems. This revised version was published online in July 2006 with corrections to the Cover Date.     

Local Fourier Analysis of Multigrid Methods with Polynomial Smoothers and Aggressive Coarsening

We focus on the study of multigrid methods with aggressive coarsening and polynomial smoothers for the solution of the linear systems corresponding to finite difference/element discretizations of the Laplace equation. Using local Fourier analysis we determine automatically the optimal values for the parameters involved in defining the polynomial smoothers and achieve fast convergence of cycles with aggressive coarsening. We also present numerical tests supporting the theoretical results and the heuristic ideas. The methods we introduce are highly parallelizable and efficient multigrid algorithms on structured and semi-structured grids in two and three spatial dimensions.     

Quasiconcavity of a separable product of utility functions

ABSTRACT

The nontrivial problem of the quasiconcavity of a separable sum of utility functions has been studied and solved by Debreu-Koopmans and Crouzeix-Lindberg via the introduction of convexity indices. This paper studies the equivalent problem of the quasiconcavity of a separable products. This approach makes the proofs easier.     

Multigrid and multilevel methods for nonconforming elements

In this paper we study theoretical properties of multigrid algorithms and multilevel preconditioners for discretizations of second-order elliptic problems using nonconforming rotated finite elements in two space dimensions. In particular, for the case of square partitions and the Laplacian we derive properties of the associated intergrid transfer operators which allow us to prove convergence of the -cycle with any number of smoothing steps and close-to-optimal condition number estimates for -cycle preconditioners. This is in contrast to most of the other nonconforming finite element discretizations where only results for -cycles with a sufficiently large number of smoothing steps and variable -cycle multigrid preconditioners are available. Some numerical tests, including also a comparison with a preconditioner obtained by switching from the nonconforming rotated discretization to a discretization by conforming bilinear elements on the same partition, illustrate the theory.

     

Multigrid Methods for Elliptic Optimal Control Problems with Pointwise State Constraints

An elliptic optimal control problem with constraints on the state variable is considered. The Lavrentiev-type regularization is used to treat the constraints on the state variable. To solve the problem numerically, the multigrid for optimization (MGOPT) technique and the collective smoothing multigrid (CSMG) are implemented. Numerical results are reported to illustrate and compare the efficiency of both multigrid strategies.     

半线性椭圆型问题Mortar有限元逼近的瀑布型多重网格法

Mortar有限元法作为一个非协调的区域分解技术已得到许多研究者的关注(如文献[2]、[5]等)。本文对半线性椭圆型问题的Mortar有限元逼近提出了瀑布型多重网格法,并给出了此法的误差估计和计算复杂度估计定理。     

The smoothing effect of a simultaneous directions parallel method as applied to Poisson problems

By using local Fourier analysis, a simultaneous directions parallel method, which is a particular instance of the parallel fractional step algorithm, is shown to possess smoothing effects when applied to Poisson problems. The specific smoothing factor is determined and the expected factor values are found to be consistent with those obtained. The simultaneous directions approach is an advantageous alternative to other existing smoothers in the multigrid environment. © 2005 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2006     

A comparative study of efficient iterative solvers for generalized Stokes equations

We consider a generalized Stokes equation with problem parameters ξ?0 (size of the reaction term) and ν>0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka‐type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters ξ and ν. We give an overview of the main theoretical convergence results known for these methods. For a three‐dimensional problem, discretized by the Hood–Taylor ??₂–??₁ pair, we give results of numerical experiments. Copyright © 2007 John Wiley & Sons, Ltd.     

On the Smoothing Property of Multigrid Methods in the Non-symmetric Case

In this paper we present an extension of Reusken's Lemma about the smoothing property of a multigrid method for solving non-symmetric linear systems of equations. One of the consequences of this extended lemma is the verification of the smoothing property for all damping factors oϵ(0, 1). Additionally, a semi-iterative smoother is constructed which gives, in some sense, optimal smoothing rate estimates.     

关于Katai的一个猜想的证明

本文证明了：如果实值加性函数ｆ（ｎ）满足条件‖ｆ（ｎ＋１）－ｆ（ｎ）‖＝ｏ（１），（ｎ→∞）这里‖‖表示一实数与最近的整数的距离，则一定有某常数ｃ使ｆ（ｎ）一ｃｌｏｇｎ为整数值加性函数．这证实了ＫａｔａｉⅠ的一个猜想．     

Parallel algorithms for nonlinear programming problems

This paper describes several parallel algorithms for solving nonlinear programming problems. Two approaches where parallelism can successfully be introduced have been explored: a quadratic approximation method based on penalty function and a dual method. These methods are improved by using two algorithms originally proposed for solving unconstrained problems: the parallel variable metric algorithm and the parallel Jacobson-Oksman algorithm. Even though general problems are dealt with, particular emphasis is placed on the potential of these parallel methods for separable programming problems. The numerical effectiveness of the algorithms is demonstrated on a set of test problems using a Cray-1S vector computer and serial computers (with respect to sequential versions of the same methods).These studies were sponsored in part by the CERT. The author would particularly like to thank Ph. Berger (LSI-ENSEEIHT), the researchers of the DERI (CERT) and of the Groupe Structures, Aerospatiale, for their assistance.     

Parallel Newton Two-Stage Multisplitting Iterative Methods for Nonlinear Systems

Parallel Newton two-stage iterative methods to solve nonlinear systems are studied. These algorithms are based on both the multisplitting technique and the two-stage iterative methods. Convergence properties of these methods are studied when the Jacobian matrix is either monotone or an H-matrix. Furthermore, in order to illustrate the performance of the algorithms studied, computational results about these methods on a distributed memory multiprocessor are discussed.This revised version was published online in October 2005 with corrections to the Cover Date.