Respectively scaled HSS iteration methods for solving discretized spatial fractional diffusion equations

For the discrete linear systems resulted from the discretization of the one‐dimensional anisotropic spatial fractional diffusion equations of variable coefficients with the shifted finite‐difference formulas of the Grünwald–Letnikov type, we propose a class of respectively scaled Hermitian and skew‐Hermitian splitting iteration method and establish its asymptotic convergence theory. The corresponding induced matrix splitting preconditioner, through further replacements of the involved Toeplitz matrices with certain circulant matrices, leads to an economic variant that can be executed by fast Fourier transforms. Both theoretical analysis and numerical implementations show that this fast respectively scaled Hermitian and skew‐Hermitian splitting preconditioner can significantly improve the computational efficiency of the Krylov subspace iteration methods employed as effective linear solvers for the target discrete linear systems.     

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.     

Extreme eigenvalues of real symmetric Toeplitz matrices

We exploit the even and odd spectrum of real symmetric Toeplitz matrices for the computation of their extreme eigenvalues, which are obtained as the solutions of spectral, or secular, equations. We also present a concise convergence analysis for a method to solve these spectral equations, along with an efficient stopping rule, an error analysis, and extensive numerical results.

     

Some extensions of the improved modified Gauss–Seidel iterative method for H‐matrices

In this paper, first we present a convergence theorem of the improved modified Gauss–Seidel iterative method, referred to as the IMGS method, for H‐matrices and compare the range of parameters α_i with that of the parameter ω of the SOR iterative method. Then with a more general splitting, the convergence analysis of this method for an H‐matrix and its comparison matrix is given. The spectral radii of them are also compared. Copyright © 2006 John Wiley & Sons, Ltd.     

Preconditioners for ill‐posed Toeplitz matrices with differentiable generating functions

Both theoretical analysis and numerical experiments in the literature have shown that the Tyrtyshnikov circulant superoptimal preconditioner for Toeplitz systems can speed up the convergence of iterative methods without amplifying the noise of the data. Here we study a family of Tyrtyshnikov‐based preconditioners for discrete ill‐posed Toeplitz systems with differentiable generating functions. In particular, we show that the distribution of the eigenvalues of these preconditioners has good regularization features, since the smallest eigenvalues stay well separated from zero. Some numerical results confirm the regularization effectiveness of this family of preconditioners. Copyright © 2009 John Wiley & Sons, Ltd.     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

On the convergence of basic iterative methods for convection–diffusion equations

In this paper we analyze convergence of basic iterative Jacobi and Gauss–Seidel type methods for solving linear systems which result from finite element or finite volume discretization of convection–diffusion equations on unstructured meshes. In general the resulting stiffness matrices are neither M‐matrices nor satisfy a diagonal dominance criterion. We introduce two newmatrix classes and analyse the convergence of the Jacobi and Gauss–Seidel methods for matrices from these classes. A new convergence result for the Jacobi method is proved and negative results for the Gauss–Seidel method are obtained. For a few well‐known discretization methods it is shown that the resulting stiffness matrices fall into the new matrix classes. Copyright © 1999 John Wiley & Sons, Ltd.     

A comparative study of efficient iterative solvers for generalized Stokes equations

We consider a generalized Stokes equation with problem parameters ξ?0 (size of the reaction term) and ν>0 (size of the diffusion term). We apply a standard finite element method for discretization. The main topic of the paper is a study of efficient iterative solvers for the resulting discrete saddle point problem. We investigate a coupled multigrid method with Braess–Sarazin and Vanka‐type smoothers, a preconditioned MINRES method and an inexact Uzawa method. We present a comparative study of these methods. An important issue is the dependence of the rate of convergence of these methods on the mesh size parameter and on the problem parameters ξ and ν. We give an overview of the main theoretical convergence results known for these methods. For a three‐dimensional problem, discretized by the Hood–Taylor ??₂–??₁ pair, we give results of numerical experiments. Copyright © 2007 John Wiley & Sons, Ltd.     

Convergence analysis of Anderson‐type acceleration of Richardson's iteration

We consider Anderson extrapolation to accelerate the (stationary) Richardson iterative method for sparse linear systems. Using an Anderson mixing at periodic intervals, we assess how this benefits convergence to a prescribed accuracy. The method, named alternating Anderson–Richardson, has appealing properties for high‐performance computing, such as the potential to reduce communication and storage in comparison to more conventional linear solvers. We establish sufficient conditions for convergence, and we evaluate the performance of this technique in combination with various preconditioners through numerical examples. Furthermore, we propose an augmented version of this technique.     

对称正定Toeplitz方程组的多级迭代求解

二级迭代法亦称内外迭代法. 多级迭代法由多个二级迭代嵌套而成.这些方法特别适合于并行计算,同时可以理解为古典迭代法的延伸或共轭梯度法的预处理子.本文讨论了对称正定Toeplitz线性方程组多级迭代法. 首先,基于Toeplitz矩阵的结构, 我们给出了多级块Jacobi分裂,然后证明了每一级分裂均为P-正则分裂, 并证明了当每一级内迭代次数均为偶数时,迭代法的收敛性. 最后通过数值实例验证了此方法的有效性.     

Spectral analysis of Pk Finite Element matrices in the case of Friedrichs–Keller triangulations via Generalized Locally Toeplitz technology

In the present article, we consider a class of elliptic partial differential equations with Dirichlet boundary conditions and where the operator is div(?a( x )?·), with a continuous and positive over $\stackrel{￣}{\mathrm{\Omega }}$, Ω being an open and bounded subset of ${\mathbb{R}}^d$, d≥1. For the numerical approximation, we consider the classical ${\mathbb{P}}_k$ Finite Elements, in the case of Friedrichs–Keller triangulations, leading, as usual, to sequences of matrices of increasing size. The new results concern the spectral analysis of the resulting matrix‐sequences in the direction of the global distribution in the Weyl sense, with a concise overview on localization, clustering, extremal eigenvalues, and asymptotic conditioning. We study in detail the case of constant coefficients on Ω=(0,1)² and we give a brief account in the more involved case of variable coefficients and more general domains. Tools are drawn from the Toeplitz technology and from the rather new theory of Generalized Locally Toeplitz sequences. Numerical results are shown for a practical evidence of the theoretical findings.     

An efficient algebraic multigrid method for quadratic discretizations of linear elasticity problems on some typical anisotropic meshes in three dimensions

The quality of the mesh used in the finite element discretizations will affect the efficiency of solving the discreted linear systems. The usual algebraic solvers except multigrid method do not consider the effect of the grid geometry and the mesh quality on their convergence rates. In this paper, we consider the hierarchical quadratic discretizations of three‐dimensional linear elasticity problems on some anisotropic hexahedral meshes and present a new two‐level method, which is weakly independent of the size of the resulting problems by using a special local block Gauss–Seidel smoother, that is LBGS_v iteration when used for vertex nodes or LBGS_m iteration for midside nodes. Moreover, we obtain the efficient algebraic multigrid (AMG) methods by applying DAMG (AMG based on distance matrix) or DAMG‐PCG (PCG with DAMG as a preconditioner) to the solution of the coarse level equation. The resulting AMG methods are then applied to a practical example as a long beam. The numerical results verify the efficiency and robustness of the proposed AMG algorithms. Copyright © 2015 John Wiley & Sons, Ltd.     

First Order LSFEM for Fluid‐Structure Problems

The Least‐Squares Finite Element Method (LSFEM) is an interesting alternative to the standard variational principles, which are used to solve partial differential equations. Advantages of the LSFEM are its robustness and the resulting symmetric positive definite matrices, which allow the use of robust iterative solvers like the CG method. In this paper we consider the application of the LSFEM for Fluid‐Structure Interaction (FSI) problems. Our model uses the LSFEM for the discretisation of the instationary incompressible Navier‐Stokes equations, which is coupled with a standard Galerkin FEM model for a linear elastic structure. The results for a simple model problem agree well with results obtained by other authors with different numerical schemes. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Inexact Methods: Forcing Terms and Conditioning

In this paper, we consider inexact Newton and Newton-like methods andprovide new convergence conditions relating the forcing terms to theconditioning of the iteration matrices. These results can be exploited wheninexact methods with iterative linear solvers are used. In this framework,preconditioning techniques can be used to improve the performance ofiterative linear solvers and to avoid the need of excessively small forcingterms. Numerical experiments validating the theoretical results arediscussed.     

Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

Acoustic simulations with higher order finite and infinite elements

The efficiency of finite element based simulations of Helmholtz problems is primarily affected by two facts. First, the numerical solution suffers from the so-called pollution effect, which leads to very high element resolutions at higher frequencies. Furthermore, the spectral properties of the resulting system matrices, and hence the convergence of iterative solvers, deteriorate with increasing wave numbers. In this contribution the influence of different types of polynomial basis functions on the efficiency and stability of interior as well as exterior acoustic simulations is analyzed. The current investigations show that a proper choice for the polynomial shape approximation may significantly increase the performance of Krylov subspace methods. In particular, the efficiency of higher order finite and infinite elements based on Bernstein polynomial shape approximation and the corresponding iterative solution strategies is assessed for practically relevant numerical examples including the sound radiation from rolling vehicle tires. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Structured FISTA for image restoration

In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.     

Coupling finite difference methods and integral formulas for elliptic problems arising in fluid mechanics

This article is devoted to the numerical analysis of two classes of iterative methods that combine integral formulas with finite‐difference Poisson solvers for the solution of elliptic problems. The first method is in the spirit of the Schwarz domain decomposition method for exterior domains. The second one is motivated by potential calculations in free boundary problems and can be viewed as a numerical analytic continuation algorithm. Numerical tests are presented that confirm the convergence properties predicted by numerical analysis. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 199–229, 2004     

On the Convergence Theory of Preconditioned Subspace Iterations for Eigenvalue Problems

We consider preconditioned subspace iterations for the numerical solution of discretized elliptic eigenvalue problems. For these iterative solvers, the convergence theory is still an incomplete puzzle. We generalize some results from the classical convergence theory of inverse subspace iterations, as given by Parlett, and some recent results on the convergence of preconditioned vector iterations. To this end, we use a geometric cone representation and prove some new trigonometric inequalities for subspace angles and canonical angles. (© 2010 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On order‐reducible sinc discretizations and block‐diagonal preconditioning methods for linear third‐order ordinary differential equations

By introducing a variable substitution, we transform the two‐point boundary value problem of a third‐order ordinary differential equation into a system of two second‐order ordinary differential equations (ODEs). We discretize this order‐reduced system of ODEs by both sinc‐collocation and sinc‐Galerkin methods, and average these two discretized linear systems to obtain the target system of linear equations. We prove that the discrete solution resulting from the linear system converges exponentially to the true solution of the order‐reduced system of ODEs. The coefficient matrix of the linear system is of block two‐by‐two structure, and each of its blocks is a combination of Toeplitz and diagonal matrices. Because of its algebraic properties and matrix structures, the linear system can be effectively solved by Krylov subspace iteration methods such as GMRES preconditioned by block‐diagonal matrices. We demonstrate that the eigenvalues of certain approximation to the preconditioned matrix are uniformly bounded within a rectangle on the complex plane independent of the size of the discretized linear system, and we use numerical examples to illustrate the feasibility and effectiveness of this new approach. Copyright © 2013 John Wiley & Sons, Ltd.