Short Communication: A note on optimal hybrid V-cycle multilevel algorithms for mixed finite element systems with penalty term

In this paper, we investigate some cost-effective hybrid V-cycle multilevel algorithms for the discrete systems that arise when a mixed finite element approach is used to solve certain second-order elliptic boundary value problems. By introducing a small penalty parameter, the perturbed indefinite system can be reduced to a symmetric positive definite system involving the unknown flux alone. We study the numerical behaviour of some hybrid V-cycle multilevel algorithms with optimal computational complexity based on the hierarchical spatial decomposition approach proposed by Cai, Goldstein and Pasciaks for the reduced system. © 1997 by John Wiley & Sons, Ltd.     

Field-of-values analysis of preconditioned iterative methods for nonsymmetric elliptic problems

Summary. The convergence rate of Krylov subspace methods for the solution of nonsymmetric systems of linear equations, such as GMRES or FOM, is studied. Bounds on the convergence rate are presented which are based on the smallest real part of the field of values of the coefficient matrix and of its inverse. Estimates for these quantities are available during the iteration from the underlying Arnoldi process. It is shown how these bounds can be used to study the convergence properties, in particular, the dependence on the mesh-size and on the size of the skew-symmetric part, for preconditioners for finite element discretizations of nonsymmetric elliptic boundary value problems. This is illustrated for the hierarchical basis and multilevel preconditioners which constitute popular preconditioning strategies for such problems. Received May 3, 1996     

Application of multilevel analysis in animal sciences

Multilevel modeling is considerably useful way to analyze hierarchical data sets. The main purpose of this paper is to apply multilevel analysis in animal science and also show that this modeling technique is appropriate to analyze this kind of data. Thus multilevel modeling technique is used to analyze the milk yield data which has hierarchical structures, sires nested within cows. As a result of the analysis done in this paper, it is obvious that multilevel modeling is needed to use for analyzing this data. This illustrates that it is a convenient way to use multilevel analysis for the data which obtained from animals when the data have hierarchies.     

The preconditioned GMRES method for systems of coupled FEM-BEM equations

We analyze the generalized minimal residual method (GMRES) as a solver for coupled finite element and boundary element equations. To accelerate the convergence of GMRES we apply a hierarchical basis block preconditioner for piecewise linear finite elements and piecewise constant boundary elements. It is shown that the number of iterations which is necessary to reach a given accuracy grows only poly-logarithmically with the number of unknowns. This revised version was published online in June 2006 with corrections to the Cover Date.     

Remarks on Multilevel Bases for Divergence-Free Finite Elements

The connection between the multilevel factorization method recently proposed by Sarin and Sameh for solving mixed discretizations of the Stokes equation using a divergence-free finite element formulation, and hierarchical basis preconditioners for the Poisson problem is established. For the 2D triangular Taylor–Hood element, a preconditioner is proposed that could be useful in fractional step methods.     

A Posteriori Error Estimates for Axisymmetric and Nonlinear Problems

We propose and examine the primal and dual finite element method for solving an axially symmetric elliptic problem with mixed boundary conditions. We derive an a posteriori error estimate and generalize the method used for a nonlinear elliptic problem. Finally, an a posteriori error estimate for a nonlinear parabolic problem based on the concept of hierarchical finite element basis functions is introduced.     

A survey of multilevel preconditioned iterative methods

We survey multilevel iterative methods applied for solving large sparse systems with matrices, which depend on a level parameter, such as arise by the discretization of boundary value problems for partial differential equations when successive refinements of an initial discretization mesh is used to construct a sequence of nested difference or finite element meshes.We discuss various two-level (two-grid) preconditioning techniques, including some for nonsymmetric problems. The generalization of these techniques to the multilevel case is a nontrivial task. We emphasize several ways this can be done including classical multigrid methods and a recently proposed algebraic multilevel preconditioning method. Conditions for which the methods have an optimal order of computational complexity are presented.On leave from the Institute of Mathematics, and Center for Informatics and Computer Technology, Bulgarian Academy of Sciences, Sofia, Bulgaria. The research of the second author reported here was partly supported by the Stichting Mathematisch Centrum, Amsterdam.     

Stabilization of algebraic multilevel iteration methods; additive methods

There exist two main versions of preconditioners of algebraic multilevel type, the additive and the multiplicative methods. They correspond to preconditioners in block diagonal and block matrix factorized form, respectively. Both can be defined and analysed as recursive two-by-two block methods. Although the analytical framework for such methods is simple, for many finite element approximations it still permits the derivation of the strongest results, such as optimal, or nearly optimal, rate of convergence and optimal, or nearly optimal order of computational complexity, when proper recursive global orderings of node points have been used or when they are applied for hierarchical basis function finite element methods for elliptic self-adjoint equations and stabilized in a certain way. This holds for general elliptic problems of second order, independent of the regularity of the problem, including independence of discontinuities of coefficients between elements and of anisotropy. Important ingredients in the methods are a proper balance of the size of the coarse mesh to the finest mesh and a proper solver on the coarse mesh. This paper presents in a survey form the basic results of such methods and considers in particular additive methods. This method has excellent parallelization properties. This revised version was published online in June 2006 with corrections to the Cover Date.     

A framework of parallel algebraic multilevel preconditioning iterations

1.IntroductionConsiderthesyllUnetricpositivedeflate(SPD)systemsoflinearequationsthatariseinfiniteelementdiscretisstionsofmanysecond-orderself-adjointellipticboundaryvalueproblems.Tosolvethisclassoflinearsystemsiteratively,AxelssonandVassilevski[1--4]preselltedthealgebraicmultileveliteration(AMLI)methodsbyreasonablyutilizingthemultigridtechniqueandthepolynomialaccelerationstrategy.Thesemethodsareamongthemostefficientiterativesolversbecausetheirpreconditioningmatricesarespectrallyequlvalellt…     

A new type of full multigrid method for the elasticity eigenvalue problem

This paper introduces a new type of full multigrid method for the elasticity eigenvalue problem. The main idea is to avoid solving large scale elasticity eigenvalue problem directly by transforming the solution of the elasticity eigenvalue problem into a series of solutions of linear boundary value problems defined on a multilevel finite element space sequence and some small scale elasticity eigenvalue problems defined on the coarsest correction space. The involved linear boundary value problems will be solved by performing some multigrid iterations. Besides, some efficient techniques such as parallel computing and adaptive mesh refinement can also be absorbed in our algorithm. The efficiency and validity of the multigrid methods are verified by several numerical experiments.     

CBS constants for multilevel splitting of graph-Laplacian and application to preconditioning of discontinuous Galerkin systems

The goal of this work is to derive and justify a multilevel preconditioner of optimal arithmetic complexity for symmetric interior penalty discontinuous Galerkin finite element approximations of second order elliptic problems. Our approach is based on the following simple idea given in [R.D. Lazarov, P.S. Vassilevski, L.T. Zikatanov, Multilevel preconditioning of second order elliptic discontinuous Galerkin problems, Preprint, 2005]. The finite element space of piece-wise polynomials, discontinuous on the partition , is projected onto the space of piece-wise constant functions on the same partition that constitutes the largest space in the multilevel method. The discontinuous Galerkin finite element system on this space is associated to the so-called “graph-Laplacian”. In 2-D this is a sparse M-matrix with -1 as off diagonal entries and nonnegative row sums. Under the assumption that the finest partition is a result of multilevel refinement of a given coarse mesh, we develop the concept of hierarchical splitting of the unknowns. Then using local analysis we derive estimates for the constants in the strengthened Cauchy–Bunyakowski–Schwarz (CBS) inequality, which are uniform with respect to the levels. This measure of the angle between the spaces of the splitting was used by Axelsson and Vassilevski in [Algebraic multilevel preconditioning methods II, SIAM J. Numer. Anal. 27 (1990) 1569–1590] to construct an algebraic multilevel iteration (AMLI) for finite element systems. The main contribution in this paper is a construction of a splitting that produces new estimates for the CBS constant for graph-Laplacian. As a result we have a preconditioner for the system of the discontinuous Galerkin finite element method of optimal arithmetic complexity.     

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.     

Some multilevel methods on graded meshes

We consider Yserentant's hierarchical basis method and multilevel diagonal scaling method on a class of refined meshes used in the numerical approximation of boundary value problems on polygonal domains in the presence of singularities. We show, as in the uniform case, that the stiffness matrix of the first method has a condition number bounded by (ln(1/h))², where h is the meshsize of the triangulation. For the second method, we show that the condition number of the iteration operator is bounded by ln(1/h), which is worse than in the uniform case but better than the hierarchical basis method. As usual, we deduce that the condition number of the BPX iteration operator is bounded by ln(1/h). Finally, graded meshes fulfilling the general conditions are presented and numerical tests are given which confirm the theoretical bounds.     

A general approach to analyse preconditioners for two‐by‐two block matrices

Two‐by‐two block matrices arise in various applications, such as in domain decomposition methods or when solving boundary value problems discretised by finite elements from the separation of the node set of the mesh into ‘fine’ and ‘coarse’ nodes. Matrices with such a structure, in saddle point form arise also in mixed variable finite element methods and in constrained optimisation problems. A general algebraic approach to construct, analyse and control the accuracy of preconditioners for matrices in two‐by‐two block form is presented. This includes both symmetric and nonsymmetric matrices, as well as indefinite matrices. The action of the preconditioners can involve element‐by‐element approximations and/or geometric or algebraic multigrid/multilevel methods. Copyright © 2011 John Wiley & Sons, Ltd.     

p－version有限元的快速高精度算法

ｐ－ｖｅｒｓｉｏｎ有限元的快速高精度算法曹礼群（湘潭大学）ＴＨＥＦＡＳＴｐ－ＶＥＲＳＩＯＮＦＩＮＩＴＥＥＬＥＭＥＮＴＭＥＴＨＯＤＷＩＴＨＨＩＧＨＡＣＣＵＲＡＣＹ￥ＣａｏＬｉ－ｑｕｎ（ＸｉａｎｇｔａｎＵｎｉｖｅｒｓｉｔｙ）Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓ...     

Stabilizing the Hierarchical Basis by Approximate Wavelets,I: Theory

This paper proposes a stabilization of the classical hierarchical basis (HB) method by modifying the HB functions using some computationally feasible approximate L²-projections onto finite element spaces of relatively coarse levels. The corresponding multilevel additive and multiplicative algorithms give spectrally equivalent preconditioners, and one action of such a preconditioner is of optimal order computationally. The results are regularity-free for the continuous problem (second order elliptic) and can be applied to problems with rough coefficients and local refinement. © 1997 by John Wiley & Sons, Ltd.     

A multi-parametric programming approach for multilevel hierarchical and decentralised optimisation problems

In this paper, we outline the foundations of a general global optimisation strategy for the solution of multilevel hierarchical and general decentralised multilevel problems, based on our recent developments on multi-parametric programming and control theory. The core idea is to recast each optimisation subproblem, present in the hierarchy, as a multi-parametric programming problem, with parameters being the optimisation variables belonging to the remaining subproblems. This then transforms the multilevel problem into single-level linear/convex optimisation problems. For decentralised systems, where more than one optimisation problem is present at each level of the hierarchy, Nash equilibrium is considered. A three person dynamic optimisation problem is presented to illustrate the mathematical developments.     

Preconditioning and a posteriori error estimates using h‐ and p‐hierarchical finite elements with rectangular supports

We show some of the properties of the algebraic multilevel iterative methods when the hierarchical bases of finite elements (FEs) with rectangular supports are used for solving the elliptic boundary value problems. In particular, we study two types of hierarchies; the so‐called h‐ and p‐hierarchical FE spaces on a two‐dimensional domain. We compute uniform estimates of the strengthened Cauchy–Bunyakowski–Schwarz inequality constants for these spaces. Moreover, for diagonal blocks of the stiffness matrices corresponding to the fine spaces, the optimal preconditioning matrices can be found, which have tri‐ or five‐diagonal forms for h‐ or p‐refinements, respectively, after a certain reordering of the elements. As another use of the hierarchical bases, the a posteriori error estimates can be computed. We compare them in test examples for h‐ and p‐hierarchical FEs with rectangular supports. Copyright © 2008 John Wiley & Sons, Ltd.     

Fuzzy systems based on component software

This paper describes hierarchical modeling of fuzzy logic concepts that has been used within the recently developed model of intelligent systems, called OBOA. The model is based on a multilevel, hierarchical, general object-oriented approach. Current methods and software design and development tools for intelligent systems are usually difficult to extend, and it is not easy to reuse their components in developing intelligent systems. The OBOA model tries to reduce these deficiencies. The model starts with a well-founded software engineering principle, making clear distinction between generic, low-level intelligent software components, and domain-dependent, high-level components of an intelligent system. This paper concentrates on modeling and implementation of fuzzy logic concepts within the hierarchical levels of the OBOA model. The fuzzy components described are extensible and adjustable. As an illustration of how these components are used in practice, a practical design example from the domain of medical diagnosis is shown. The paper also suggests some steps towards future design of fuzzy components and tools for intelligent systems.     

Modeling quasi-static crack growth with the embedded finite element method on multiple levels

The current work presents the multilevel approach of the embedded finite element method which is obtained by combining features of the method of domain decomposition with those of the standard embedded finite element method. The conventional requirement of fine mesh in a possible failure zone is rendered unnecessary with the new approach thereby reducing the computational expense. In addition, it is also possible to stop a propagating crack-tip in the middle of a finite element. In this approach, the finite elements at the failure-prone zone where cracks or shear bands, referred to as strong discontinuities which represent jumps in the displacement field, can form and propagate based on some failure criterion are treated as separate sub-boundary value problems which are adaptively discretized during the run time into a number of sub-elements and subjected to a kinematic constraint on their boundary. Each sub-element becomes equally capable of developing a strong discontinuity depending upon its state of stress. A linear displacement based constraint is applied initially which is modified accordingly as soon as a strong discontinuity propagates through the boundary of the main finite element. At the local equilibrium, the coupling between the quantities at two different levels of discretization is obtained by matching the virtual energies due to admissible variations of the main finite element and its constituent sub-elements. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)