Adaptive frame methods for elliptic operator equations: the steepest descent approach

Massimo Fornasier^¶ Dipartimento di Metodi e Modelli Matematici per le Scienze Applicate, Università "La Sapienza" in Roma, Via Antonio Scarpa, 16/B, I-00161 Roma, Italy Rob Stevenson^|| Department of Mathematics, Utrecht University, PO Box 80.010, NL-3508 TA Utrecht, The Netherlands ^{This paper is concerned with the development of adaptive numericalmethods for elliptic operator equations. We are particularlyinterested in discretization schemes based on wavelet frames.We show that by using three basic subroutines an implementable,convergent scheme can be derived, which, moreover, has optimalcomputational complexity. The scheme is based on adaptive steepestdescent iterations. We illustrate our findings by numericalresults for the computation of solutions of the Poisson equationwith limited Sobolev smoothness on intervals in 1D and L-shapeddomains in 2D.}     

Adaptive wavelet methods for elliptic operator equations: Convergence rates

This paper is concerned with the construction and analysis of wavelet-based adaptive algorithms for the numerical solution of elliptic equations. These algorithms approximate the solution of the equation by a linear combination of wavelets. Therefore, a benchmark for their performance is provided by the rate of best approximation to by an arbitrary linear combination of wavelets (so called -term approximation), which would be obtained by keeping the largest wavelet coefficients of the real solution (which of course is unknown). The main result of the paper is the construction of an adaptive scheme which produces an approximation to with error in the energy norm, whenever such a rate is possible by -term approximation. The range of 0$"> for which this holds is only limited by the approximation properties of the wavelets together with their ability to compress the elliptic operator. Moreover, it is shown that the number of arithmetic operations needed to compute the approximate solution stays proportional to . The adaptive algorithm applies to a wide class of elliptic problems and wavelet bases. The analysis in this paper puts forward new techniques for treating elliptic problems as well as the linear systems of equations that arise from the wavelet discretization.

     

Composite wavelet bases for operator equations

This paper is concerned with the construction of biorthogonal wavelet bases defined on a union of parametric images of the unit -cube. These bases are to satisfy certain requirements imposed by applications to a class of operator equations acting on such domains. This covers also elliptic boundary value problems, although this study is primarily motivated by our previous analysis of wavelet methods for pseudo-differential equations with special emphasis on boundary integral equations. In this case it is natural to model the boundary surface as a union of parametric images of the unit cube. It will be shown how to construct wavelet bases on the surface which are composed of wavelet bases defined on each surface patch. Here the relevant properties are the validity of norm equivalences in certain ranges of Sobolev scales, as well as appropriate moment conditions.

     

Adaptive wavelet frame domain decomposition methods for nonlinear elliptic equations

In this article, we are concerned with the numerical treatment of nonlinear elliptic boundary value problems. Our method of choice is a domain decomposition strategy. Partially following the lines from (Cohen, Dahmen and deVore, SIAM J Numer Anal 41 (2003), 1785–1823; Kappei, Appl Anal J Sci 90 (2011), 1323–1353; Lui, SIAM J Sci Comput 21 (2000), 1506–1523; Stevenson and Werner, Math Comp 78 (2009), 619–644), we develop an adaptive additive Schwarz method using wavelet frames. We show that the method converges with an asymptotically optimal rate and support our theoretical results with numerical tests in one and two space dimensions. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 2013     

Numerical solutions of coupled systems of nonlinear elliptic equations

This article deals with numerical solutions of a general class of coupled nonlinear elliptic equations. Using the method of upper and lower solutions, monotone sequences are constructed for difference schemes which approximate coupled systems of nonlinear elliptic equations. This monotone convergence leads to existence‐uniqueness theorems for solutions to problems with reaction functions of quasi‐monotone nondecreasing, quasi‐monotone nonincreasing and mixed quasi‐monotone types. A monotone domain decomposition algorithm which combines the monotone approach and an iterative domain decomposition method based on the Schwarz alternating, is proposed. An application to a reaction‐diffusion model in chemical engineering is given. © 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 621–640, 2012     

Nonlinear and adaptive frame approximation schemes for elliptic PDEs: Theory and numerical experiments

This article is concerned with adaptive numerical frame methods for elliptic operator equations. We show how specific noncanonical frame expansions on domains can be constructed. Moreover, we study the approximation order of best n‐term frame approximation, which serves as the benchmark for the performance of adaptive schemes. We also discuss numerical experiments for second order elliptic boundary value problems in polygonal domains where the discretization is based on recent constructions of boundary adapted wavelet bases on the interval. © 2008 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Multilevel augmentation methods for differential equations

We develop multilevel augmentation methods for solving differential equations. We first establish a theoretical framework for convergence analysis of the boundary value problems of differential equations, and then construct multiscale orthonormal bases in H₀^m(0,1) spaces. Finally, the multilevel augmentation methods in conjunction with the multiscale orthonormal bases are applied to two-point boundary value problems of both second-order and fourth-order differential equations. Theoretical analysis and numerical tests show that these methods are computationally stable, efficient and accurate. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday with friendship and esteem. Mathematics subject classifications (2000) 65J15, 65R20. Zhongying Chen: Supported in part by the Natural Science Foundation of China under grants 10371137 and 10201034, the Foundation of Doctoral Program of National Higher Education of China under grant 20030558008, Guangdong Provincial Natural Science Foundation of China under grant 1011170 and the Foundation of Zhongshan University Advanced Research Center. Yuesheng Xu: Corresponding author. Supported in part by the US National Science Foundation under grants 9973427 and 0312113, by NASA under grant NCC5-399, by the Natural Science Foundation of China under grant 10371122 and by the Chinese Academy of Sciences under the program of “One Hundred Distinguished Young Scientists”.     

An experimental study of interface relaxation methods for composite elliptic differential equations

The recently proposed simulation framework of interface relaxation for developing multi-domain multi-physics simulation engines is considered. An experimental study of the behavior of two representative interface relaxation methods is presented. Three linear and one non-linear elliptic two-dimensional PDE problems are considered and they are coupled with both cartesian and general decompositions. The characteristics and the effectiveness of the proposed collaborative PDE solving framework in general, and of the two interface relaxation methods in particular are shown.     

Approximation methods for nonlinear operator equations

Let be a real normed linear space and be a uniformly quasi-accretive map. For arbitrary define the sequence by where is a positve real sequence satisfying the following conditions: (i) ; (ii) . For , assume that 0$"> and that , where (the set of all positive integers): and is a strictly increasing function with . It is proved that a Mann-type iteration process converges strongly to . Furthermore if, in addition, is a uniformly continuous map, it is proved, without the condition on , that the Mann-type iteration process converges strongly to . As a consequence, corresponding convergence theorems for fixed points of hemi-contractive maps are proved.

     

Superlinear convergence theorems for Newton-type methods for nonlinear systems of equations

In this paper, someQ-order convergence theorems are given for the problem of solving nonlinear systems of equations when using very general finitely terminating methods for the solution of the associated linear systems. The theorems differ from those of Dembo, Eisenstat, and Steihaug in the different stopping condition and in their applicability to the nonlinear ABS algorithm.Lecture presented at the University of Bergamo, Bergamo, Italy, October 1989.     

A method for constructing solutions to linear systems of partial differential equations

We obtain some conditions of solvability in Sobolev spaces for the systems of linear partial differential equations and deduce the corresponding formulas for solutions to these systems. The solutions are given as the sum of the series whose terms are the iterations of some pseudodifferential operators constructed explicitly.     

The use of second degree normalized implicit conjugate gradient methods for solving large sparse systems of linear equations

Second degree normalized implicit conjugate gradient methods for the numerical solution of self-adjoint elliptic partial differential equations are developed. A proposal for the selection of certain values of the iteration parameters ?_i, γ_i involved in solving two and three-dimensional elliptic boundary-value problems leading to substantial savings in computational work is presented. Experimental results for model problems are given.     

Adaptive methods for boundary integral equations: Complexity and convergence estimates

This paper is concerned with developing numerical techniques for the adaptive application of global operators of potential type in wavelet coordinates. This is a core ingredient for a new type of adaptive solvers that has so far been explored primarily for PDEs. We shall show how to realize asymptotically optimal complexity in the present context of global operators. ``Asymptotically optimal' means here that any target accuracy can be achieved at a computational expense that stays proportional to the number of degrees of freedom (within the setting determined by an underlying wavelet basis) that would ideally be necessary for realizing that target accuracy if full knowledge about the unknown solution were given. The theoretical findings are supported and quantified by the first numerical experiments.

     

Tensor-Krylov methods for large nonlinear equations

In this paper, we describe tensor methods for large systems of nonlinear equations based on Krylov subspace techniques for approximately solving the linear systems that are required in each tensor iteration. We refer to a method in this class as a tensor-Krylov algorithm. We describe comparative testing for a tensor-Krylov implementation versus an analogous implementation based on a Newton-Krylov method. The test results show that tensor-Krylov methods are much more efficient and robust than Newton-Krylov methods on hard nonlinear equations problems.Part of this work was performed while the author was research associate at CERFACS (Centre Européen de Recherche et de Formation Avancée en Calcul Scientifique).Research supported in part by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Adaptive finite element methods for Boussinesq equations

An a posteriori error analysis for Boussinesq equations is derived in this article. Then we compare this new estimate with a previous one developed for a regularized version of Boussinesq equations in a previous work. © 2000 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 16: 214–236, 2000     

Sufficient conditions for the asymptotic optimality of projection methods as applied to operator equations

Sufficient conditions are found for the asymptotic optimality of projection methods as applied to linear operator equations in Hilbert spaces. The conditions are applicable to a wide class of equations when asymptotically optimal projection methods are sought for their solution. Applications illustrating the result are presented.     

Inexact trust region method for large sparse systems of nonlinear equations

The main purpose of this paper is to prove the global convergence of the new trust region method based on the smoothed CGS algorithm. This method is surprisingly convenient for the numerical solution of large sparse systems of nonlinear equations, as is demonstrated by numerical experiments. A modification of the proposed trust region method does not use matrices, so it can be used for large dense systems of nonlinear equations.