On the multi-level splitting of finite element spaces

Summary In this paper we analyze the condition number of the stiffness matrices arising in the discretization of selfadjoint and positive definite plane elliptic boundary value problems of second order by finite element methods when using hierarchical bases of the finite element spaces instead of the usual nodal bases. We show that the condition number of such a stiffness matrix behaves like O((log )²) where is the condition number of the stiffness matrix with respect to a nodal basis. In the case of a triangulation with uniform mesh sizeh this means that the stiffness matrix with respect to a hierarchical basis of the finite element space has a condition number behaving like instead of for a nodal basis. The proofs of our theorems do not need any regularity properties of neither the continuous problem nor its discretization. Especially we do not need the quasiuniformity of the employed triangulations. As the representation of a finite element function with respect to a hierarchical basis can be converted very easily and quickly to its representation with respect to a nodal basis, our results mean that the method of conjugate gradients needs onlyO(log n) steps andO(n log n) computer operations to reduce the energy norm of the error by a given factor if one uses hierarchical bases or related preconditioning procedures. Heren denotes the dimension of the finite element space and of the discrete linear problem to be solved.     

Analysis of Iterative Sub-structuring Techniques for Boundary Element Approximation of the Hypersingular Operator in Three Dimensions

The article deals with the analysis of Additive Schwarz preconditioners for the h -version of the boundary element method for the hypersingular integral equation on surfaces in three dimensions. The first preconditioner consists of decomposing into local spaces associated with the subdomain interiors, supplemented with a wirebasket space associated with the subdomain interfaces. The wirebasket correction only involves the inversion of a diagonal matrix, while the interior correction consists of inverting the sub-blocks of the stiffness matrix corresponding to the interior degrees of freedom on each subdomain. It is shown that the condition number of the preconditioned system grows at most as max K H m 1 (1 + log H / h K ) 2 where H is the size of the quasi-uniform subdomains and h K is the size of the elements in subdomain K . A second preconditioner is given that incorporates a coarse space associated with the subdomains. This improves the robustness of the method with respect to the number of subdomains: theoretical analysis shows that growth of the condition number of the preconditioned system is now bounded by max K (1 + log H / h K ) 2 .     

依赖时间的Lagrange乘子区域分解法的显式格式

１．引言 近年来,一类新的区域分解法－非匹配网格区域分解法,日益引起人们的广泛兴趣．这类区域分解法的特点是：相邻子区域在公共边（或面）上的结点可以不重合,从而可方便地处理匹配网格区域分解法难以处理的问题：变动网格问题（例如石油勘探中的地层错动问题）和最优网格设计问题（即根据解的性质和实际问题的要求在不同子区域上采用不同的单元类型,不同的网格尺寸和不同阶的逼近多项式）． 在这类区域分解的算法设计中面临着两个困难：界面上非协调性的处理（与通常的协调元不同）和界面上积分的有效计算．现有算法中较引人注目的…     

基于子结构法构造用非协调元解椭圆型问题的预处理器（Ⅰ）

基于子结构法构造用非协调元解椭圆型问题的预处理器（Ⅰ）顾金生，胡显承（清华大学应用数学系）ＴＨＥＣＯＮＳＴＲＵＣＴＩＯＮＯＦＰＲＥＣＯＮＤＩＴＩＯＮＥＲＳＦＯＲＥＬＬＩＰＴＩＣＰＲＯＢＬＥＭＳＤＩＳＣＲＥＴＩＺＥＤＢＹＮＯＮＣＯＮＦＯＲＭＩＮＧＦＩＮ...     

SINE TRANSFORM PRECONDITIONERS FOR SECOND-ORDER PARTIAL DIFFERENTIAL EQUATIONS

In this paper, we are concerned with the numerical solution of second-order partial differential equations. We analyse the use of the Sine Transform precondilioners for the solution of linear systems arising from the discretization of p.d.e. via the preconditioned conjugate gradient method. For the second-order partial differential equations with Dirichlel boundary conditions, we prove that the condition number of the preconditioned system is O(1) while the condition number of the original system is O(m 2) Here m is the number of interior gridpoints in each direction. Such condition number produces a linear convergence rale.     

Preconditioning of the Stiffness Matrix of Local Refined Triangulation

A preconditioning method for the finite element stiffness matrix is given in this paper. The triangulation is refined in a subregion; the preconditioning process is composed of resolution of two regular subproblems; the condition number of the preconditioned matrix is O(1 logH/h), where H and h are mesh sizes of the unrefined and local refined triangulations respectively.     

A Study on the Conditioning of Finite Element Equations with Arbitrary Anisotropic Meshes via a Density Function Approach

The linear finite element approximation of a general linear diffusion problem with arbitrary anisotropic meshes is considered. The conditioning of the resultant stiffness matrix and the Jacobi preconditioned stiffness matrix is investigated using a density function approach proposed by Fried in 1973. It is shown that the approach can be made mathematically rigorous for general domains and used to develop bounds on the smallest eigenvalue and the condition number that are sharper than existing estimates in one and two dimensions and comparable in three and higher dimensions. The new results reveal that the mesh concentration near the boundary has less influence on the condition number than the mesh concentration in the interior of the domain. This is especially true for the Jacobi preconditioned system where the former has little or almost no influence on the condition number. Numerical examples are presented.     

On condition numbers in hp-FEM with Gauss–Lobatto-based shape functions

Sharp bounds on the condition number of stiffness matrices arising in hp/spectral discretizations for two-dimensional problems elliptic problems are given. Two types of shape functions that are based on Lagrange interpolation polynomials in the Gauss–Lobatto points are considered. These shape functions result in condition numbers O(p) and $\text{O(p}\text{ln}\text{p)}$ for the condensed stiffness matrices, where p is the polynomial degree employed. Locally refined meshes are analyzed. For the discretization of Dirichlet problems on meshes that are refined geometrically toward singularities, the conditioning of the stiffness matrix is shown to be independent of the number of layers of geometric refinement.     

基于非协调元的加法型Schwarz交替法──弱重迭情形

基于非协调元的加法型Ｓｃｈｗａｒｚ交替法──弱重迭情形黄建国（上海交通大学应用数学系）ＡＤＤＩＴＩＶＥＳＣＨＷＡＲＺＡＬＴＥＲＮＡＴＩＮＧＭＥＴＨＯＤＦＯＲＮＯＮＣＯＮＦＯＲＭＩＮＧＦＩＮＩＴＥＥＬＥＭＥＮＴ──ＣＡＳＥＯＦＷＥＡＫＯＶＥＲＬＡＰ￥Ｈ...     

A preconditioning strategy for boundary element Galerkin methods

The Dirichlet and Neumann problems for the Laplacian are reformulated in the usual way as boundary integral equations of the first kind with symmetric kernels. These integral equations are solved using Galerkin's method with piecewise-constant and piecewise-linear boundary elements, respectively. In both cases, the stiffness matrix is symmetric and positive-definite, and has a condition number of order N, the number of degrees of freedom. By contrast, the condition number of the product of the two stiffness matrices is bounded independently of N. Hence, we can use the Neumann stiffness matrix to precondition the Dirichlet stiffness matrix, and vice versa. © 1997 John Wiley & Sons, Inc.     

基于子结构法构造用非协调元解椭圆型问题的预处理器（II）

基于子结构法构造用非协调元解椭圆型问题的预处理器（ＩＩ）顾金生，胡显承（清华大学应用数学系）李岷珊（北方交通大学数学系）ＴＨＥＣＯＮＳＴＲＵＣＴＩＯＮＯＦＰＲＥＣＯＮＤＩＴＩＯＮＥＲＳＦＯＲＥＬＬＩＰＴＩＣＰＲＯＢＬＥＭＳＤＩＳＣＲＥＴＩＺＥＤＢＹＮ...     

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 WAVELET METHOD FOR THE FREDHOLM INTEGRO-DIFFERENTIAL EQUATIONS WITH CONVOLUTION KERNEL

1.IntroductionInthispaper,westudytheFredholmintegro-differentialequationbythewaveletmethod.Theapplicationsoftheequationinimagerestorationcouldbefoundin[101.ForthehistoryofnumericalmethodsfortheFredholmintegro-differentialequations,wereferto[4].FOllow...     

Band Toeplitz preconditioners for block Toeplitz systems

We consider the solutions of block Toeplitz systems with Toeplitz blocks by the preconditioned conjugate gradient (PCG) method. Here the block Toeplitz matrices are generated by nonnegative functions f(x,y). We use band Toeplitz matrices as preconditioners. The generating functions g(x,y) of the preconditioners are trigonometric polynomials of fixed degree and are determined by minimizing (f − g)/f∞. We prove that the condition number of the preconditioned system is O(1). An a priori bound on the number of iterations for convergence is obtained.     

群体偏差映射的扩展理性条件

对于文[1]引进的群体偏差映射，本文给出了与K．O．May和A．K．Sen关于序数型理性条件相应的6个基数型条件．同时，就群体加权和偏差映射对这些理性条件进行了检验．     

混合元解重调和方程的条件数

考虑重调和方程第一边值问题Ω是R~2中的有界多边形区域。根据[1,381—424],问题可转化为 找(u,φ)∈H~1(Ω)×H_0~1(Ω),使成立     

Estimating the manipulation errors in finite element analysis, Part I

In Part I of this two-part work, the relative errors in representing and processing real numbers in digital computers are reviewed, and the computation of the digits lost from the relative errors is shown. The upper bound estimate of the relative error in the solution of Kξ = p for the displacements ξ is given as a function of the condition number of the stiffness matrix K, and the relative errors in K and the load vector p. The computation of relative errors for p and K by equilibrium checks is outlined, and various estimates for the condition number of the stiffness matrix are given.     

纯应力平面弹性问题的一个非协调矩形元(英文)

针对纯应力平面弹性问题构造了一个非协调矩形元.该单元满足离散的第二Korn不等式,并且关于λ有一致最优收敛阶,其误差的能量模和L2-模分别为O(h2)和O(h3) .     

Repeated Red-Black ordering: a new approach

Hereafter, we describe and analyze, from both a theoretical and a numerical point of view, an iterative method for efficiently solving symmetric elliptic problems with possibly discontinuous coefficients. In the following, we use the Preconditioned Conjugate Gradient method to solve the symmetric positive definite linear systems which arise from the finite element discretization of the problems. We focus our interest on sparse and efficient preconditioners. In order to define the preconditioners, we perform two steps: first we reorder the unknowns and then we carry out a (modified) incomplete factorization of the original matrix. We study numerically and theoretically two preconditioners, the second preconditioner corresponding to the one investigated by Brand and Heinemann [2]. We prove convergence results about the Poisson equation with either Dirichlet or periodic boundary conditions. For a meshsizeh, Brand proved that the condition number of the preconditioned system is bounded byO(h ^–1/2) for Dirichlet boundary conditions. By slightly modifying the preconditioning process, we prove that the condition number is bounded byO(h ^–1/3).     

MIXED FINITE ELEMENT METHODS BASED ON RIESZ-REPRESENTING OPERATORS FOR THE SHELL PROBLEM

1. IntroductionAs far as the shell problem is concerned, [l] established a mixed formulation in the clas-sical W that the K-ellipticity and the lnfSup condition are introduced. Unfortunately it isvery dndcult to construct ndxed elemellts simultaneously satisfying the K-ellipticity and theInfSup conditionI2], which are indeed prerequisites Of the stability and the convergence. Inaddition, the indefiniteness of the resulting linear algebraic system complicates the solutionalgorithIn.ffecentl…