Necessity for algebraic parabolicity conditions for nonstationary problems

It is known that single-valued solvability of nonstationary problems in spaces W₂ ^(l) with a priori estimate holds in the evaluation of some algebraic parabolicity conditions. It is proved in this note that the parabolicity conditions result from this estimate. (6 References)Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 615–625, December, 1967.     

Geometric and algebraic multigrid techniques for fluid dynamics problems on unstructured grids

Issues concerning the implementation and practical application of geometric and algebraic multigrid techniques for solving systems of difference equations generated by the finite volume discretization of the Euler and Navier–Stokes equations on unstructured grids are studied. The construction of prolongation and interpolation operators, as well as grid levels of various resolutions, is discussed. The results of the application of geometric and algebraic multigrid techniques for the simulation of inviscid and viscous compressible fluid flows over an airfoil are compared. Numerical results show that geometric methods ensure faster convergence and weakly depend on the method parameters, while the efficiency of algebraic methods considerably depends on the input parameters.     

Distributed algebraic multigrid for finite element computations

The Finite Element Method has been successfully applied to a variety of problems in engineering, medicine, biology, and physics. However, this method can be computationally intensive, particularly for problems in which an unstructured mesh of elements is generated. In such situations, the Algebraic Multigrid (AMG) can prove to be a robust method for solving the discretized linear systems that emerge from the problem. Unfortunately, AMG requires a large amount of storage (thus causing swapping on most sequential machines), and typically converges slowly. We show that distributing the algorithm across a cluster of workstations can help alleviate these problems. The distributed algorithm is run on a number of geomechanics problems that are solved using finite elements. The results show that distributed processing is extremely useful in maintaining the performance of the AMG algorithm with increasing problem size, particularly by reducing the amount of disk swapping required.     

Analytic solution of boundary-value problems for nonstationary model kinetic equations

A theory for constructing the solutions of boundary-value problems for nonstationary model kinetic equations is constructed. This theory was incorrectly presented in the recent well-known monographs of Cercignani [1,2]. After application of a Laplace transformation to the studied equation, separation of the variables is used, this leading to a characteristic equation. Eigenfunctions are found in the space of generalized functions, and the eigenvalue spectrum is investigated. An existence and uniqueness theorem for the expansion of the Laplace transform of the solution with respect to the eigenfunctions is proved. The proof is constructive and gives explicit expressions for the expansion coefficients. An application to the Rayleight problem is obtained, and the corresponding result of Cercignani is corrected.Moscow Pedagogical University. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 92, No. 1, pp. 127–138, July, 1992.     

Numerical simulation of fluid-structure interaction problems on hybrid meshes with algebraic multigrid methods

Fluid-structure interaction problems arise in many fields of application such as flows around elastic structures and blood flow in arteries. The method presented in this paper for solving such a problem is based on a reduction to an equation at the interface, involving the so-called Steklov-Poincaré operators. This interface equation is solved by a Newton iteration, for which directional derivatives involving shape derivatives with respect to the interface perturbation have to be evaluated appropriately. One step of the Newton iteration requires the solution of several decoupled linear sub-problems in the structure and the fluid domains. These sub-problems are spatially discretized by a finite element method on hybrid meshes. For the time discretization, implicit first-order methods are used for both sub-problems. The discretized equations are solved by algebraic multigrid methods.     

An accelerated algebraic multigrid algorithm for total-variation denoising

The variational partial differential equation (PDE) approach for image denoising restoration leads to PDEs with nonlinear and highly non-smooth coefficients. Such PDEs present convergence difficulties for standard multigrid methods. Recent work on algebraic multigrid methods (AMGs) has shown that robustness can be achieved in general but AMGs are well known to be expensive to apply. This paper proposes an accelerated algebraic multigrid algorithm that offers fast speed as well as robustness for image PDEs. Experiments are shown to demonstrate the improvements obtained.     

Reducing complexity of algebraic multigrid by aggregation

A typical approach to decrease computational costs and memory requirements of classical algebraic multigrid methods is to replace a conservative coarsening algorithm and short‐distance interpolation on a fixed number of fine levels by an aggressive coarsening with a long‐distance interpolation. Although the quality of the resulting algebraic multigrid grid preconditioner often deteriorates in terms of convergence rates and iteration counts of the preconditioned iterative solver, the overall performance can improve substantially. We investigate here, as an alternative, a possibility to replace the classical aggressive coarsening by aggregation, which is motivated by the fact that the convergence of aggregation methods can be independent of the problem size provided that the number of levels is fixed. The relative simplicity of aggregation can lead to improved solution and setup costs. The numerical experiments show the relevance of the proposed combination on both academic and benchmark problems in reservoir simulation from oil industry. Copyright © 2016 John Wiley & Sons, Ltd.     

An algebraic multigrid method with interpolation reproducing rigid body modes for semi-definite problems in two-dimensional linear elasticity

Based on the geometric grid information as geometric coordinates, an algebraic multigrid (AMG) method with the interpolation reproducing the rigid body modes (namely the kernel elements of semi-definite operator arising from linear elasticity) is constructed, and such method is applied to the linear elasticity problems with a traction free boundary condition and crystal problems with free boundary conditions as well. The results of various numerical experiments in two dimensions are presented. It is shown from the numerical results that the constructed AMG method is robust and efficient for such semi-definite problems, and the convergence is uniformly bounded away from one independent of the problem size. Furthermore, the AMG method proposed in this paper has better convergence rate than the commonly used AMG methods. Simultaneously, an AMG method that can preserve the quotient space, which means that if the exact solution of original problem belongs to the quotient space of discrete operator considered, then the numerical solution of AMG method is convergent in the same quotient space, is obtained using the technique of orthogonal decomposition.     

A noniterative algebraic solution for Riccati equations satisfying two-point boundary-value problems

A noniterative algebraic method is presented for solving differential Riccati equations which satisfy two-point boundary-value problems. This class of numerical problems arises in quadratic optimization problems where the cost functionals are composed of both continuous and discrete state penalties, leading to piecewise periodic feedback gains. The necessary condition defining the solution for the two-point boundary value problem is cast in the form of a discrete-time algebraic Riccati equation, by using a formal representation for the solution of the differential Riccati equation. A numerical example is presented which demonstrates the validity of the approach.The authors would like to thank Dr. Fernando Incertis, IBM Madrid Scientific Center, who reviewed this paper and pointed out that the two-point boundary-value necessary condition could be manipulated into the form of a discrete-time Riccati equation. His novel approach proved to be superior to the authors' previously proposed iterative continuation method.     

Nonnested multigrid methods for linear problems

This article presents an application of nonnested and unstructured multigrid methods to linear elastic problems. A variational formulation for transfer operators and some multigrid strategies, including adaptive algorithms, are presented. Expressions for the performance evaluation of multigrid strategies and its comparison with direct and preconditioned conjugate gradient algorithms are also presented. A C++ implementation of the multigrid algorithms and the quadtree and octree data structures for transfer operators are discussed. Some two‐ and three‐dimensional elasticity examples are analyzed. © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17:313–331, 2001     

Cascadic multigrid methods for parabolic problems

In this paper,we consider the cascadic multigrid method for a parabolic type equation.Backward Euler approximation in time and linear finite element approximation in space are employed.A stability result is established under some conditions on the smoother.Using new and sharper estimates for the smoothers that reflect the precise dependence on the time step and the spatial mesh parameter,these conditions are verified for a number of popular smoothers.Optimal error bound sare derived for both smooth and non-smooth data.Iteration strategies guaranteeing both the optimal accuracy and the optimal complexity are presented.     

Defect-correction multigrid methods for nonlinear problems

Auzinger and Stetter [1] combine a multigrid method with defect-correction iteration and derive a composite iterative procedure which they call the DCMG (defect-correction multigrid) cycle. Using a high-order discrete operator in the coarsegrid correction and a lower-order operator in relaxation, the DCMG cycle achieves the higher-order approximation [4]. In an analogous way, DCMG can be used to solve nonlinear PDEs by using the nonlinear operator in correction and a related linear operator in relaxation. We prove convergence of such a DCMG scheme and give an error estimation.     

Notes on convergence of an algebraic multigrid method

The convergence theory for algebraic multigrid (AMG) algorithms proposed in Chang and Huang [Q.S. Chang, Z.H. Huang, Efficient algebraic multigrid algorithms and their convergence, SIAM J. Sci. Comput. 24 (2002) 597–618] is further discussed and a smaller and elegant upper bound is obtained. On the basis of element-free AMGe [V.E. Henson, P.S. Vassilevski, Element-free AMGe: General algorithms for computing interpolation weights in AMG, SIAM J. Sci. Comput. 23(2) (2001) 629–650] we rewrite the interpolation operator for the classical AMG (cAMG), present a uniform expression and then, by introducing a sparse approximate inverse in the Frobenius norm, give a general convergence theorem which is suited for not only cAMG but also AMG for finite elements and element-free AMGe.     

Convergence of algebraic multigrid based on smoothed aggregation

Summary. We prove an abstract convergence estimate for the Algebraic Multigrid Method with prolongator defined by a disaggregation followed by a smoothing. The method input is the problem matrix and a matrix of the zero energy modes of the same problem but with natural boundary conditions. The construction is described in the case of a general elliptic system. The condition number bound increases only as a polynomial of the number of levels, and requires only a uniform weak approximation property for the aggregation operators. This property can be a-priori verified computationally once the aggregates are known. For illustration, it is also verified here for a uniformly elliptic diffusion equations discretized by linear conforming quasiuniform finite elements. Only very weak and natural assumptions on the hierarchy of aggregates are needed. Received March 1, 1998 / Revised version received January 28, 2000 / Published online: December 19, 2000     

High-order discretization and multigrid solution of elliptic nonlinear constrained optimal control problems

High(-mixed)-order finite difference discretization of optimality systems arising from elliptic nonlinear constrained optimal control problems are discussed. For the solution of these systems, an efficient and robust multigrid algorithm is presented. Theoretical and experimental results show the advantages of higher-order discretization and demonstrate that the proposed multigrid scheme is able to solve efficiently constrained optimal control problems also in the limit case of bang-bang control.     

Analysis of algebraic multigrid parameters for two-dimensional steady-state heat diffusion equations

In this work, it is provided a comparison for the algebraic multigrid (AMG) and the geometric multigrid (GMG) parameters, for Laplace and Poisson two-dimensional equations in square and triangular grids. The analyzed parameters are the number of: inner iterations in the solver, grids and unknowns. For the AMG, the effects of the grid reduction factor and the strong dependence factor in the coarse grid on the necessary CPU time are studied. For square grids the finite difference method is used, and for the triangular grids, the finite volume one. The results are obtained with the use of an adapted AMG1R6 code of Ruge and Stüben. For the AMG the following components are used: standard coarsening, standard interpolation, correction scheme (CS), lexicographic Gauss–Seidel and V-cycle. Comparative studies among the CPU time of the GMG, AMG and singlegrid are made. It was verified that: (1) the optimum inner iterations is independent of the multigrid, however it is dependent on the grid; (2) the optimum number of grids is the maximum number; (3) AMG was shown to be sensitive to both the variation of the grid reduction factor and the strong dependence factor in the coarse grid; (4) in square grids, the GMG CPU time is 20% of the AMG one.     

An algebraic multigrid method for finite element systems on criss-cross grids

In this paper, we design and analyze an algebraic multigrid method for a condensed finite element system on criss-cross grids and then provide a convergence analysis. Criss-cross grid finite element systems represent a large class of finite element systems that can be reduced to a smaller system by first eliminating certain degrees of freedoms. The algebraic multigrid method that we construct is analogous to many other algebraic multigrid methods for more complicated problems such as unstructured grids, but, because of the specialty of our problem, we are able to provide a rigorous convergence analysis to our algebraic multigrid method. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday The work was supported in part by NSAF(10376031) and National Major Key Project for basic researches and by National High-Tech ICF Committee in China.     

An algebraic multigrid method for finite element discretizations with edge elements

This paper presents an algebraic multigrid method for the efficient solution of the linear system arising from a finite element discretization of variational problems in H₀(curl,Ω). The finite element spaces are generated by Nédélec's edge elements. A coarsening technique is presented, which allows the construction of suitable coarse finite element spaces, corresponding transfer operators and appropriate smoothers. The prolongation operator is designed such that coarse grid kernel functions of the curl‐operator are mapped to fine grid kernel functions. Furthermore, coarse grid kernel functions are ‘discrete’ gradients. The smoothers proposed by Hiptmair and Arnold, Falk and Winther are directly used in the algebraic framework. Numerical studies are presented for 3D problems to show the high efficiency of the proposed technique. Copyright © 2002 John Wiley & Sons, Ltd.     

The cascadic multigrid method for elliptic problems

Summary. The paper deals with certain adaptive multilevel methods at the confluence of nested multigrid methods and iterative methods based on the cascade principle of [10]. From the multigrid point of view, no correction cycles are needed; from the cascade principle view, a basic iteration method without any preconditioner is used at successive refinement levels. For a prescribed error tolerance on the final level, more iterations must be spent on coarser grids in order to allow for less iterations on finer grids. A first candidate of such a cascadic multigrid method was the recently suggested cascadic conjugate gradient method of [9], in short CCG method, whichused the CG method as basic iteration method on each level. In [18] it has been proven, that the CCG method is accurate with optimal complexity for elliptic problems in 2D and quasi-uniform triangulations. The present paper simplifies that theory and extends it to more general basic iteration methods like the traditional multigrid smoothers. Moreover, an adaptive control strategy for the number of iterations on successive refinement levels for possibly highly non-uniform grids is worked out on the basis of a posteriori estimates. Numerical tests confirm the efficiency and robustness of the cascadic multigrid method. Received November 12, 1994 / Revised version received October 12, 1995