Multilevel preconditioning for partition of unity methods: some analytic concepts

This paper is concerned with the construction and analysis of multilevel Schwarz preconditioners for partition of unity methods applied to elliptic problems. We show under which conditions on a given multilevel partition of unity hierarchy (MPUM) one even obtains uniformly bounded condition numbers and how to realize such requirements. The main anlytical tools are certain norm equivalences based on two-level splits providing frames that are stable under taking subsets. This work has been supported in part by the European Community’s Human Potential Programme under contract HPRN-CT-202-00286 (BREAKING COMPLEXITY), by the Leibniz-Programme of the German Research Foundation (DFG), and by the SFB 401 funded by DFG.     

Multilevel preconditioning — Appending boundary conditions by Lagrange multipliers

For saddle point problems stemming from appending essential boundary conditions in connection with Galerkin methods for elliptic boundary value problems, a class of multilevel preconditioners is developed. The estimates are based on the characterization of Sobolev spaces on the underlying domain and its boundary in terms of weighted sequence norms relative to corresponding multilevel expansions. The results indicate how the various ingredients of a typical multilevel framework affect the growth rate of the condition numbers. In particular, it is shown how to realize even condition numbers that are uniformly bounded independently of the discretization.These investigations are motivated by the idea of employing nested refinable shift-invariant spaces as trial spaces covering various types of wavelets that are of advantage for the solution of boundary value problems from other points of view. Instead of incorporating the boundary conditions into the approximation spaces in the Galerkin formulation, they are appended by means of Lagrange multipliers leading to a saddle point problem.The work of the author is partially supported by the Deutsche Forschungsgemeinschaft under grant numbers Ku1028/1-1 and Pr336/4-1.     

A General framework for local interpolation

Summary We present a general framework for the construction of local interpolation methods with a given approximation order. Some applications to multivariate spline spaces are presented.Supported by the National Science Foundation, Contract Nos. DMS-8602337 and DMS-8701190Sponsored by Defense Advanced Research Projects Agency (DARPA), under contract No. MDA 972-88-C-0047 for DARPA Initiative in Concurrent Engineering (DICE)     

A NOTE ON SUNSETS IN SPACES OF BOUNDED LINEAR OPERATORS

In the note the author gives a correct proof of the theorem on sunsets in spaces of bounded linear operators given in the author‘s another paper.     

A matrix lower bound

Four essentially different interpretations of a lower bound for linear operators are shown to be equivalent for matrices (involving inequalities, convex sets, minimax problems, and quotient spaces). Properties stated by von Neumann in a restricted case are satisfied by the lower bound. Applications are made to rank reduction, s-numbers, condition numbers, and pseudospectra. In particular, the matrix lower bound is the distance to the nearest matrix with strictly contained row or column spaces, and it occurs in a condition number formula for any consistent system of linear equations, including those that are underdetermined.     

Multigrid and multilevel methods for quadratic spline collocation

Multigrid methods are developed and analyzed for quadratic spline collocation equations arising from the discretization of one-dimensional second-order differential equations. The rate of convergence of the two-grid method integrated with a damped Richardson relaxation scheme as smoother is shown to be faster than 1/2, independently of the step-size. The additive multilevel versions of the algorithms are also analyzed. The development of quadratic spline collocation multigrid methods is extended to two-dimensional elliptic partial differential equations. Multigrid methods for quadratic spline collocation methods are not straightforward: because the basis functions used with quadratic spline collocation are not nodal basis functions, the design of efficient restriction and extension operators is nontrivial. Experimental results, with V-cycle and full multigrid, indicate that suitably chosen multigrid iteration is a very efficient solver for the quadratic spline collocation equations. Supported by Communications and Information Technology Ontario (CITO), Canada. Supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Computational and Technology Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Geometry of optimality conditions and constraint qualifications

Certain types of necessary optimality conditions for mathematical programming problems are equivalent to corresponding regularity conditions on the constraint set. For any problem, a certain natural optimality condition, dependent upon the particular constraint set, is always satisfied. This condition can be strengthened in numerous ways by invoking appropriate regularity assumptions on the constraint set. Results are presented for Euclidean spaces and some extensions to Banach spaces are given.This work was supported in part by the Office of Naval Research, Contract No. N00014-67-A-0321-0003 (NR-047-095).     

A note on exploiting structure when using slack variables

We show how to exploit the structure inherent in the linear algebra for constrained nonlinear optimization problems when inequality constraints have been converted to equations by adding slack variables and the problem is solved using an augmented Lagrangian method.This research was supported in part by the Advanced Research Projects Agency of the Department of Defense and was monitored by the Air Force Office of Scientific Research under Contract No F49620-91-C-0079. The United States Goverment is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation hereon.Corresponding author.     

Multilevel decompositions of functional spaces

A unified abstract framework for the multilevel decomposition of both Banach and quasi-Banach spaces is presented. The characterization of intermediate spaces and their duals is derived from general Bernstein and Jackson inequalities. Applications to compactly supported biorthogonal wavelet decompositions of families of Besov spaces are also given. The first author was partially supported by grants from MURST (40% Analisi Numerica) and ASI (Contract ASI-92-RS-89), whereas the second author was partially supported by grants from MURST (40% Analisi Funzionale) and CNR (Progetto Strategico “Applicazioni della Matematica per la Tecnologia e la Società”).     

On a direct method for the solution of nearly uncoupled Markov chains

Summary This note is concerned with the accuracy of the solution of nearly uncoupled Markov chains by a direct method based on the LU decomposition. It is shown that plain Gaussian elimination may fail in the presence of rounding errors. A modification of Gaussian elimination with diagonal pivoting and correction of small pivots is proposed and analyzed. It is shown that the accuracy of the solution is affected by two condition numbers associated with aggregation and the coupling respectively.This work was supported in part by the Air Force Office of Sponsored Research under Contract AFOSR-87-0188     

On best error bounds for approximation by piecewise polynomial functions

Summary An analog of the well-known Jackson-Bernstein-Zygmund theory on best approximation by trigonometric polynomials is developed for approximation methods which use piecewise polynomial functions. Interpolation and best approximation by polynomial splines, Hermite and finite element functions are examples of such methods. A direct theorem is proven for methods which are stable, quasi-linear and optimally accurate for sufficiently smooth functions. These assumptions are known to be satisfied in many cases of practical interest. Under a certain additional assumption, on the family of meshes, an inverse theorem is proven which shows that the direct theorem is sharp.The work presented in this paper was supported by the ERDA Mathematics and Computing Laboratory, Courant Institute of Mathematical Sciences, New York University, under Contract E(11-1)-3077 with the Energy Research and Development Administration.     

Ginzburg-Landau equation and motion by mean curvature, II: Development of the initial interface

In this paper, we study the short time behavior of the solutions of a sequence of Ginzburg-Landau equations indexed by ∈. We prove that under appropriate assumptions on the initial data, solutions converge to ±1 in short time and behave like the one-dimensional traveling wave across the interface. In particular, energy remains uniformly bounded in ∈. Partially supported by the NSF Grant DMS-9200801 and by the Army Research Office through the Center for Nonlinear Analysis.     

Preconditioning cubic spline collocation discretizations of elliptic equations

Summary. This work considers the uniformly elliptic operator defined by in (the unit square) with boundary conditions: on and on and its discretization based on Hermite cubic spline spaces and collocation at the Gauss points. Using an interpolatory basis with support on the Gauss points one obtains the matrix . We discuss the condition numbers and the distribution of -singular values of the preconditioned matrices where is the stiffness matrix associated with the finite element discretization of the positive definite uniformly elliptic operator given by in with boundary conditions: on on . The finite element space is either the space of continuous functions which are bilinear on the rectangles determined by Gauss points or the space of continuous functions which are linear on the triangles of the triangulation of using the Gauss points. When we obtain results on the eigenvalues of . In the general case we obtain bounds and clustering results on the -singular values of . These results are related to the results of Manteuffel and Parter [MP], Parter and Wong [PW], and Wong [W] for finite element discretizations as well as the results of Parter and Rothman [PR] for discretizations based on Legendre Spectral Collocation. Received January 1, 1994 / Revised version received February 7, 1995     

Extremal equilibria for monotone semigroups in ordered spaces with application to evolutionary equations

We consider monotone semigroups in ordered spaces and give general results concerning the existence of extremal equilibria and global attractors. We then show some applications of the abstract scheme to various evolutionary problems, from ODEs and retarded functional differential equations to parabolic and hyperbolic PDEs. In particular, we exhibit the dynamical properties of semigroups defined by semilinear parabolic equations in RN with nonlinearities depending on the gradient of the solution. We consider as well systems of reaction-diffusion equations in RN and provide some results concerning extremal equilibria of the semigroups corresponding to damped wave problems in bounded domains or in RN. We further discuss some nonlocal and quasilinear problems, as well as the fourth order Cahn-Hilliard equation.     

Integration and approximation in arbitrary dimensions

We study multivariate integration and approximation for various classes of functions of d variables with arbitrary d. We consider algorithms that use function evaluations as the information about the function. We are mainly interested in verifying when integration and approximation are tractable and strongly tractable. Tractability means that the minimal number of function evaluations needed to reduce the initial error by a factor of ɛ is bounded by C(d)ɛ^−p for some exponent p independent of d and some function C(d). Strong tractability means that C(d) can be made independent of d. The ‐exponents of tractability and strong tractability are defined as the smallest powers of ɛ{^-1} in these bounds. We prove that integration is strongly tractable for some weighted Korobov and Sobolev spaces as well as for the Hilbert space whose reproducing kernel corresponds to the covariance function of the isotropic Wiener measure. We obtain bounds on the ‐exponents, and for some cases we find their exact values. For some weighted Korobov and Sobolev spaces, the strong ‐exponent is the same as the ‐exponent for d=1, whereas for the third space it is 2. For approximation we also consider algorithms that use general evaluations given by arbitrary continuous linear functionals as the information about the function. Our main result is that the ‐exponents are the same for general and function evaluations. This holds under the assumption that the orthonormal eigenfunctions of the covariance operator have uniformly bounded L∞ norms. This assumption holds for spaces with shift-invariant kernels. Examples of such spaces include weighted Korobov spaces. For a space with non‐shift‐invariant kernel, we construct the corresponding space with shift-invariant kernel and show that integration and approximation for the non-shift-invariant kernel are no harder than the corresponding problems with the shift-invariant kernel. If we apply this construction to a weighted Sobolev space, whose kernel is non-shift-invariant, then we obtain the corresponding Korobov space. This enables us to derive the results for weighted Sobolev spaces. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fully discrete approximation methods for the estimation of parabolic systems and boundary parameters

A spatially and temporally discrete numerical approximation scheme is developed for the identification of a class of semilinear parabolic systems with unknown boundary parameters. The identification problem is formulated as a least squares fit to data subject to an equivalent representation for the dynamics in the form of an abstract evolution equation. Finite-dimensional difference equation state approximations are constructed using a cubic spline-based, Galerkin method and the Padé rational function approximations to the exponential. A sequence of approximating identification problems result, the solutions of which are shown to exist and, in a certain sense, approximate solutions to the original identification problem. Numerical results for two examples, one involving the modeling of biological mixing in deep sea sediment cores, and the other, the estimation of transport parameters for indoor mixing, are discussed. In both examples, the identification is based upon actual experimental data.Parts of the research were carried out while the authors were visitors at the Institute for Computer Applications in Science and Engineering (ICASE), NASA Langley Research Center, Hampton, Virginia, which is operated under NASA Contracts No. NAS1-17070 and No. NAS1-17130.Research supported in part by NSF Grant MCS-8205355, AFOSR Contract 81-0198 and ARO Contract ARO-DAAG-29-K-0029.     

Generalized complementarity problem

A general complementarity problem with respect to a convex cone and its polar in a locally convex, vector-topological space is defined. It is observed that, in this general setting, the problem is equivalent to a variational inequality over a convex cone. An existence theorem is established for this general case, from which several of the known results for the finite-dimensional cases follow under weaker assumptions than have been required previously. In particular, it is shown that, if the given map under consideration is strongly copositive with respect to the underlying convex cone, then the complementarity problem has a solution.This research was partially supported by the Office of Naval Research, Contract No. N-00014-67-A0112-0011, by the Atomic Energy Commission, Contract No. AT[04-3]-326-PA-18, and by the National Science Foundation, Grant No. GP-9329.     

A domain decomposition algorithm for elliptic problems in three dimensions

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.     

Co-volume methods for degenerate parabolic problems

Summary A complementary volume (co-volume) technique is used to develop a physically appealing algorithm for the solution of degenerate parabolic problems, such as the Stefan problem. It is shown that, these algorithms give rise to a discrete semigroup theory that parallels the continuous problem. In particular, the discrete Stefan problem gives rise to nonlinear semigroups in both the discreteL ¹ andH ^–1 spaces.The first author was supported by a grant from the Hughes foundation, and the second author was supported by the National Science Foundation Grant No. DMS-9002768 while this work was undertaken. This work was supported by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.     

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