A wavelet-based nested iteration–inexact conjugate gradient algorithm for adaptively solving elliptic PDEs

In Cohen et al. (Math Comput 70:27–75, 2001), a new paradigm for the adaptive solution of linear elliptic partial differential equations (PDEs) was proposed, based on wavelet discretizations. Starting from a well-conditioned representation of the linear operator equation in infinite wavelet coordinates, one performs perturbed gradient iterations involving approximate matrix–vector multiplications of finite portions of the operator. In a bootstrap-type fashion, increasingly smaller tolerances guarantee convergence of the adaptive method. In addition, coarsening performed on the iterates allow one to prove asymptotically optimal complexity results when compared to the wavelet best N-term approximation. In the present paper, we study adaptive wavelet schemes for symmetric operators employing inexact conjugate gradient routines. Inspired by fast schemes on uniform grids, we incorporate coarsening and the adaptive application of the elliptic operator into a nested iteration algorithm. Our numerical results demonstrate that the runtime of the algorithm is linear in the number of unknowns and substantial savings in memory can be achieved in two and three space dimensions.     

Stability of the space identification problem for the elliptic‐telegraph differential equation

The present paper is devoted to study the space identification problem for the elliptic‐telegraph differential equation in Hilbert spaces with the self‐adjoint positive definite operator. The main theorem on the stability of the space identification problem for the elliptic‐telegraph differential equation is proved. In applications, theorems on the stability of three source identification problems for one dimensional with nonlocal conditions and multidimensional elliptic‐telegraph differential equations are established.     

An optimal adaptive wavelet method for nonsymmetric and indefinite elliptic problems

In this paper, we modify the adaptive wavelet algorithm from Gantumur et al. [An optimal adaptive wavelet method without coarsening of the iterands, Technical Report 1325, Department of Mathematics, Utrecht University, March 2005, Math. Comp., to appear] so that it applies directly, i.e., without forming the normal equation, not only to self-adjoint elliptic operators but also to operators of the form L=A+B$L=A+B$, where A is self-adjoint elliptic and B is compact, assuming that the resulting operator equation is well posed. We show that the algorithm has optimal computational complexity.     

Divergence-free wavelet solution to the Stokes problem

In this paper, we use divergence-free wavelets to give an adaptive solution to the velocity field of the Stokes problem. We first use divergence-free wavelets to discretize the divergence-free weak formulation of the Stokes problem and obtain a discrete positive definite linear system of equations whose coefficient matrix is quasi-sparse; Secondly, an adaptive scheme is used to solve the discrete linear system of equations and the error estimation and complexity analysis are given.     

An asymptotically optimal Schur complement reduction for the Stokes equation

Summary. In this paper we develop an efficient Schur complement method for solving the 2D Stokes equation. As a basic algorithm, we apply a decomposition approach with respect to the trace of the pressure. The alternative stream function-vorticity reduction is also discussed. The original problem is reduced to solving the equivalent boundary (interface) equation with symmetric and positive definite operator in the appropriate trace space. We apply a mixed finite element approximation to the interface operator by iso triangular elements and prove the optimal error estimates in the presence of stabilizing bubble functions. The norm equivalences for the corresponding discrete operators are established. Then we propose an asymptotically optimal compression technique for the related stiffness matrix (in the absence of bubble functions) providing a sparse factorized approximation to the Schur complement. In this case, the algorithm is shown to have an optimal complexity of the order , q = 2 or q = 3, depending on the geometry, where N is the number of degrees of freedom on the interface. In the presence of bubble functions, our method has the complexity arithmetical operations. The Schur complement interface equation is resolved by the PCG iterations with an optimal preconditioner. Received March 20, 1996 / Revised version received October 28, 1997     

Adaptive Wavelet Methods II—Beyond the Elliptic Case

This paper is concerned with the design and analysis of adaptive wavelet methods for systems of operator equations. Its main accomplishment is to extend the range of applicability of the adaptive wavelet-based method developed in [17] for symmetric positive definite problems to indefinite or unsymmetric systems of operator equations. This is accomplished by first introducing techniques (such as the least squares formulation developed in [26]) that transform the original (continuous) problem into an equivalent infinite system of equations which is now well-posed in the Euclidean metric. It is then shown how to utilize adaptive techniques to solve the resulting infinite system of equations. This second step requires a significant modification of the ideas from [17]. The main departure from [17] is to develop an iterative scheme that directly applies to the infinite-dimensional problem rather than finite subproblems derived from the infinite problem. This rests on an adaptive application of the infinite-dimensional operator to finite vectors representing elements from finite-dimensional trial spaces. It is shown that for a wide range of problems, this new adaptive method performs with asymptotically optimal complexity, i.e., it recovers an approximate solution with desired accuracy at a computational expense that stays proportional to the number of terms in a corresponding wavelet-best N -term approximation. An important advantage of this adaptive approach is that it automatically stabilizes the numerical procedure so that, for instance, compatibility constraints on the choice of trial spaces, like the LBB condition, no longer arise.     

关于分块松弛算子中拟边界Jacobi成份的影响

分布式存贮并行计算环境中，高效率的获取一般通过区域分解或数据分割实现大粒度并行~[4]。因此，对于有效求解偏微分方程的多重网格算法~([1]、[7]),并行计算均采用网格划分进行任务分配~[6]以实现大料度并行。通讯的主体存在于松弛算子，其并行度是影响算法并行效率高低的关键因素。     

A three-level BDDC algorithm for a saddle point problem

BDDC algorithms have previously been extended to the saddle point problems arising from mixed formulations of elliptic and incompressible Stokes problems. In these two-level BDDC algorithms, all iterates are required to be in a benign space, a subspace in which the preconditioned operators are positive definite. This requirement can lead to large coarse problems, which have to be generated and factored by a direct solver at the beginning of the computation and they can ultimately become a bottleneck. An additional level is introduced in this paper to solve the coarse problem approximately and to remove this difficulty. This three-level BDDC algorithm keeps all iterates in the benign space and the conjugate gradient methods can therefore be used to accelerate the convergence. This work is an extension of the three-level BDDC methods for standard finite element discretization of elliptic problems and the same rate of convergence is obtained for the mixed formulation of the same problems. Estimate of the condition number for this three-level BDDC methods is provided and numerical experiments are discussed.     

Adaptive frame methods for elliptic operator equations

This paper is concerned with the development of adaptive numerical methods for elliptic operator equations. We are especially interested in discretization schemes based on frames. The central objective is to derive an adaptive frame algorithm which is guaranteed to converge for a wide range of cases. As a core ingredient we use the concept of Gelfand frames which induces equivalences between smoothness norms and weighted sequence norms of frame coefficients. It turns out that this Gelfand characteristic of frames is closely related to their localization properties. We also give constructive examples of Gelfand wavelet frames on bounded domains. Finally, an application to the efficient adaptive computation of canonical dual frames is presented.     

椭圆边界上的自然积分算子及各向异性外问题的耦合算法

1.引 言为求解微分方程的外边值问题常需要引进人工边界（见[1-4]）,对人工边界外部区域作自然边界归化得到的自然积分方程即Dirichlet-Neumann映射,正是人工边界上的准确的边界条件（见[2-6]）,这是一类非局部边界条件.自然积分算子即Dirichlet-Neumann算子,     

Discontinuous Legendre wavelet element method for elliptic partial differential equations

By incorporating the Legendre multiwavelet into the discontinuous Galerkin (DG) method, this paper presents a novel approach for solving Poisson’s equation with Dirichlet boundary, which is known as the discontinuous Legendre multiwavelet element (DLWE) method, derive an adaptive algorithm for the method, and estimate the approximating error of its numerical fluxes. One striking advantage of our method is that the differential operator, boundary conditions and numerical fluxes involved in the elementwise computation can be done with lower time cost. Numerical experiments demonstrate the validity of this method. Furthermore, this paper generalizes the DLWE method to the general elliptic equations defined on a bounded domain and describes the possibilities of constructing optimal adaptive algorithm. The proposed method and its generalizations are also applicable to some other kinds of partial differential equations.     

Numerical solution to a stokes interface problem

A numerical algorithm is described for solving the generalized eigenvalue problem arising in the study of the spectrum of a preconditioned operator in the pressure equation derived from a Stokes interface problem. The algorithm is implemented for two finite element schemes. It is tested for a problem with an analytical solution and is applied to spectrum computations in the case of a piecewise constant viscosity. A large number of numerical experiments are analyzed, and recommendations are given for solving the Stokes interface problem in practice.     

A fast adaptive spectral graph wavelet method for the viscous Burgers' equation on a star-shaped connected graph

Water wave propagation in an open channel network can be described by the viscous Burgers' equation on the corresponding connected graph, possibly with small viscosity. In this paper, we propose a fast adaptive spectral graph wavelet method for the numerical solution of the viscous Burgers' equation on a star-shaped connected graph. The vital feature of spectral graph wavelets is that they can be constructed on any complex network using the graph Laplacian. The essence of the method is that the same operator can be used for the construction of the spectral graph wavelet and the approximation of the differential operator involved in the Burgers' equation. In this paper, two test problems are considered with homogeneous Dirichlet boundary condition. The numerical results show that the method accurately captures the evolution of the localized patterns at all the scales, and the adaptive node arrangement is accordingly obtained. The convergence of the given method is verified, and efficiency is shown using CPU time.     

Numerical solution of evolutionary integral equations with completely monotonic kernel by Runge–Kutta convolution quadrature

We study the numerical solutions of the initial boundary value problems for the Volterra‐type evolutionary integal equations, in which the integral operator is a convolution product of a completely monotonic kernel and a positive definite operator, such as an elliptic partial‐differential operator. The equation is discretized in time by the Runge–Kutta convolution quadrature. Error estimates are derived and numerical experiments reported. © 2014 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq31: 105–142, 2015     

A Geometric Space-Time Multigrid Algorithm for the Heat Equation

We study the time-dependent heat equation on its space-time domain that is discretised by a $k$-spacetree. $k$-spacetrees are a generalisation of the octree concept and are a discretisation paradigm yielding a multiscale representation of dynamically adaptive Cartesian grids with low memory footprint. The paper presents a full approximation storage geometric multigrid implementation for this setting that combines the smoothing properties of multigrid for the equation's elliptic operator with a multiscale solution propagation in time. While the runtime and memory overhead for tackling the all-in-one space-time problem is bounded, the holistic approach promises to exhibit a better parallel scalability than classical time stepping, adaptive dynamic refinement in space and time fall naturally into place, as well as the treatment of periodic boundary conditions of steady cycle systems, on-time computational steering is eased as the algorithm delivers guesses for the solution's long-term behaviour immediately, and, finally, backward problems arising from the adjoint equation benefit from the the solution being available for any point in space and time.     

Two-level Additive Schwarz Preconditioners for Nonconforming Finite Element Methods

Two-level additive Schwarz preconditioners are developed for the nonconforming P1 finite element approximation of scalar second-order symmetric positive definite elliptic boundary value problems, the Morley finite element approximation of the biharmonic equation, and the divergence-free nonconforming P1 finite element approximation of the stationary Stokes equations. The condition numbers of the preconditioned systems are shown to be bounded independent of mesh sizes and the number of subdomains in the case of generous overlap.

     

美式看跌期权定价中的小波方法

本文采用有限差分格式和 Daubechies正交小波 ,提出了一种求解 Black- Scholes方程数值解新算法 .为美式看跌期定价提供了一条新的途径 .利用小波基的自适应性和消失矩特性 ,使偏微分算子矩阵和小波级数稀疏化 ,大大减少了计算量 .     

Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations

Time harmonic Maxwell equations in lossless media lead to a second order differential equation for the electric field involving a differential operator that is neither elliptic nor definite. A Galerkin method using Nedelec spaces can be employed to get approximate solutions numerically. The problem of preconditioning the indefinite matrix arising from this method is discussed here. Specifically, two overlapping Schwarz methods will be shown to yield uniform preconditioners.

     

Solvability of the dirichlet problem for a class of degenerate quasilinear elliptic equations

In a bounded domain of an n-dimensional space one considers the first boundary-value problem for second-order quasilinear elliptic equations having a divergent structure and admitting an implicit degeneracy of a definite type: viz., at the points where the solution vanishes the strong ellipticity of the equation is violated. The dependence of the principal part of the equation on the gradient of the solution is not assumed to be linear. One gives the definition of a generalized solution of the Dirichlet problem for such equations and one shows its existence under the condition of coerciveness (in a definite sense) and of pseudomonotonicity of the differential operator.     

Adaptive Wavelet Methods for Elliptic Operator Equations with Nonlinear Terms

We present an adaptive wavelet method for the numerical solution of elliptic operator equations with nonlinear terms. This method is developed based on tree approximations for the solution of the equations and adaptive fast reconstruction of nonlinear functionals of wavelet expansions. We introduce a constructive greedy scheme for the construction of such tree approximations. Adaptive strategies of both continuous and discrete versions are proposed. We prove that these adaptive methods generate approximate solutions with optimal order in both of convergence and computational complexity when the solutions have certain degree of Besov regularity.