AMLI preconditioner for the p‐version of the FEM

From the literature it is known that the conjugate gradient method with domain decomposition preconditioners is one of the most efficient methods for solving systems of linear algebraic equations resulting from p‐version finite element discretizations of elliptic boundary value problems. One ingredient of such a preconditioner is a preconditioner related to the Dirichlet problems. In the case of Poisson's equation, we present a preconditioner for the Dirichlet problems which can be interpreted as the stiffness matrix K_h,k resulting from the h‐version finite element discretization of a special degenerated problem. We construct an AMLI preconditioner C_h,k for the matrix K_h,k and show that the condition number of C K_h,k is independent of the discretization parameter. This proof is based on the strengthened Cauchy inequality. The theoretical result is confirmed by numerical examples. Copyright © 2003 John Wiley & Sons, Ltd.     

Analysis of a multigrid preconditioner for Crouzeix–Raviart discretization of elliptic partial differential equation with jump coefficients

In this paper, we present a multigrid V‐cycle preconditioner for the linear system arising from piecewise linear nonconforming Crouzeix–Raviart discretization of second‐order elliptic problems with jump coefficients. The preconditioner uses standard conforming subspaces as coarse spaces. We showed that the convergence rates of the (multiplicative) two‐grid and multigrid V‐cycle algorithms will deteriorate rapidly because of large jumps in coefficient. However, the preconditioned systems have only a fixed number of small eigenvalues depending on the large jump in coefficient, and the effective condition numbers are independent of the coefficient and bounded logarithmically with respect to the mesh size. As a result, the two‐grid or multigrid preconditioned conjugate gradient algorithm converges nearly uniformly. We also comment on some major differences of the convergence theory between the nonconforming case and the standard conforming case. Numerical experiments support the theoretical results. Copyright © 2012 John Wiley & Sons, Ltd.     

A multigrid‐based shifted Laplacian preconditioner for a fourth‐order Helmholtz discretization

In this paper, an iterative solution method for a fourth‐order accurate discretization of the Helmholtz equation is presented. The method is a generalization of that presented in (SIAM J. Sci. Comput. 2006; 27 :1471–1492), where multigrid was employed as a preconditioner for a Krylov subspace iterative method. The multigrid preconditioner is based on the solution of a second Helmholtz operator with a complex‐valued shift. In particular, we compare preconditioners based on a point‐wise Jacobi smoother with those using an ILU(0) smoother, we compare using the prolongation operator developed by de Zeeuw in (J. Comput. Appl. Math. 1990; 33 :1–27) with interpolation operators based on algebraic multigrid principles, and we compare the performance of the Krylov subspace method Bi‐conjugate gradient stabilized with the recently introduced induced dimension reduction method, IDR(s). These three improvements are combined to yield an efficient solver for heterogeneous problems. Copyright © 2009 John Wiley & Sons, Ltd.     

Local and parallel finite element method for solving the biharmonic eigenvalue problem of plate vibration

In this paper, we establish a new local and parallel finite element discrete scheme based on the shifted‐inverse power method for solving the biharmonic eigenvalue problem of plate vibration. We prove the local error estimation of finite element solution for the biharmonic equation/eigenvalue problem and prove the error estimation of approximate solution obtained by the local and parallel scheme. When the diameters of three grids satisfy H⁴ = ?(w²) = ?(h), the approximate solutions obtained by our schemes can achieve the asymptotically optimal accuracy. The numerical experiments show that the computational schemes proposed in this paper are effective to solve the biharmonic eigenvalue problem of plate vibration.     

Preconditioning by inverting the Laplacian: an analysis of the eigenvalues

Wolfgang Hackbusch ^{We study the eigenvalues of the operator generated by usingthe inverse of the Laplacian as a preconditioner for self-adjointsecond-order elliptic partial differential equations with smoothcoefficients. It is well-known that the spectral condition numberof the preconditioned operator can be bounded by , where k is the uniformly positive coefficientof the second-order elliptic equation. The purpose of this paperis to study the spectrum of the preconditioned operator. Wewill show that there is a strong relation between the spectrumof this operator and the range of the coefficient function.In the continuous case, we prove, both for mappings definedon Sobolev spaces and in terms of generalized functions, thatthe spectrum of the preconditioned operator contains the rangeof the coefficient function k. In the discrete case, we indicateby numerical examples that the entire discrete spectrum is approximatelygiven by values of k.}     

A C0 interior penalty method for a singularly‐perturbed fourth‐order elliptic problem on a layer‐adapted mesh

We analyze the convergence of a continuous interior penalty (CIP) method for a singularly perturbed fourth‐order elliptic problem on a layer‐adapted mesh. On this anisotropic mesh, we prove under reasonable assumptions uniform convergence of almost order k ? 1 for finite elements of degree k ≥ 2. This result is of better order than the known robust result on standard meshes. A by‐product of our analysis is an analytic lower bound for the penalty of the symmetric CIP method. Finally, our convergence result is verified numerically. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 838–861, 2014     

A domain decomposition preconditioner for hermite collocation problems

We propose a preconditioning method for linear systems of equations arising from piecewise Hermite bicubic collocation applied to two‐dimensional elliptic PDEs with mixed boundary conditions. We construct an efficient, parallel preconditioner for the GMRES method. The main contribution of the article is a novel interface preconditioner derived in the framework of substructuring and employing a local Hermite collocation discretization for the interface subproblems based on a hybrid fine‐coarse mesh. Interface equations based on this mesh depend only weakly on unknowns associated with subdomains. The effectiveness of the proposed method is highlighted by numerical experiments that cover a variety of problems. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 19: 135–151, 2003     

A highly accurate numerical solution of a biharmonic equation

The coefficients for a nine–point high–order accuracy discretization scheme for a biharmonic equation ∇ ⁴u = f(x, y) (∇² is the two–dimensional Laplacian operator) are derived. The biharmonic problem is defined on a rectangular domain with two types of boundary conditions: (1) u and ∂²u/∂n² or (2) u and ∂u/part;n (where ∂/part;n is the normal to the boundary derivative) are specified at the boundary. For both considered cases, the truncation error for the suggested scheme is of the sixth-order O(h⁶) on a square mesh (h_x = h_y = h) and of the fourth-order O(h⁴_xh²_xh²_y h⁴_y) on an unequally spaced mesh. The biharmonic equation describes the deflection of loaded plates. The advantage of the suggested scheme is demonstrated for solving problems of the deflection of rectangular plates for cases of different boundary conditions: (1) a simply supported plate and (2) a plate with built-in edges. In order to demonstrate the high–order accuracy of the method, the numerical results are compared with exact solutions. © John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 13: 375–391, 1997     

Time evolution of discrete fourth‐order elliptic operators

The evolution equation is considered. A discrete parabolic methodology is developed, based on a discrete elliptic (fourth‐order) calculus. The main ingredient of this calculus is a discrete biharmonic operator (DBO). In the general case, it is shown that the approximate solutions converge to the continuous one. An “almost optimal” convergence result (O(h^{4 ? ?})) is established in the case of constant coefficients, in particular in the pure biharmonic case. Several numerical test cases are presented that not only corroborate the theoretical accuracy result, but also demonstrate high‐order accuracy of the method in nonlinear cases. The nonlinear equations include the well‐studied Kuramoto–Sivashinsky equation. Numerical solutions for this equation are shown to approximate remarkably well the exact solutions. The numerical examples demonstrate the great improvement achieved by using the DBO instead of the standard (five‐point) discrete bilaplacian.     

C1natural neighbor interpolant for partial differential equations

Natural neighbor coordinates [20] are optimum weighted‐average measures for an irregular arrangement of nodes in ℝⁿ. [26] used the notion of Bézier simplices in natural neighbor coordinates Φ to propose a C¹ interpolant. The C¹ interpolant has quadratic precision in Ω ⊂ ℝ², and reduces to a cubic polynomial between adjacent nodes on the boundary ∂Ω. We present the C¹ formulation and propose a computational methodology for its numerical implementation (Natural Element Method) for the solution of partial differential equations (PDEs). The approach involves the transformation of the original Bernstein basis functions B(Φ) to new shape functions Ψ (Φ), such that the shape functions ψ_3I−2(Φ), ψ_3I−1(Φ), and ψ_3I(Φ) for node I are directly associated with the three nodal degrees of freedom w_I, , respectively. The C¹ shape functions interpolate to nodal function and nodal gradient values, which renders the interpolant amenable to application in a Galerkin scheme for the solution of fourth‐order elliptic PDEs. Results for the biharmonic equation with Dirichlet boundary conditions are presented. The generalized eigenproblem is studied to establish the ellipticity of the discrete biharmonic operator, and consequently the stability of the numerical method. © 1999 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 15: 417–447, 1999     

An iterative method based on equation decomposition for the fourth‐order singular perturbation problem

In this article, we propose an iterative method based on the equation decomposition technique ( 1 ) for the numerical solution of a singular perturbation problem of fourth‐order elliptic equation. At each step of the given method, we only need to solve a boundary value problem of second‐order elliptic equation and a second‐order singular perturbation problem. We prove that our approximate solution converges to the exact solution when the domain is a disc. Our numerical examples show the efficiency and accuracy of our method. Our iterative method works very well for singular perturbation problems, that is, the case of 0 < ε ? 1, and the convergence rate is very fast. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

STRICHARTZ ESTIMATES FOR A SCHRÖDINGER OPERATOR WITH NONSMOOTH COEFFICIENTS

ABSTRACT

We prove Strichartz type estimates for the Schrödinger equation corresponding to a second order elliptic operator with variable coefficients. We assume that the coefficients are a C ² compactly supported perturbation of the identity, satisfying a nontrapping condition.     

Exact elliptic compactons in generalized Korteweg–De Vries equations

Using the action principle, and assuming a solitary wave of the generic form u(x,t) = AZ(β(x + q(t)), we derive a general theorem relating the energy, momentum, and velocity of any solitary wave solution of the generalized Korteweg‐De Vries equation K*(l,p). Specifically we find that , where l,p are nonlinearity parameters. We also relate the amplitude, width, and momentum to the velocity of these solutions. We obtain the general condition for linear and Lyapunov stability. We then obtain a two‐parameter family of exact solutions to these equations, which include elliptic and hyper‐elliptic compacton solutions. For this general family we explicitly verify both the theorem and the stability criteria. © 2006 Wiley Periodicals, Inc. Complexity 11: 30–34, 2006     

High‐order characteristic‐tracking strategy for simulation of a nonlinear advection–diffusion equation

In this study, new high‐order backward semi‐Lagrangian methods are developed to solve nonlinear advection–diffusion type problems, which are realized using high‐order characteristic‐tracking strategies. The proposed characteristic‐tracking strategies are second‐order L‐stable and third‐order L(α)‐stable methods, which are based on a classical implicit multistep method combined with a error‐correction method. We also use backward differentiation formulas and the fourth‐order finite‐difference scheme for diffusion problem discretization in the temporal and spatial domains, respectively. To demonstrate the adaptability and efficiency of these time‐discretization strategies, we apply these methods to nonlinear advection–diffusion type problems such as the viscous Burgers' equation. Through simulations, not only the temporal and spatial accuracies are numerically evaluated but also the proposed methods are shown to be superior to the compared existing characteristic‐tracking methods under the same rates of convergence in terms of accuracy and efficiency. Finally, we have shown that the proposed method well preserves the energy and mass when the viscosity coefficient becomes zero.     

Optimal uniform error estimates for moving least‐squares collocation with application to option pricing under jump‐diffusion processes

In this study, we derive optimal uniform error bounds for moving least‐squares (MLS) mesh‐free point collocation (also called finite point method) when applied to solve second‐order elliptic partial integro‐differential equations (PIDEs). In the special case of elliptic partial differential equations (PDEs), we show that our estimate improves the results of Cheng and Cheng (Appl. Numer. Math. 58 (2008), no. 6, 884–898) both in terms of the used error norm (here the uniform norm and there the discrete vector norm) and the obtained order of convergence. We then present optimal convergence rate estimates for second‐order elliptic PIDEs. We proceed by some numerical experiments dealing with elliptic PDEs that confirm the obtained theoretical results. The article concludes with numerical approximation of the linear parabolic PIDE arising from European option pricing problem under Merton's and Kou's jump‐diffusion models. The presented computational results (including the computation of option Greeks) and comparisons with other competing approaches suggest that the MLS collocation scheme is an efficient and reliable numerical method to solve elliptic and parabolic PIDEs arising from applied areas such as financial engineering.     

Existence of solutions for some non‐Fredholm integro‐differential equations with the bi‐Laplacian

We prove the existence of solutions for some semilinear elliptic equations in the appropriate H⁴ spaces using the fixed‐point technique where the elliptic equation contains fourth‐order differential operators with and without Fredholm property, generalizing the previous results.     

Circulant preconditioners for pricing options

We use the normalized preconditioned conjugate gradient method with Strang’s circulant preconditioner to solve a nonsymmetric Toeplitz system A_nx=b, which arises from the discretization of a partial integro-differential equation in option pricing. By using the definition of family of generating functions introduced in [16], we prove that Strang’s circulant preconditioner leads to a superlinear convergence rate under certain conditions. Numerical results exemplify our theoretical analysis.     

Screen‐type boundary value problems for polymetaharmonic equations

In this paper, we consider the three‐dimensional Riquier‐type and Dirichlet‐type screen boundary value problems for the polymetaharmonic equation with real wave numbers k₁ and k₂. We investigate these problems by means of the potential method and the theory of pseudodifferential equations, prove the existence and uniqueness of solutions in Sobolev–Slobodetski spaces, and on the basis of asymptotic analysis, we establish the best Hölder smoothness results for solutions. Copyright © 2012 John Wiley & Sons, Ltd.     

On regularized Hermitian splitting iteration methods for solving discretized almost‐isotropic spatial fractional diffusion equations

The shifted finite‐difference discretization of the one‐dimensional almost‐isotropic spatial fractional diffusion equation results in a discrete linear system whose coefficient matrix is a sum of two diagonal‐times‐Toeplitz matrices. For this kind of linear systems, we propose a class of regularized Hermitian splitting iteration methods and prove its asymptotic convergence under mild conditions. For appropriate circulant‐based approximation to the corresponding regularized Hermitian splitting preconditioner, we demonstrate that the induced fast regularized Hermitian splitting preconditioner possesses a favorable preconditioning property. Numerical results show that, when used to precondition Krylov subspace iteration methods such as generalized minimal residual and biconjugate gradient stabilized methods, the fast preconditioner significantly outperforms several existing ones.     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.