共查询到20条相似文献,搜索用时 15 毫秒
1.
Marcus Sarkis 《Numerische Mathematik》1997,77(3):383-406
Summary. Two-level domain decomposition methods are developed for a simple nonconforming approximation of second order elliptic problems.
A bound is established for the condition number of these iterative methods, that grows only logarithmically with the number
of degrees of freedom in each subregion. This bound holds for two and three dimensions and is independent of jumps in the
value of the coefficients and number of subregions. We introduce face coarse spaces, and isomorphisms to map between conforming
and nonconforming spaces.
ReceivedMarch 1, 1995 / Revised version received January 16, 1996 相似文献
2.
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 相似文献
3.
Xuejun Zhang 《Numerische Mathematik》1992,63(1):521-539
Summary We consider the solution of the algebraic system of equations which result from the discretization of second order elliptic equations. A class of multilevel algorithms are studied using the additive Schwarz framework. We establish that the condition number of the iteration operators are bounded independent of mesh sizes and the number of levels. This is an improvement on Dryja and Widlund's result on a multilevel additive Schwarz algorithm, as well as Bramble, Pasciak and Xu's result on the BPX algorithm. Some multiplicative variants of the multilevel methods are also considered. We establish that the energy norms of the corresponding iteration operators are bounded by a constant less than one, which is independent of the number of levels. For a proper ordering, the iteration operators correspond to the error propagation operators of certain V-cycle multigrid methods, using Gauss-Seidel and damped Jacobi methods as smoothers, respectively.This work was supported in part by the National Science Foundation under Grants NSF-CCR-8903003 at Courant Institute of Mathematical Sciences, New York University and NSF-ASC-8958544 at Department of Computer Science, University of Maryland. 相似文献
4.
Summary. In this paper, the multilevel ILU (MLILU) decomposition is introduced. During an incomplete Gaussian elimination process
new matrix entries are generated such that a special ordering strategy yields distinct levels. On these levels, some smoothing
steps are computed. The MLILU decomposition exists and the corresponding iterative scheme converges for all symmetric and
positive definite matrices. Convergence rates independent of the number of unknowns are shown numerically for several examples.
Many numerical experiments including unsymmetric and anisotropic problems, problems with jumping coefficients as well as realistic
problems are presented. They indicate a very robust convergence behavior of the MLILU method.
Received June 13, 1997 / Revised version received March 17, 1998 相似文献
5.
Summary.
In recent years, it has been shown that many modern iterative algorithms
(multigrid schemes, multilevel preconditioners, domain decomposition
methods etc.)
for solving problems resulting from the discretization
of PDEs can be
interpreted as additive (Jacobi-like) or multiplicative
(Gauss-Seidel-like) subspace correction methods. The key to their
analysis is the study of certain metric properties of the underlying
splitting of the discretization space into a sum of subspaces
and the splitting of the variational problem on into auxiliary problems on
these subspaces.
In this paper, we propose a modification of the abstract convergence
theory of the additive and multiplicative Schwarz methods, that
makes the relation to traditional iteration methods more explicit.
The analysis of the additive and multiplicative Schwarz iterations
can be carried out in almost the same spirit as in the
traditional block-matrix
situation, making convergence proofs of multilevel and domain decomposition
methods clearer, or, at least, more classical.
In addition, we present a
new bound for the convergence rate of the appropriately scaled
multiplicative Schwarz method directly in terms
of the condition number of the corresponding additive
Schwarz operator.
These results may be viewed as an appendix to the
recent surveys [X], [Ys].
Received February 1, 1994 / Revised version received August
1, 1994 相似文献
6.
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. 相似文献
7.
Arnold Reusken 《Numerische Mathematik》1995,71(3):365-397
Summary.
We consider a two-grid method for solving 2D convection-diffusion
problems. The coarse grid correction is based on approximation of
the Schur complement. As a preconditioner of the Schur complement we use the
exact Schur complement of modified fine grid equations. We assume constant
coefficients and periodic boundary conditions and apply Fourier analysis. We
prove an upper bound for the spectral radius of the two-grid iteration
matrix that is smaller than one and independent of the mesh size, the
convection/diffusion ratio and the flow direction; i.e. we have a (strong)
robustness result. Numerical results illustrating the robustness of the
corresponding multigrid -cycle are given.
Received October 14, 1994 相似文献
8.
Summary. Multilevel preconditioners are proposed for the iterative solution of the discrete problems which arise when orthogonal spline
collocation with piecewise Hermite bicubics is applied to the Dirichlet boundary value problem for a self-adjoint elliptic
partial differential equation on a rectangle. Additive and multiplicative preconditioners are defined respectively as sums
and products of independent operators on a sequence of nested subspaces of the fine partition approximation space. A general
theory of additive and multiplicative Schwarz methods is used to prove that the preconditioners are spectrally equivalent
to the collocation discretization of the Laplacian with the spectral constants independent of the fine partition stepsize
and the number of levels. The preconditioned conjugate gradient and preconditioned Orthomin methods are considered for the
solution of collocation problems. An implementation of the methods is discussed and the results of numerical experiments are
presented.
Received March 1, 1994 / Revised version received January 23, 1996 相似文献
9.
Summary.
We develop and analyze a procedure for creating a hierarchical basis of
continuous piecewise linear polynomials on an arbitrary, unstructured,
nonuniform triangular
mesh. Using these hierarchical basis functions, we are able to define
and analyze corresponding iterative methods for solving the linear
systems arising from finite element discretizations of elliptic
partial differential equations. We show that such iterative methods
perform as well as those developed for the usual case of
structured, locally refined meshes. In particular, we show that the
generalized condition numbers for such iterative methods are
of order ,
where is the number of hierarchical basis levels.
Received December 5, 1994 相似文献
10.
Summary.
We consider two level overlapping Schwarz domain decomposition methods
for solving the finite element problems that arise from
discretizations of elliptic problems on general unstructured meshes
in two and three dimensions. Standard finite element interpolation
from
the coarse to the fine grid may be used. Our theory requires no
assumption on the substructures
that constitute the whole domain, so the
substructures can be of arbitrary shape and of different
size. The global coarse mesh is allowed to be non-nested
to the fine grid on which the discrete problem is to be solved, and
neither
the coarse mesh nor the fine mesh need be quasi-uniform.
In addition, the domains defined by the fine and coarse grid need
not be identical. The one important constraint is that the closure
of the coarse grid must cover any portion of the fine grid boundary
for which Neumann boundary conditions are given.
In this general setting, our algorithms have the same optimal
convergence rate as the usual two level overlapping domain decomposition
methods on structured meshes.
The condition number of the preconditioned system depends only on the
(possibly small)
overlap of the
substructures and the size of the coarse grid, but is independent of
the sizes of the subdomains.
Received
March 23, 1994 / Revised version received June 2, 1995 相似文献
11.
Summary. In this paper we consider two aspects of the problem of designing efficient numerical methods for the approximation of semilinear
boundary value problems. First we consider the use of two and multilevel algorithms for approximating the discrete solution.
Secondly we consider adaptive mesh refinement based on feedback information from coarse level approximations. The algorithms
are based on an a posteriori error estimate, where the error is estimated in terms of computable quantities only. The a posteriori
error estimate is used for choosing appropriate spaces in the multilevel algorithms, mesh refinements, as a stopping criterion
and finally it gives an estimate of the total error.
Received April 8, 1997 / Revised version received July 27, 1998 / Published online September 24, 1999 相似文献
12.
The cascadic multigrid method for elliptic problems 总被引:23,自引:0,他引:23
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 相似文献
13.
James H. Bramble Richard E. Ewing Joseph E. Pasciak Jian Shen 《Advances in Computational Mathematics》1996,5(1):15-29
In this paper, we examine multigrid algorithms for cell centered finite difference approximations of second order elliptic boundary value problems. The cell centered application gives rise to one of the simplest non-variational multigrid algorithms. We shall provide an analysis which guarantees that the W-cycle and variable V-cycle multigrid algorithms converge with a rate of iterative convergence which can be bounded independently of the number of multilevel spaces. In contrast, the natural variational multigrid algorithm converges much more slowly. 相似文献
14.
Ralf Kornhuber 《Numerische Mathematik》1996,72(4):481-499
Summary.
We derive globally convergent multigrid methods
for discrete elliptic
variational inequalities of the second kind
as obtained from
the approximation of related continuous
problems by piecewise linear finite elements.
The coarse grid corrections are computed
from certain obstacle problems.
The actual constraints are fixed by the
preceding nonlinear fine grid smoothing.
This new approach allows the implementation
as a classical V-cycle and preserves
the usual multigrid efficiency.
We give estimates
for the asymptotic convergence rates.
The numerical results indicate a significant improvement
as compared with previous multigrid approaches.
Received
March 26, 1994 / Revised version received September 22, 1994 相似文献
15.
Barry F. Smith 《Numerische Mathematik》1991,60(1):219-234
Summary Most domain decomposition algorithms have been developed for problems in two dimensions. One reason for this is the difficulty in devising a satisfactory, easy-to-implement, robust method of providing global communication of information for problems in three dimensions. Several methods that work well in two dimension do not perform satisfactorily in three dimensions.A new iterative substructuring algorithm for three dimensions is proposed. It is shown that the condition number of the resulting preconditioned problem is bounded independently of the number of subdomains and that the growth is quadratic in the logarithm of the number of degrees of freedom associated with a subdomain. The condition number is also bounded independently of the jumps in the coefficients of the differential equation between subdomains. The new algorithm also has more potential parallelism than the iterative substructuring methods previously proposed for problems in three dimensions.This work was supported in part by the National Science Foundation under grant NSF-CCR-8903003 and by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38. 相似文献
16.
Summary. In this paper, the adaptive filtering method is introduced and analysed. This method leads to robust algorithms for the solution
of systems of linear equations which arise from the discretisation of partial differential equations with strongly varying
coefficients. These iterative algorithms are based on the tangential frequency filtering decompositions (TFFD). During the
iteration with a preliminary preconditioner, the adaptive test vector method calculates new test vectors for the TFFD. The
adaptive test vector iterative method allows the combination of the tangential frequency decomposition and other iterative
methods such as multi-grid. The connection with the TFFD improves the robustness of these iterative methods with respect to
varying coefficients. Interface problems as well as problems with stochastically distributed properties are considered. Realistic
numerical experiments confirm the efficiency of the presented algorithms.
Received June 26, 1996 / Revised version received October 7, 1996 相似文献
17.
Summary For solving second order elliptic problems discretized on a sequence of nested mixed finite element spaces nearly optimal iterative methods are proposed. The methods are within the general framework of the product (multiplicative) scheme for operators in a Hilbert space, proposed recently by Bramble, Pasciak, Wang, and Xu [5,6,26,27] and make use of certain multilevel decomposition of the corresponding spaces for the flux variable. 相似文献
18.
Tarek P. Mathew 《Numerische Mathematik》1993,65(1):445-468
Summary We describe sequential and parallel algorithms based on the Schwarz alternating method for the solution of mixed finite element discretizations of elliptic problems using the Raviart-Thomas finite element spaces. These lead to symmetric indefinite linear systems and the algorithms have some similarities with the traditional block Gauss-Seidel or block Jacobi methods with overlapping blocks. The indefiniteness requires special treatment. The sub-blocks used in the algorithm correspond to problems on a coarse grid and some overlapping subdomains and is based on a similar partition used in an algorithm of Dryja and Widlund for standard elliptic problems. If there is sufficient overlap between the subdomains, the algorithm converges with a rate independent of the mesh size, the number of subdomains and discontinuities of the coefficients. Extensions of the above algorithms to the case of local grid refinement is also described. Convergence theory for these algorithms will be presented in a subsequent paper.This work was supported in part by the National Science Foundation under Grant NSF-CCR-8903003, while the author was a graduate student at New York University, and in part by the Army Research Office under Grant DAAL 03-91-G-0150, while the author was a Visiting Assistant Researcher at UCLA 相似文献
19.
Multilevel diagonal scaling preconditioners for boundary element equations on locally refined meshes
Summary. We study a multilevel preconditioner for the Galerkin boundary element matrix arising from a symmetric positive-definite
bilinear form. The associated energy norm is assumed to be equivalent to a Sobolev norm of positive, possibly fractional,
order m on a bounded (open or closed) surface of dimension d, with . We consider piecewise linear approximation on triangular elements. Successive levels of the mesh are created by selectively
subdividing elements within local refinement zones. Hanging nodes may be created and the global mesh ratio can grow exponentially
with the number of levels. The coarse-grid correction consists of an exact solve, and the correction on each finer grid amounts
to a simple diagonal scaling involving only those degrees of freedom whose associated nodal basis functions overlap the refinement zone. Under appropriate assumptions on the choice of refinement zones, the condition number of the preconditioned system is shown
to be bounded by a constant independent of the number of degrees of freedom, the number of levels and the global mesh ratio.
In addition to applying to Galerkin discretisation of hypersingular boundary integral equations, the theory covers finite
element methods for positive-definite, self-adjoint elliptic problems with Dirichlet boundary conditions.
Received October 5, 2001 / Revised version received December 5, 2001 / Published online April 17, 2002
The support of this work through Visiting Fellowship grant GR/N21970 from the Engineering and Physical Sciences Research
Council of Great Britain is gratefully acknowledged. The second author was also supported by the Australian Research Council 相似文献
20.
Domain decomposition for multiscale PDEs 总被引:3,自引:1,他引:2
We consider additive Schwarz domain decomposition preconditioners for piecewise linear finite element approximations of elliptic
PDEs with highly variable coefficients. In contrast to standard analyses, we do not assume that the coefficients can be resolved
by a coarse mesh. This situation arises often in practice, for example in the computation of flows in heterogeneous porous
media, in both the deterministic and (Monte–Carlo simulated) stochastic cases. We consider preconditioners which combine local
solves on general overlapping subdomains together with a global solve on a general coarse space of functions on a coarse grid.
We perform a new analysis of the preconditioned matrix, which shows rather explicitly how its condition number depends on
the variable coefficient in the PDE as well as on the coarse mesh and overlap parameters. The classical estimates for this
preconditioner with linear coarsening guarantee good conditioning only when the coefficient varies mildly inside the coarse
grid elements. By contrast, our new results show that, with a good choice of subdomains and coarse space basis functions,
the preconditioner can still be robust even for large coefficient variation inside domains, when the classical method fails
to be robust. In particular our estimates prove very precisely the previously made empirical observation that the use of low-energy
coarse spaces can lead to robust preconditioners. We go on to consider coarse spaces constructed from multiscale finite elements
and prove that preconditioners using this type of coarsening lead to robust preconditioners for a variety of binary (i.e.,
two-scale) media model problems. Moreover numerical experiments show that the new preconditioner has greatly improved performance
over standard preconditioners even in the random coefficient case. We show also how the analysis extends in a straightforward
way to multiplicative versions of the Schwarz method.
We would like to thank Bill McLean for very useful discussions concerning this work. We would also like to thank Maksymilian
Dryja for helping us to improve the result in Theorem 4.3. 相似文献