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]

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]