Algebraic Multigrid Based on Computational Molecules, 1: Scalar Elliptic Problems

We consider the problem of splitting a symmetric positive definite (SPD) stiffness matrix A arising from finite element discretization into a sum of edge matrices thereby assuming that A is given as the sum of symmetric positive semidefinite (SPSD) element matrices. We give necessary and sufficient conditions for the existence of an exact splitting into SPSD edge matrices and address the problem of best positive (nonnegative) approximation. Based on this disassembling process we present a new concept of ``strong' and ``weak' connections (edges), which provides a basis for selecting the coarse-grid nodes in algebraic multigrid methods. Furthermore, we examine the utilization of computational molecules (small collections of edge matrices) for deriving interpolation rules. The reproduction of edge matrices on coarse levels offers the opportunity to combine classical coarsening algorithms with effective (energy minimizing) interpolation principles yielding a flexible and robust new variant of AMG.     

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

Algebraic multigrid methods based on element preconditioning

This paper presents a new algebraic multigrid (AMG) solution strategy for large linear systems with a sparse matrix arising from a finite element discretization of some self-adjoint, second order, scalar, elliptic partial differential equation. The AMG solver is based on Ruge/Stübens method. Ruge/Stübens algorithm is robust for M-matrices, but unfortunately the “region of robustness“ between symmetric positive definite M-matrices and general symmetric positive definite matrices is very fuzzy.

For this reason the so-called element preconditioning technique is introduced in this paper. This technique aims at the construction of an M-matrix that is spectrally equivalent to the original stiffness matrix. This is done by solving small restricted optimization problems. AMG applied to the spectrally equivalent M-matrix instead of the original stiffness matrix is then used as a preconditioner in the conjugate gradient method for solving the original problem.

The numerical experiments show the efficiency and the robustness of the new preconditioning method for a wide class of problems including problems with anisotropic elements.     

On the Convergence of a Multigrid Method for Linear Reaction-Diffusion Problems

In this note we consider discrete linear reaction-diffusion problems. For the discretization a standard conforming finite element method is used. For the approximate solution of the resulting discrete problem a multigrid method with a damped Jacobi or symmetric Gauss-Seidel smoother is applied. We analyze the convergence of the multigrid V- and W-cycle in the framework of the approximation- and smoothing property. The multigrid method is shown to be robust in the sense that the contraction number can be bounded by a constant smaller than one which does not depend on the mesh size or on the diffusion-reaction ratio. Received June 15, 2000     

Composite Finite Elements for Elliptic Boundary Value Problems with Discontinuous Coefficients

In this paper, we will introduce composite finite elements for solving elliptic boundary value problems with discontinuous coefficients. The focus is on problems where the geometry of the interfaces between the smooth regions of the coefficients is very complicated. On the other hand, efficient numerical methods such as, e.g., multigrid methods, wavelets, extrapolation, are based on a multi-scale discretization of the problem. In standard finite element methods, the grids have to resolve the structure of the discontinuous coefficients. Thus, straightforward coarse scale discretizations of problems with complicated coefficient jumps are not obvious. In this paper, we define composite finite elements for problems with discontinuous coefficients. These finite elements allow the coarsening of finite element spaces independently of the structure of the discontinuous coefficients. Thus, the multigrid method can be applied to solve the linear system on the fine scale. We focus on the construction of the composite finite elements and the efficient, hierarchical realization of the intergrid transfer operators. Finally, we present some numerical results for the multigrid method based on the composite finite elements (CFE–MG).     

Computing Interpolation Weights in AMG Based on Multilevel Schur Complements

This paper presents a particular construction of neighborhood matrices to be used in the computation of the interpolation weights in AMG (algebraic multigrid). The method utilizes the existence of simple interpolation matrices (piecewise constant for example) on a hierarchy of coarse spaces (grids). Then one constructs by algebraic means graded away coarse spaces for any given fine-grid neighborhood. Next, the corresponding stiffness matrix is computed on this graded away mesh, and the actual neighborhood matrix is obtained by computing the multilevel Schur complement of this matrix where degrees of freedom outside the neighborhood have to be eliminated. The paper presents algorithmic details, provides model complexity analysis as well as some comparative tests of the quality of the resulting interpolation based on the multilevel Schur complements versus element interpolation based on the true element matrices.     

A finite element based level set method for two-phase incompressible flows

We present a method that has been developed for the efficient numerical simulation of two-phase incompressible flows. For capturing the interface between the phases the level set technique is applied. The continuous model consists of the incompressible Navier–Stokes equations coupled with an advection equation for the level set function. The effect of surface tension is modeled by a localized force term at the interface (so-called continuum surface force approach). For spatial discretization of velocity, pressure and the level set function conforming finite elements on a hierarchy of nested tetrahedral grids are used. In the finite element setting we can apply a special technique to the localized force term, which is based on a partial integration rule for the Laplace–Beltrami operator. Due to this approach the second order derivatives coming from the curvature can be eliminated. For the time discretization we apply a variant of the fractional step θ-scheme. The discrete saddle point problems that occur in each time step are solved using an inexact Uzawa method combined with multigrid techniques. For reparametrization of the level set function a new variant of the fast marching method is introduced. A special feature of the solver is that it combines the level set method with finite element discretization, Laplace–Beltrami partial integration, multilevel local refinement and multigrid solution techniques. All these components of the solver are described. Results of numerical experiments are presented.     

Algebraic spectral multigrid methods

For the Helmholtz equation a spectral discretization with a symmetric and sparse matrix is presented. Certain algebraic spectral multigrid methods can be efficiently used for solving the linear systems.     

科恩-沈方程与含时科恩-沈方程的一个自适应有限元数值方法

在材料分析、纳米光学等研究中,高质量数值模拟多体系统电子密度的随时间演化是一类重要研究内容.演化中产生的时间依赖偶极子等物理量,是更进一步研究的基础.此类数值模拟分为两个步骤,即多体系统的基态求解、及以基态为初值的系统的动态演化模拟.这两个步骤可以分别通过数值求解科恩-沈(Kohn-Sham)方程及含时科恩-沈(time-dependent Kohn-Sham)方程实现.本文中,我们提出一类基于有限元方法的数值求解框架,为这两个步骤提供一个统一的模拟实现.在基态求解中,我们利用一类自洽场迭代对方程进行线性化,采用局部最优块预处理共轭梯度法求解导出的广义特征值问题,并设计了一个基于多重网格方法的预优对求解进行有效加速.在动态演化模拟中,针对方程的结构,我们提出了一个基于隐式中点公式的数值方法,利用预估-校正方法对方程进行线性化处理,并设计了一个针对复值线性系统的代数多重网格求解器用于加速时间推进.特别地,我们基于提出的数值方法,分别针对科恩-沈及含时科恩-沈方程导出了残量型后验误差估计子,并实现了基于局部加密的网格自适应方法,用于进一步改善数值模拟效率.数值解展示了方法的有效性.     

Energy Optimization of Algebraic Multigrid Bases

We propose a fast iterative method to optimize coarse basis functions in algebraic multigrid by minimizing the sum of their energies, subject to the condition that linear combinations of the basis functions equal to given zero energy modes, and subject to restrictions on the supports of the coarse basis functions. For a particular selection of the supports, the first iteration gives exactly the same basis functions as our earlier method using smoothed aggregation. The convergence rate of the minimization algorithm is bounded independently of the mesh size under usual assumptions on finite elements. The construction is presented for scalar problems as well as for linear elasticity. Computational results on difficult industrial problems demonstrate that the use of energy minimal basis functions improves algebraic multigrid performance and yields a more robust multigrid algorithm than smoothed aggregation. Received: March 9, 1998; revised January 25, 1999     

Fast Matrix-Vector Multiplication in the Sparse-Grid Galerkin Method

Sparse grid discretization of higher dimensional partial differential equations is a means to break the curse of dimensionality. For classical sparse grids based on the one-dimensional hierarchical basis, a sophisticated algorithm has been devised to calculate the application of a vector to the Galerkin matrix in linear complexity, despite the fact that the matrix is not sparse. However more general sparse grid constructions have been recently introduced, e.g. based on multilevel finite elements, where the specified algorithms only have a log-linear scaling. This article extends the idea of the linear scaling algorithm to more general sparse grid spaces. This is achieved by abstracting the algorithm given in (Balder and Zenger, SIAM J. Sci. Comput. 17:631, 1996) from specific bases, thereby identifying the prerequisites for performing the algorithm. In this way one can easily adapt the algorithm to specific discretizations, leading for example to an optimal linear scaling algorithm in the case of multilevel finite element frames.     

基于局部松弛和粗化策略的代数多重网格方法

受强振荡、间断系数和非均匀网格步长的影响,由偏微分方程离散所得的稀疏线性代数方程组的系数矩阵呈现多尺度性质,即同一行的非对角元素可相差几个数量级,使得经典代数多重网格（AMG）算法难以适应.本文提出一种新的AMG方法（LRC-AMG）,基于强弱相邻关系分离某些具有特殊性质的点结成网格子块,仅在局部块内进行光滑和粗化,可有效地消除多尺度性对收敛速度的影响.数值实验在文中给出.     

Higher Order Sparse Grid Methods for Elliptic Partial Differential Equations with Variable Coefficients

We present a method for discretizing and solving general elliptic partial differential equations on sparse grids employing higher order finite elements. On the one hand, our approach is charactarized by its simplicity. The calculation of the occurring functionals is composed of basic pointwise or unidirectional algorithms. On the other hand, numerical experiments prove our method to be robust and accurate. Discontinuous coefficients can be treated as well as curvilinearly bounded domains. When applied to adaptively refined sparse grids, our discretization results to be highly efficient, yielding balanced errors on the computational domain.     

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.     

Semi-Unstructured Grids

We present a novel automatic grid generator for the finite element discretization of partial differential equations in 3D. The grids constructed by this grid generator are composed of a pure tensor product grid in the interior of the domain and an unstructured grid which is only contained in boundary cells. The unstructured component consists of tetrahedra, each of which satisfies a maximal interior angle condition. By suitable constructing the boundary cells, the number of types of boundary subcells is reduced to 12 types. Since this grid generator constructs large structured grids in the interior and small unstructured grids near the boundary, the resulting semi-unstructured grids have similar properties as structured tensor product grids. Some appealing properties of this method are computational efficiency and natural construction of coarse grids for multilevel algorithms. Numerical results and an analysis of the discretization error are presented. Received July 17, 2000; revised October 27, 2000     

A scaled thickness conditioning for solid- and solid-shell discretizations of thin-walled structures

The numerical discretization of thin shell structures yields ill-conditioned stiffness matrices due to an inherent large eigenvalue spectrum. Finite element parametrization that depends on shell thickness, like relative displacement shells, solid shells and other solid finite elements even add to the ill-conditioning by introducing high eigenmodes.To overcome this numerical issue we present a scaled thickness conditioning (STC) approach, a mechanically motivated preconditioner for thin-walled structures discretized with continuum based element formulations. The proposed approach is motivated by the scaled director conditioning (SDC) method for relative displacement shell elements. In contrast to SDC, the novel STC approach yields a preconditioner for the effective linear system. It is applicable independently of element technology employed, coupling to other physical fields, boundary conditions applied and additional algebraic constraints and can be easily extended to multilayer shell formulations.The effect of the proposed preconditioner on the conditioning of the effective stiffness matrix and its eigenvalue spectrum is studied. It is shown that the condition number of the modified system becomes almost independent from the aspect ratio of the employed elements. The improved conditioning has a positive influence on the convergence behavior of iterative linear solvers. In particular, in combination with algebraic multigrid preconditioners the number of iterations could be decreased by more than 85% for some examples and the computation time could be reduced by about 60%.     

Explicit approximate inverse preconditioning techniques

Summary  The numerical treatment and the production of related software for solving large sparse linear systems of algebraic equations, derived mainly from the discretization of partial differential equation, by preconditioning techniques has attracted the attention of many researchers. In this paper we give an overview of explicit approximate inverse matrix techniques for computing explicitly various families of approximate inverses based on Choleski and LU—type approximate factorization procedures for solving sparse linear systems, which are derived from the finite difference, finite element and the domain decomposition discretization of elliptic and parabolic partial differential equations. Composite iterative schemes, using inner-outer schemes in conjunction with Picard and Newton method, based on approximate inverse matrix techniques for solving non-linear boundary value problems, are presented. Additionally, isomorphic iterative methods are introduced for the efficient solution of non-linear systems. Explicit preconditioned conjugate gradient—type schemes in conjunction with approximate inverse matrix techniques are presented for the efficient solution of linear and non-linear system of algebraic equations. Theoretical estimates on the rate of convergence and computational complexity of the explicit preconditioned conjugate gradient method are also presented. Applications of the proposed methods on characteristic linear and non-linear problems are discussed and numerical results are given.     

Solution of linear equations with skyline-stored symmetric matrix

Fortran IV subroutines for the in-core solution of linear algebraic systems with a sparse, symmetric, skyline-stored coefficient matrix are presented. Such systems arise in a variety of applications, notably the numerical discretization of conservative physical systems by finite differences or finite element techniques. The routines can be used for processing constrained systems without need for prearranging equations. The application to ‘superelement’ condensation of large-scale systems is discussed.     

Solution of linear equations with a symmetrically skyline-stored nonsymmetric matrix

Fortran IV subroutines for the in-core solution of linear algebraic systems with a sparse, symmetrically skylined-stored nonsymmetric coefficient matrix are presented. Such systems arise in various computations, among which are the finite element discretization in conjunction with incremental continuum mechanics, or space-time finite elements for dynamical systems. These routines can be used for constrained systems without prearranging. The feature of partial decomposition is installed and its application to the analysis of singular matrices is discussed.     

A Domain Decomposition Preconditioner for p-FEM Discretizations of Two-dimensional Elliptic Problems

In this paper, a uniformly elliptic second order boundary value problem in 2-D discretized by the p-version of the finite element method is considered. An inexact Dirichlet-Dirichlet domain decomposition pre-conditioner for the system of linear algebraic equations is investigated. Two solvers for the problem in the sub-domains, a pre-conditioner for the Schur-complement and an extension operator operating from the edges of the elements into the interior are proposed as ingredients for the inexact DD-pre-conditioner. In the main part of the paper, several numerical experiments on a parallel computer are given.