Search

We propose in this paper a new minimization algorithm based on a slightly modified version of the scalar auxialiary variable (SAV) approach coupled with a relaxation step and an adaptive strategy. It enjoys several distinct advantages over popular gradient based methods: (i) it is unconditionally energy diminishing with a modified energy which is intrinsically related to the original energy, and thus no parameter tuning is needed for stability; (ii) it allows the use of large step-sizes which can effectively accelerate the convergence rate. We also present a convergence analysis for some SAV based algorithms, which include our new algorithm without the relaxation step as a special case. We apply our new algorithm to several illustrative and benchmark problems and compare its performance with several popular gradient based methods. The numerical results indicate that the new algorithm is very robust, and its adaptive version usually converges significantly faster than those popular gradient decent based methods. [ABSTRACT FROM AUTHOR]

This paper proposes some efficient and accurate adaptive two-grid (ATG) finite element algorithms for linear and nonlinear PDEs. The main idea of these algorithms is to utilize the solutions on the kth-level adaptive meshes to find the solutions on the (k + 1)th-level adaptive meshes which are constructed by performing adaptive element bisections on the k th-level adaptive meshes. These algorithms transform nonsymmetric positive definite (non-SPD) PDEs (resp., nonlinear PDEs) into symmetric positive definite (SPD) PDEs (resp., linear PDEs). The proposed algorithms are both accurate and efficient due to the following advantages: They do not need to solve the nonsymmetric or nonlinear systems; the degrees of freedom are very small, they are easily implemented, and the interpolation errors are very small. Next, this paper constructs residual-type a posteriori error estimators which are shown to be reliable and efficient. The key ingredient in proving the efficiency is to establish an upper bound of the oscillation terms, which may not be higher-order terms due to the low regularity of the numerical solution. Furthermore, the convergence of the algorithms is proved when bisection is used for the mesh refinements. Finally, numerical experiments are provided to verify the accuracy and efficiency of the ATG finite element algorithms compared to regular adaptive finite element algorithms and two-grid finite element algorithms [J. Xu, SIAM J. Numer. Anal., 33 (1996), pp. 1759-1777]. [ABSTRACT FROM AUTHOR]

The integral equation method is widely used in numerical simulations of 2D/3D acoustic and electromagnetic scattering problems, which need a large number of values of the Green's functions. A significant topic is the scattering problems in periodic domains, where the corresponding Green's functions are quasi-periodic. The quasi-periodic Green's functions are defined by series that converge too slowly to be used for calculations. Many mathematicians have developed several efficient numerical methods to calculate quasi-periodic Green's functions. In this paper, we propose a new FFT-based fast algorithm to compute the 2D/3D quasi-periodic Green's functions for both the Helmholtz equations and Maxwell's equations. The convergence results and error estimates are also investigated in this paper. Further, the numerical examples are given to show that, when a large number of values is needed, the new algorithm is very competitive. [ABSTRACT FROM AUTHOR]

The alternating direction method of multipliers (ADMM) has been extensively used in a wide variety of different applications. When large datasets with high-dimensional variables are considered, subproblems arising from the ADMM must be inexactly solved even though they may theoretically have closed-form solutions. Such a scenario immediately poses mathematical ambiguities such as how these subproblems should be accurately solved and whether the convergence can still be guaranteed. Although the ADMM is well known, it seems that these topics should be deeply investigated. In this paper, we study the mathematics of how to implement the ADMM for a large dataset scenarios. More specifically, we attempt to focus on the convex programming case where there is a quadratic function with extremely high-dimensional variables in the objective function of the model; thereby there is a huge-scale system for linear equations needing to be solved at each iteration of the ADMM. It is revealed that there is no need, indeed it is impossible, to exactly solve this linear system, and we attempt to propose an adjustable inexactness criterion to automatically and inexactly solve this linear system. We further attempt to identify the safe-guard number for the internally nested iterations that can sufficiently ensure this inexactness criterion if the linear system would be solved by a standard numerical linear algebra solver. The convergence, together with the worst-case convergence rate measured by the iteration complexity, is rigorously established for the ADMM with inexactly solved subproblems. Some numerical experiments for large datasets of the least absolute shrinkage and selection operator containing millions of variables are reported to show the efficiency of the mentioned inaccurate implementation of the ADMM. [ABSTRACT FROM AUTHOR]

In this paper, we consider a classical algebraic multigrid (AMG) form of optimal interpolation that directly minimizes the two-grid convergence rate and compare it with a so-called ideal interpolation that minimizes a weak approximation property of the coarse space. We study compatible relaxation type estimates for the quality of the coarse grid and derive a new sharp measure using optimal interpolation that provides a guaranteed lower bound on the convergence rate of the resulting two-grid method for a given grid. In addition, we design a generalized bootstrap AMG setup algorithm that computes a sparse approximation to the optimal interpolation matrix. We demonstrate numerically that the bootstrap AMG method with sparse interpolation matrix (and spanning multiple levels) converges faster than the two-grid method with the standard ideal interpolation (a dense matrix) for various scalar diffusion problems with highly varying diffusion coefficient. [ABSTRACT FROM AUTHOR]

In this paper, two applications of linear barycentric rational interpolation are used to derive a difference-quadrature scheme for solving a class of systems of Volterra integro-differential equations of the second kind. The convergence of the proposed method is proved, and the order of convergence is obtained in terms of the parameters of the method. Furthermore, the linear stability of the proposed method with respect to both the basic and convolution test equations is analyzed. All the obtained theoretical results are verified by several numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, two finite difference/element approaches for the time-fractional subdiffusion equation with Dirichlet boundary conditions are developed, in which the time direction is approximated by the fractional linear multistep method and the space direction is approximated by the finite element method. The two methods are unconditionally stable and convergent of order O(τq +hr+1) in the L² norm, where q = 2-β or 2 when the analytical solution to the subdiffusion equation is sufficiently smooth, β (0 < β < 1) is the order of the fractional derivative, τ and h are the step sizes in time and space, respectively, and r is the degree of the polynomial space. The corresponding schemes for the subdiffusion equation with Neumann boundary conditions are presented as well, where the stability and convergence are shown. Numerical examples are provided to verify the theoretical analysis. Comparisons between the algorithms derived in this paper and the existing algorithms are given, which show that our numerical schemes exhibit better performances than the existing ones. [ABSTRACT FROM AUTHOR]

The shifted-inverse iteration based on the multigrid discretizations developed in recent years is an efficient computation method for eigenvalue problems. In this paper, for general self-adjoint eigenvalue problems, including the Maxwell eigenvalue problem and integral operator eigenvalue problem, we establish the inverse iteration with fixed shift based on multigrid discretizations. We study in depth the inverse iteration with fixed shift and Rayleigh quotient iteration based on multigrid discretizations and first prove under general conditions the error estimates and convergence for the iterative solution approximating the exact solution of the original eigenvalue problems, especially in an adaptive fashion. Finally, we present some numerical examples performed to validate our theoretical results. [ABSTRACT FROM AUTHOR]

In this paper, a novel compact operator is derived for the approximation of the Riesz derivative with order α ∈ (1, 2]. The compact operator is proved with fourth-order accuracy. Combining the compact operator in space discretization, a linearized difference scheme is proposed for a two-dimensional nonlinear space fractional Schrödinger equation. It is proved that the difference scheme is uniquely solvable, stable, and convergent with order O(τ² + h4), where τ is the time step size, h = max{h1, h2}, and h1, h2 are space grid sizes in the x direction and the y direction, respectively. Based on the linearized difference scheme, a compact alternating direction implicit scheme is presented and analyzed. Numerical results demonstrate that the compact operator does not bring in extra computational cost but improves the accuracy of the scheme greatly. [ABSTRACT FROM AUTHOR]

In the image processing community, there have recently been many restoration and reconstruction problems that can be reformulated into linearly constrained convex programming models whose objective functions have separable structures. These favorable reformulations have promoted impressive applications of the alternating direction method (ADM) in the field of image processing. At each iteration, the computation of ADM is dominated by solving two subproblems exactly. However, in many restoration and reconstruction applications, it is cither impossible or extremely expensive to obtain exact solutions of these ADM subproblems. This fact urges the development on inexact versions of ADM, which allow the generated ADM subproblems to be solved approximately subject to certain inexactness criteria. In this paper, we develop some truly implementable inexact ADMs whose inexactness criteria controlling the accuracy of the ADM subproblems are easily implementable. The convergence of the new inexact ADMs will be proved. Numerical results on several image processing problems will be given to illustrate the effectiveness of the proposed inexact ADMs. [ABSTRACT FROM AUTHOR]

In this paper, we consider the issue of convergence toward entropy solutions for the high order finite volume weighted essentially nonoscillatory (WENO) scheme and the discontinuous Galerkin (DG) finite element method approximating scalar nonconvex conservation laws. Although such high order nonlinearly stable schemes can usually converge to entropy solutions of convex conservation laws, convergence may fail for certain nonconvex conservation laws. We perform a detailed study to demonstrate such convergence issues for a few representative examples and suggest a modification of the high order schemes based on either first order monotone schemes or a second order entropic projection [Bouchut, Bourdarias, and Perthame, Math. Comp., 65 (1996), pp. 1438-1461] to achieve convergence toward entropy solutions while maintaining high order accuracy in smooth regions. [ABSTRACT FROM AUTHOR]

We consider in this paper the wave scattering problem by an object with Neumann boundary conditions in an anisotropic elastic body. To obtain an efficient numerical method (permitting the use of regular grids) we follow a fictitious domain approach coupled with a first order velocity stress formulation for elastodynamics. We first observe that the method does not always converge when the Qdiv1 - Q0 finite element is used. In particular, the method converges for some scattering object geometries but not for others. Note that the convergence of the Qdiv1 -Q0 finite element method was shown in [E. Bécache, P. Joly, and C. Tsogka, SIAM J. Numer. Anal., 39 (2002), pp. 2109-2132] for the elastodynamic problem in the absence of a scattering object (i.e., without the coupling of the mixed finite elements with the fictitious domain method). Therefore we propose here a modification of the Qdiv1 - Q0 element following the approach in [E. Bécache, J. Rodríguez, and C. Tsogka, On the convergence of the fictitious domain method for wave equation problems, Technical report 5802, INRIA, 2006], where the simpler acoustic case was considered. To study the numerical properties of the new element we carry out a dispersion analysis. Several numerical simulations as well as a numerical convergence analysis show that the proposed method provides a good approximate solution. [ABSTRACT FROM AUTHOR]

This paper is concerned with monotone iterative methods for numerical solutions of a class of nonlinear fourth-order elliptic boundary value problems in a two-dimensional domain. The boundary value problem is discretized by the finite difference method, and two iterative processes, called block Jacobi and block Gauss­Seidel monotone iterations, are presented for the computation of solutions of the finite difference system using either an upper solution or a lower solution as the initial iteration. It is shown that the sequence of iterations converges monotonically to a maximal solution or a minimal solution if the nonlinear function is quasi-monotone nondecreasing. A sufficient condition is given to ensure that the maximal and minimal solutions coincide and their common value is the unique solution of the finite difference system. Similar results are obtained for quasi-monotone nonincreasing functions. An analytical comparison relation between the block Jacobi and block Gauss­Seidel monotone iterations is obtained. It is also shown that the finite difference solution converges to the continuous solution as the mesh size tends to zero. Numerical results by the block monotone iterative schemes are given for two model problems and are compared with the known analytical solutions for accuracy. Also compared are the rates of convergence of the two types of block monotone iterations as well as similar types of pointwise monotone iterations. [ABSTRACT FROM AUTHOR]

This paper deals with a solution approach suitable for composite partial differential equations (PDEs) with interface conditions. We present a general framework based on interface relaxation which provides a uniform platform for building problem solving environments through efficient software integration and for implementing various relaxation schemes. Mathematically, this framework contains many existing domain decomposition methods and also allows the extension to a variety of new relaxers. In particular, we describe a class of relaxers which are suitable for general and complicated interface conditions. Interface relaxation is more general than the traditional domain decomposition methods in that it allows unrelated PDE problems on different subdomains. Convergence analysis, error estimates, and preconditioning strategies are presented which show that these relaxers are competitive with existing domain decomposition methods for model problems involving a single PDE. We present experimental results which demonstrate the wide applicability of this approach. Differences between this approach and other domain decomposition methods are also discussed. [ABSTRACT FROM AUTHOR]