共查询到20条相似文献,搜索用时 656 毫秒
1.
Preconditioners based on various multilevel extensions of two‐level finite element methods (FEM) lead to iterative methods which have an optimal order computational complexity with respect to the size of the system. Such methods were first presented in Axelsson and Padiy (SIAM. J. Sci. Stat. Comp. 1990; 20 :1807) and Axelsson and Vassilevski (Numer. Math. 1989; 56 :157), and are based on (recursive) two‐level splittings of the finite element space. The key role in the derivation of optimal convergence rate estimates is played by the constant γ in the so‐called Cauchy–Bunyakowski–Schwarz (CBS) inequality, associated with the angle between the two subspaces of the splitting. It turns out that only existence of uniform estimates for this constant is not enough but accurate quantitative bounds for γ have to be found as well. More precisely, the value of the upper bound for γ∈(0,1) is part of the construction of various multilevel extensions of the related two‐level methods. In this paper, an algebraic two‐level preconditioning algorithm for second‐order elliptic boundary value problems is constructed, where the discretization is done using Crouzeix–Raviart non‐conforming linear finite elements on triangles. An important point to make is that in this case the finite element spaces corresponding to two successive levels of mesh refinements are not nested. To handle this, a proper two‐level basis is considered, which enables us to fit the general framework for the construction of two‐level preconditioners for conforming finite elements and to generalize the method to the multilevel case. The major contribution of this paper is the derived estimates of the related constant γ in the strengthened CBS inequality. These estimates are uniform with respect to both coefficient and mesh anisotropy. To our knowledge, the results presented in the paper are the first such estimates for non‐conforming FEM systems. Copyright © 2004 John Wiley & Sons, Ltd. 相似文献
2.
Petia Boyanova Svetozar Margenov 《Journal of Computational and Applied Mathematics》2010,235(2):380-390
For the iterative solution of linear systems of equations arising from finite element discretization of elliptic problems there exist well-established techniques to construct numerically efficient and computationally optimal preconditioners. Among those, most often preferred choices are Multigrid methods (geometric or algebraic), Algebraic MultiLevel Iteration (AMLI) methods, Domain Decomposition techniques.In this work, the method in focus is AMLI. We extend its construction and the underlying theory over to systems arising from discretizations of parabolic problems, using non-conforming finite element methods (FEM). The AMLI method is based on an approximated block two-by-two factorization of the original system matrix. A key ingredient for the efficiency of the AMLI preconditioners is the quality of the utilized block two-by-two splitting, quantified by the so-called Cauchy-Bunyakowski-Schwarz (CBS) constant, which measures the abstract angle between the two subspaces, associated with the two-by-two block splitting of the matrix.The particular choice of space discretization for the parabolic equations, used in this paper, is Crouzeix-Raviart non-conforming elements on triangular meshes. We describe a suitable splitting of the so-arising matrices and derive estimates for the associated CBS constant. The estimates are uniform with respect to discretization parameters in space and time as well as with respect to coefficient and mesh anisotropy, thus providing robustness of the method. 相似文献
3.
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. 相似文献
4.
Peter Oswald 《Numerical Linear Algebra with Applications》1995,2(6):487-505
Recently, some new multilevel preconditioners for solving elliptic finite element discretizations by iterative methods have been proposed. They are based on appropriate splittings of the finite element spaces under consideration, and may be analyzed within the framework of additive Schwarz schemes. In this paper we discuss some multilevel methods for discretizations of the fourth-order biharmonic problem by rectangular elements and derive optimal estimates for the condition numbers of the preconditioned linear systems. For the Bogner–Fox–Schmit rectangle, the generalization of the Bramble–Pasciak–Xu method is discussed. As a byproduct, an optimal multilevel preconditioner for nonconforming discretizations by Adini elements is also derived. 相似文献
5.
Christoph Pflaum 《Numerical Linear Algebra with Applications》1999,6(8):701-728
We study the convergence rate of multilevel algorithms from an algebraic point of view. This requires a detailed analysis of the constant in the strengthened Cauchy–Schwarz inequality between the coarse‐grid space and a so‐called complementary space. This complementary space may be spanned by standard hierarchical basis functions, prewavelets or generalized prewavelets. Using generalized prewavelets, we are able to derive a constant in the strengthened Cauchy–Schwarz inequality which is less than 0.31 for the L2 and H1 bilinear form. This implies a convergence rate less than 0.15. So, we are able to prove fast multilevel convergence. Furthermore, we obtain robust estimations of the convergence rate for a large class of anisotropic ellipic equations, even for some that are not H1‐elliptic. Copyright © 1999 John Wiley & Sons, Ltd. 相似文献
6.
Summary.
In this paper we introduce a class of robust multilevel
interface solvers for two-dimensional
finite element discrete elliptic problems with highly
varying coefficients corresponding to geometric decompositions by a
tensor product of strongly non-uniform meshes.
The global iterations convergence rate is shown to be of
the order
with respect to the number of degrees
of freedom on the single subdomain boundaries, uniformly upon the
coarse and fine mesh sizes, jumps in the coefficients
and aspect ratios of substructures.
As the first approach, we adapt the frequency filtering techniques
[28] to construct robust smoothers
on the highly non-uniform coarse grid. As an alternative, a multilevel
averaging procedure for successive coarse grid correction is
proposed and analyzed.
The resultant multilevel coarse grid
preconditioner is shown to have (in a two level case) the condition
number independent
of the coarse mesh grading and
jumps in the coefficients related to the coarsest refinement level.
The proposed technique exhibited high serial and parallel
performance in the skin diffusion processes modelling [20]
where the high dimensional coarse mesh problem inherits a strong geometrical
and coefficients anisotropy.
The approach may be also applied to magnetostatics problems
as well as in some composite materials simulation.
Received December 27, 1994 相似文献
7.
I. Pultarová 《Numerical Linear Algebra with Applications》2009,16(5):415-430
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. 相似文献
8.
We introduce a numerical method for solving an anisotropic elliptic problem. We address the case where the direction of the anisotropy varies, and the anisotropy is high. A finite volume scheme is implemented to solve the problem for small anisotropy ratio, then the parameterization method consists in devising an extrapolation of the solution of the anisotropic problem by combining solutions of a sequence of isotropic problems. To cite this article: P. Guillaume, V. Latocha, C. R. Acad. Sci. Paris, Ser. I 337 (2003). 相似文献
9.
We consider anisotropic second order elliptic boundary value problems in two dimensions, for which the anisotropy is exactly aligned with the coordinate axes. This includes cases where the operator features a singular perturbation in one coordinate direction, whereas its restriction to the other direction remains neatly elliptic. Most prominently, such a situation arises when polar coordinates are introduced.The common multigrid approach to such problems relies on line relaxation in the direction of the singular perturbation combined with semi-coarsening in the other direction. Taking the idea from classical Fourier analysis of multigrid, we employ eigenspace techniques to separate the coordinate directions. Thus, convergence of the multigrid method can be examined by looking at one-dimensional operators only. In a tensor product Galerkin setting, this makes it possible to confirm that the convergence rates of the multigrid V-cycle are bounded independently of the number of grid levels involved. In addition, the estimates reveal that convergence is also robust with respect to a singular perturbation in one coordinate direction.Finally, we supply numerical evidence that the algorithm performs satisfactorily in settings more general than those covered by the proof. 相似文献
10.
Y. Notay 《Numerische Mathematik》1998,80(3):397-417
Summary. This paper deals with the iterative solution of large sparse symmetric positive definite systems. We investigate preconditioning
techniques of the two-level type that are based on a block factorization of the system matrix. Whereas the basic scheme assumes
an exact inversion of the submatrix related to the first block of unknowns, we analyze the effect of using an approximate
inverse instead. We derive condition number estimates that are valid for any type of approximation of the Schur complement
and that do not assume the use of the hierarchical basis. They show that the two-level methods are stable when using approximate inverses
based on modified ILU techniques, or explicit inverses that meet some row-sum criterion. On the other hand, we bring to the
light that the use of standard approximate inverses based on convergent splittings can have a dramatic effect on the convergence
rate. These conclusions are numerically illustrated on some examples
Received March 3, 1997 / Revised version received July 16, 1997 相似文献
11.
In this paper, we derive robust a posteriori error estimates for conforming approximations to a singularly perturbed reaction-diffusion problem on anisotropic meshes, since the solution in general exhibits anisotropic features, e.g., strong boundary or interior layers. Based on the anisotropy of the mesh elements, we improve the a posteriori error estimates developed by Cheddadi et al., which are reliable and efficient on isotropic meshes but fail on anisotropic ones. Without the assumption that the mesh is shape-regular, the resulting mesh-dependent error estimator is shown to be reliable, efficient and robust with respect to the reaction coefficient, as long as the anisotropic mesh sufficiently reflects the anisotropy of the solution. We present our results in the framework of the vertex-centered finite volume method but their nature is general for any conforming one, like the piecewise linear finite element one. Our estimates are based on the usual H(div)-conforming, locally conservative flux reconstruction in the lowest-order Raviart-Thomas space on a dual mesh associated with the original anisotropic simplex one. Numerical experiments in 2D confirm that our estimates are reliable, efficient and robust on anisotropic meshes. 相似文献
12.
Owe Axelsson 《Numerical Algorithms》1999,21(1-4):23-47
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. 相似文献
13.
Guozhu Yu Jinchao Xu Ludmil T. Zikatanov 《Numerical Linear Algebra with Applications》2013,20(5):832-851
This paper is on the convergence analysis for two‐grid and multigrid methods for linear systems arising from conforming linear finite element discretization of the second‐order elliptic equations with anisotropic diffusion. The multigrid algorithm with a line smoother is known to behave well when the discretization grid is aligned with the anisotropic direction; however, this is not the case with a nonaligned grid. The analysis in this paper is mainly focused on two‐level algorithms. For aligned grids, a lower bound is given for a pointwise smoother, and this bound shows a deterioration in the convergence rate, whereas for ‘maximally’ nonaligned grids (with no edges in the triangulation parallel to the direction of the anisotropy), the pointwise smoother results in a robust convergence. With a specially designed block smoother, we show that, for both aligned and nonaligned grids, the convergence is uniform with respect to the anisotropy ratio and the mesh size in the energy norm. The analysis is complemented by numerical experiments that confirm the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd. 相似文献
14.
白中治 《应用数学学报(英文版)》1999,15(4):385-395
1.IntroductionConsiderthesyllUnetricpositivedeflate(SPD)systemsoflinearequationsthatariseinfiniteelementdiscretisstionsofmanysecond-orderself-adjointellipticboundaryvalueproblems.Tosolvethisclassoflinearsystemsiteratively,AxelssonandVassilevski[1--4]preselltedthealgebraicmultileveliteration(AMLI)methodsbyreasonablyutilizingthemultigridtechniqueandthepolynomialaccelerationstrategy.Thesemethodsareamongthemostefficientiterativesolversbecausetheirpreconditioningmatricesarespectrallyequlvalellt… 相似文献
15.
HYBRIDALGEBRAICMULTILEVELPRECONDITIONINGMETHODS¥BaiZhongzhi(白中治)(FudanUniversity,复旦大学,邮编:200433)Abstract:Aclassofhybridalgebr... 相似文献
16.
The aim of this paper is to display numerical results that show the interest of some multilevel methods for problems of parabolic type. These schemes are based on multilevel spatial splittings and the use of different time steps for the various spatial components. The spatial discretization we investigate is of spectral Fourier type, so the approximate solution naturally splits into the sum of a low frequency component and a high frequency one. The time discretization is of implicit/explicit Euler type for each spatial component. Based on a posteriori estimates, we introduce adaptive one-level and multilevel algorithms. Two problems are considered: the heat equation and a nonlinear problem. Numerical experiments are conducted for both problems using the one-level and the multilevel algorithms. The multilevel method is up to 70% faster than the one-level method.
17.
This paper proposes a stabilization of the classical hierarchical basis (HB) method by modifying the HB functions using some computationally feasible approximate L2-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. 相似文献
18.
白中治 《应用数学学报(英文版)》1999,15(2):132-143
1.IntroductionThediscretizationofmanysecondorderselfadjointellipticboundaryvalueproblemsbythefiniteelementmethodleadstolargesparsesystemsoflinearequationswithsymmetricpositivedefinite(SPD)coefficientmatrices.Fortheselinearsystems,algebraicmultilevelp... 相似文献
19.
Zhong‐Zhi Bai 《Advances in Computational Mathematics》1999,10(2):169-186
A class of modified block SSOR preconditioners is presented for solving symmetric positive definite systems of linear equations,
which arise in the hierarchical basis finite element discretizations of the second order self‐adjoint elliptic boundary value
problems. This class of methods is strongly related to two level methods, standard multigrid methods, and Jacobi‐like hierarchical
basis methods. The optimal relaxation factors and optimal condition numbers are estimated in detail. Theoretical analyses
show that these methods are very robust, and especially well suited to difficult problems with rough solutions, discretized
using highly nonuniform, adaptively refined meshes.
This revised version was published online in June 2006 with corrections to the Cover Date. 相似文献
20.
二阶椭圆问题新的混合元格式 总被引:2,自引:0,他引:2
本文基于二阶椭圆问题一种新的混合变分形式,给出同时满足强椭圆性和B-B条件的任意次的求解格式.理论分析表明这些单元论证简单而且用了较少的自由度达到最优误差估计.同时我们还给出了它们在各向异性网格下的误差估计. 相似文献