A note on the mesh independence of convergence bounds for additive Schwarz preconditioned GMRES

Additive Schwarz preconditioners, when including a coarse grid correction, are said to be optimal for certain discretized partial differential equations, in the sense that bounds on the convergence of iterative methods are independent of the mesh size h. Cai and Zou (Numer. Linear Algebra Appl. 2002; 9 :379–397) showed with a one‐dimensional example that in the absence of a coarse grid correction the usual GMRES bound has a factor of the order of . In this paper we consider the same example and show that for that example the behavior of the method is not well represented by the above‐mentioned bound: We use an a posteriori bound for GMRES from (SIAM Rev. 2005; 47 :247–272) and show that for that example a relevant factor is bounded by a constant. Furthermore, for a sequence of meshes, the convergence curves for that one‐dimensional example, and for several two‐dimensional model problems, are very close to each other; thus, the number of preconditioned GMRES iterations needed for convergence for a prescribed tolerance remains almost constant. Copyright © 2008 John Wiley & Sons, Ltd.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.     

On the geometric convergence of optimized Schwarz methods with applications to elliptic problems

The Schwarz method can be used for the iterative solution of elliptic boundary value problems on a large domain Ω. One subdivides Ω into smaller, more manageable, subdomains and solves the differential equation in these subdomains using appropriate boundary conditions. Optimized Schwarz Methods use Robin conditions on the artificial interfaces for information exchange at each iteration, and for which one can optimize the Robin parameters. While the convergence theory of classical Schwarz methods (with Dirichlet conditions on the artificial interface) is well understood, the overlapping Optimized Schwarz Methods still lack a complete theory. In this paper, an abstract Hilbert space version of the Optimized Schwarz Method (OSM) is presented, together with an analysis of conditions for its geometric convergence. It is also shown that if the overlap is relatively uniform, these convergence conditions are met for Optimized Schwarz Methods for two-dimensional elliptic problems, for any positive Robin parameter. In the discrete setting, we obtain that the convergence factor ρ(h) varies like a polylogarithm of h. Numerical experiments show that the methods work well and that the convergence factor does not appear to depend on h.     

On preconditioned MHSS iteration methods for complex symmetric linear systems

We propose a preconditioned variant of the modified HSS (MHSS) iteration method for solving a class of complex symmetric systems of linear equations. Under suitable conditions, we prove the convergence of the preconditioned MHSS (PMHSS) iteration method and discuss the spectral properties of the PMHSS-preconditioned matrix. Numerical implementations show that the resulting PMHSS preconditioner leads to fast convergence when it is used to precondition Krylov subspace iteration methods such as GMRES and its restarted variants. In particular, both the stationary PMHSS iteration and PMHSS-preconditioned GMRES show meshsize-independent and parameter-insensitive convergence behavior for the tested numerical examples.     

A convergence theory of multilevel additive Schwarz methods on unstructured meshes

We develop a convergence theory for two level and multilevel additive Schwarz domain decomposition methods for elliptic and parabolic problems on general unstructured meshes in two and three dimensions. The coarse and fine grids are assumed only to be shape regular, and the domains formed by the coarse and fine grids need not be identical. In this general setting, our convergence theory leads to completely local bounds for the condition numbers of two level additive Schwarz methods, which imply that these condition numbers are optimal, or independent of fine and coarse mesh sizes and subdomain sizes if the overlap amount of a subdomain with its neighbors varies proportionally to the subdomain size. In particular, we will show that additive Schwarz algorithms are still very efficient for nonselfadjoint parabolic problems with only symmetric, positive definite solvers both for local subproblems and for the global coarse problem. These conclusions for elliptic and parabolic problems improve our earlier results in [12, 15, 16]. Finally, the convergence theory is applied to multilevel additive Schwarz algorithms. Under some very weak assumptions on the fine mesh and coarser meshes, e.g., no requirements on the relation between neighboring coarse level meshes, we are able to derive a condition number bound of the orderO(² L ²), where = max₁lL(h _l +_l– 1)/ _l,h _l is the element size of thelth level mesh, _l the overlap of subdomains on thelth level mesh, andL the number of mesh levels.The work was partially supported by the NSF under contract ASC 92-01266, and ONR under contract ONR-N00014-92-J-1890. The second author was also partially supported by HKRGC grants no. CUHK 316/94E and the Direct Grant of CUHK.     

BCCB preconditioners for systems of BVM‐based numerical integrators

Boundary value methods (BVMs) for ordinary differential equations require the solution of non‐symmetric, large and sparse linear systems. In this paper, these systems are solved by using the generalized minimal residual (GMRES) method. A block‐circulant preconditioner with circulant blocks (BCCB preconditioner) is proposed to speed up the convergence rate of the GMRES method. The BCCB preconditioner is shown to be invertible when the BVM is A_k1,k2‐stable. The spectrum of the preconditioned matrix is clustered and therefore, the preconditioned GMRES method converges fast. Moreover, the operation cost in each iteration of the preconditioned GMRES method by using our BCCB preconditioner is less than that required by using block‐circulant preconditioners proposed earlier. In numerical experiments, we compare the number of iterations of various preconditioners. Copyright © 2003 John Wiley & Sons, Ltd.     

Preconditioners for non‐Hermitian Toeplitz systems

In this paper, we construct new ω‐circulant preconditioners for non‐Hermitian Toeplitz systems, where we allow the generating function of the sequence of Toeplitz matrices to have zeros on the unit circle. We prove that the eigenvalues of the preconditioned normal equation are clustered at 1 and that for (N, N)‐Toeplitz matrices with spectral condition number 𝒪(N^α) the corresponding PCG method requires at most 𝒪(N log² N) arithmetical operations. If the generating function of the Toeplitz sequence is a rational function then we show that our preconditioned original equation has only a fixed number of eigenvalues which are not equal to 1 such that preconditioned GMRES needs only a constant number of iteration steps independent of the dimension of the problem. Numerical tests are presented with PCG applied to the normal equation, GMRES, CGS and BICGSTAB. In particular, we apply our preconditioners to compute the stationary probability distribution vector of Markovian queuing models with batch arrival. Copyright © 2001 John Wiley & Sons, Ltd.     

A priori error estimates for interior penalty versions of the local discontinuous Galerkin method applied to transport equations

The local discontinuous Galerkin method has been developed recently by Cockburn and Shu for convection‐dominated convection‐diffusion equations. In this article, we consider versions of this method with interior penalties for the numerical solution of transport equations, and derive a priori error estimates. We consider two interior penalty methods, one that penalizes jumps in the solution across interelement boundaries, and another that also penalizes jumps in the diffusive flux across such boundaries. For the first penalty method, we demonstrate convergence of order k in the L^∞(L²) norm when polynomials of minimal degree k are used, and for the second penalty method, we demonstrate convergence of order k+1/2. Through a parabolic lift argument, we show improved convergence of order k+1/2 (k+1) in the L²(L²) norm for the first penalty method with a penalty parameter of order one (h^?1). © 2001 John Wiley & Sons, Inc. Numer Methods Partial Differential Eq 17: 545–564, 2001     

Convergence of the point vortex method for the 3-D euler equations

We prove consistency, stability, and convergence of a point vortex approximation to the 3-D incompressible Euler equations with smooth solutions. The 3-D algorithm we consider here is similar to the corresponding 3-D vortex blob algorithm introduced by Beale and Majda; see [3]. We first show that the discretization error is second-order accurate. Then we show that the method is stable in l^p norm for the particle trajectories and in w^?1.p norm for discrete vorticity. Consequently, the method converges up to any time for which the Euler equations have a smooth solution. One immediate application of our convergence result is that the vortex filament method without smoothing also converges.     

A note on preconditioned GMRES for solving singular linear systems

For solving a singular linear system Ax=b by GMRES, it is shown in the literature that if A is range-symmetric, then GMRES converges safely to a solution. In this paper we consider preconditioned GMRES for solving a singular linear system, we construct preconditioners by so-called proper splittings, which can ensure that the coefficient matrix of the preconditioned system is range-symmetric.     

Preconditioned Krylov subspace method for the solution of least-squares problems

We consider preconditioned Krylov subspace iteration methods, e.g., CG, LSQR and GMRES, for the solution of large sparse least-squares problems min ∥Ax – b ∥₂, with A ∈ R ^m×n, based on the Krylov subspaces K_k (BA, Br) and K_k (AB, r), respectively, where B ∈ R ^n×m is the preconditioning matrix. More concretely, we propose and implement a class of incomplete QR factorization preconditioners based on the Givens rotations and analyze in detail the efficiency and robustness of the correspondingly preconditioned Krylov subspace iteration methods. A number of numerical experiments are used to further examine their numerical behaviour. It is shown that for both overdetermined and underdetermined least-squares problems, the preconditioned GMRES methods are the best for large, sparse and ill-conditioned matrices in terms of both CPU time and iteration step. Also, comparisons with the diagonal scaling and the RIF preconditioners are given to show the superiority of the newly-proposed GMRES-type methods. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Convergence analysis and computational testing of the finite element discretization of the Navier–Stokes alpha model

This report performs a complete analysis of convergence and rates of convergence of finite element approximations of the Navier–Stokes‐α (NS‐α) regularization of the NSE, under a zero‐divergence constraint on the velocity, to the true solution of the NSE. Convergence of the discrete NS‐α approximate velocity to the true Navier–Stokes velocity is proved and rates of convergence derived, under no‐slip boundary conditions. Generalization of the results herein to periodic boundary conditions is evident. Two‐dimensional experiments are performed, verifying convergence and predicted rates of convergence. It is shown that the NS‐α‐FE solutions converge at the theoretical limit of O(h²) when choosing α = h, in the H¹ norm. Furthermore, in the case of flow over a step the NS‐α model is shown to resolve vortex separation in the recirculation zone. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2010     

Fully discrete interior penalty discontinuous Galerkin methods for nonlinear parabolic equations

In this article, we investigate interior penalty discontinuous Galerkin (IPDG) methods for solving a class of two‐dimensional nonlinear parabolic equations. For semi‐discrete IPDG schemes on a quasi‐uniform family of meshes, we obtain a priori bounds on solutions measured in the L² norm and in the broken Sobolev norm. The fully discrete IPDG schemes considered are based on the approximation by forward Euler difference in time and broken Sobolev space. Under a restriction related to the mesh size and time step, an hp ‐version of an a priori l^∞(L²) and l²(H¹) error estimate is derived and numerical experiments are presented.© 2010 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 28: 288–311, 2012     

Compact difference schemes for heat equation with Neumann boundary conditions

In this article, two recent proposed compact schemes for the heat conduction problem with Neumann boundary conditions are analyzed. The first difference scheme was proposed by Zhao, Dai, and Niu (Numer Methods Partial Differential Eq 23, (2007), 949–959). The unconditional stability and convergence are proved by the energy methods. The convergence order is O(τ² + h^2.5) in a discrete maximum norm. Numerical examples demonstrate that the convergence order of the scheme can not exceeds O(τ² + h³). An improved compact scheme is presented, by which the approximate values at the boundary points can be obtained directly. The second scheme was given by Liao, Zhu, and Khaliq (Methods Partial Differential Eq 22, (2006), 600–616). The unconditional stability and convergence are also shown. By the way, it is reported how to avoid computing the values at the fictitious points. Some numerical examples are presented to show the theoretical results. © 2009 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2009     

Algebraic analysis of multigrid algorithms

We study the convergence rate of multilevel algorithms from an algebraic point of view. This requires a detailed analysis of the constant in the strengthened Cauchy–Schwarz inequality between the coarse‐grid space and a so‐called complementary space. This complementary space may be spanned by standard hierarchical basis functions, prewavelets or generalized prewavelets. Using generalized prewavelets, we are able to derive a constant in the strengthened Cauchy–Schwarz inequality which is less than 0.31 for the L² and H¹ bilinear form. This implies a convergence rate less than 0.15. So, we are able to prove fast multilevel convergence. Furthermore, we obtain robust estimations of the convergence rate for a large class of anisotropic ellipic equations, even for some that are not H¹‐elliptic. Copyright © 1999 John Wiley & Sons, Ltd.     

Maximum error estimates for a compact difference scheme of the coupled nonlinear Schrödinger–Boussinesq equations

The coupled nonlinear Schrödinger–Boussinesq (SBq) equations describe the nonlinear development of modulational instabilities associated with Langmuir field amplitude coupled to intense electromagnetic wave in dispersive media such as plasmas. In this paper, we present a conservative compact difference scheme for the coupled SBq equations and analyze the conservative property and the existence of the scheme. Then we prove that the scheme is convergent with convergence order O(τ² + h⁴) in L_∞‐norm and is stable in L_∞‐norm. Numerical results verify the theoretical analysis.     

Convergence analysis of the rectangular Morley element scheme for second order problem in arbitrary dimensions

We present the convergence analysis of the rectangular Morley element scheme utilised on the second order problem in arbitrary dimensions. Specifically, we prove that the convergence of the scheme is of O(h) order in energy norm and of O(h²) order in L² norm on general d-rectangular triangulations. Moreover, when the triangulation is uniform, the convergence rate can be of O(h²) order in energy norm, and the convergence rate in L² norm is still of O(h²) order, which cannot be improved. Numerical examples are presented to demonstrate our theoretical results.     

An additive Schwarz preconditioner for the FETI method

Summary.  A new additive Schwarz preconditioner for the Finite Element Tearing and Interconnecting (FETI) method is analyzed in this paper. This preconditioner has the unique feature that the coefficient matrix of its ``coarse grid' problem is mesh independent. For a model second order heterogeneous elliptic boundary value problem in two dimensions, the condition number of the preconditioned system is shown to be bounded by C[1+ln(H/h)]², where h is the mesh size, H is the typical diameter of the subdomains, and the constant C is independent of h, H, the number of subdomains and the coefficients of the boundary value problem. Received May 8, 2000 / Revised version received January 2, 2002 / Published online July 18, 2002 Mathematics Subject Classification (1991): 65N55, 65N30     

A two-grid finite element method for the Allen-Cahn equation with the logarithmic potential

In this paper, we present a two-grid finite element method for the Allen-Cahn equation with the logarithmic potential. This method consists of two steps. In the first step, based on a fully implicit finite element method, the Allen-Cahn equation is solved on a coarse grid with mesh size H. In the second step, a linearized system whose nonlinear term is replaced by the value of the first step is solved on a fine grid with mesh size h. We give the energy stabilities of the traditional finite element method and the two-grid finite element method. The optimal convergence order of the two-grid finite element method in H¹ norm is achieved when the mesh sizes satisfy h = O(H²). Numerical examples are given to demonstrate the validity of the proposed scheme. The results show that the two-grid method can save the CPU time while keeping the same convergence rate.     

A conservative compact difference scheme for the coupled Klein–Gordon–Schrödinger equation

In this article, a conservative compact difference scheme is presented for the periodic initial‐value problem of Klein–Gordon–Schrödinger equation. On the basis of some inequalities about norms and the priori estimates, convergence of the difference solution is proved with order O(h⁴ +τ ²) in maximum norm. Numerical experiments demonstrate the accuracy and efficiency of the compact scheme. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013