On HSS and AHSS iteration methods for nonsymmetric positive definite Toeplitz systems

Two iteration methods are proposed to solve real nonsymmetric positive definite Toeplitz systems of linear equations. These methods are based on Hermitian and skew-Hermitian splitting (HSS) and accelerated Hermitian and skew-Hermitian splitting (AHSS). By constructing an orthogonal matrix and using a similarity transformation, the real Toeplitz linear system is transformed into a generalized saddle point problem. Then the structured HSS and the structured AHSS iteration methods are established by applying the HSS and the AHSS iteration methods to the generalized saddle point problem. We discuss efficient implementations and demonstrate that the structured HSS and the structured AHSS iteration methods have better behavior than the HSS iteration method in terms of both computational complexity and convergence speed. Moreover, the structured AHSS iteration method outperforms the HSS and the structured HSS iteration methods. The structured AHSS iteration method also converges unconditionally to the unique solution of the Toeplitz linear system. In addition, an upper bound for the contraction factor of the structured AHSS iteration method is derived. Numerical experiments are used to illustrate the effectiveness of the structured AHSS iteration method.     

A choice of forcing terms in inexact Newton method

Inexact Newton method is one of the effective tools for solving systems of nonlinear equations. In each iteration step of the method, a forcing term, which is used to control the accuracy when solving the Newton equations, is required. The choice of the forcing terms is of great importance due to their strong influence on the behavior of the inexact Newton method, including its convergence, efficiency, and even robustness. To improve the efficiency and robustness of the inexact Newton method, a new strategy to determine the forcing terms is given in this paper. With the new forcing terms, the inexact Newton method is locally Q-superlinearly convergent. Numerical results are presented to support the effectiveness of the new forcing terms.     

A fast algorithm for solving diagonally dominant symmetric pentadiagonal Toeplitz systems

Banded Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Recently, significant advancement has been made in algorithm development of fast parallel scalable methods to solve tridiagonal Toeplitz problems. In this paper we will derive a new algorithm for solving symmetric pentadiagonal Toeplitz systems of linear equations based upon a technique used in [J.M. McNally, L.E. Garey, R.E. Shaw, A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Int. J. Comput. Math. 75 (2000) 303-313] for tridiagonal Toeplitz systems. A common example which arises in natural quintic spline problems will be used to demonstrate the algorithm’s effectiveness. Finally computational results and comparisons will be presented.     

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14], it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper is to give a complete convergence proof of the method in [10,14] for this class of generating functions. Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001     

A modified SSOR iterative method for augmented systems

Golub, Wu and Yuan [G.H. Golub, X. Wu, J.Y. Yuan, SOR-like methods for augmented systems, BIT 41 (2001) 71–85] have presented the SOR-like algorithm to solve augmented systems. In this paper, we present the modified symmetric successive overrelaxation (MSSOR) method for solving augmented systems, which is based on Darvishi and Hessari’s work above. We derive its convergence under suitable restrictions on the iteration parameter, determine its optimal iteration parameter and the corresponding optimal convergence factor under certain conditions. Finally, we apply the MSSOR method to solve augmented systems.     

Convergence analysis of two-grid methods for elliptic Toeplitz and PDEs Matrix-sequences

Summary. The solution of large Toeplitz systems with nonnegative generating functions by multigrid methods was proposed in previous papers [13,14,22]. The technique was modified in [6,36] and a rigorous proof of convergence of the TGM (two-grid method) was given in the special case where the generating function has only a zero at of order at most two. Here, by extending the latter approach, we perform a complete analysis of convergence of the TGM under the sole assumption that f is nonnegative and with a zero at of finite order. An extension of the same analysis in the multilevel case and in the case of finite difference matrix sequences discretizing elliptic PDEs with nonconstant coefficients and of any order is then discussed. Received May 28, 1999 / Revised version received January 26, 2001 / Published online November 15, 2001     

The rate of convergence of GMRES on a tridiagonal toeplitz linear system. II

This paper continues the recent work of the authors’ [R.-C. Li, W. Zhang, The rate of convergence of GMRES on a tridiagonal Toeplitz linear system, Numer. Math. 112 (2009) 267-293 (electronically published on 19 December 2008)] on the rate of convergence of GMRES for a tridiagonal Toeplitz linear system Ax=b. Much simpler formulas than the earlier ones for GMRES residuals when b is the first or the last column of the identity matrix are established, and these formulas allow us to confirm the rate of convergence that was conjectured but only partially proven earlier. Simpler and sharper bounds than earlier ones when all b’s entries, except its first and last ones, are zeros are also obtained.     

On deflation and singular symmetric positive semi-definite matrices

For various applications, it is well-known that the deflated ICCG is an efficient method for solving linear systems with invertible coefficient matrix. We propose two equivalent variants of this deflated ICCG which can also solve linear systems with singular coefficient matrix, arising from discretization of the discontinuous Poisson equation with Neumann boundary conditions. It is demonstrated both theoretically and numerically that the resulting methods accelerate the convergence of the iterative process.     

Generalized Newton’s method based on graphical derivatives

This paper concerns developing a numerical method of the Newton type to solve systems of nonlinear equations described by nonsmooth continuous functions. We propose and justify a new generalized Newton algorithm based on graphical derivatives, which have never been used to derive a Newton-type method for solving nonsmooth equations. Based on advanced techniques of variational analysis and generalized differentiation, we establish the well-posedness of the algorithm, its local superlinear convergence, and its global convergence of the Kantorovich type. Our convergence results hold with no semismoothness and Lipschitzian assumptions, which is illustrated by examples. The algorithm and main results obtained in the paper are compared with well-recognized semismooth and B-differentiable versions of Newton’s method for nonsmooth Lipschitzian equations.     

On the Newton method for set-valued maps

The Newton method is one of the most powerful tools used to solve systems of nonlinear equations. Its set-valued generalization, considered in this work, allows one to solve also nonlinear equations with geometric constraints and systems of inequalities in a unified manner. The emphasis is given to systems of linear inequalities. The study of the well-posedness of the algorithm and of its convergence is fulfilled in the framework of modern variational analysis.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.     

Circulant and skew-circulant preconditioners for skew-hermitian type Toeplitz systems

We study the solutions of Toeplitz systemsA _n x=b by the preconditioned conjugate gradient method. Then ×n matrixA _n is of the forma ₀ I+H _n wherea ₀ is a real number,I is the identity matrix andH _n is a skew-Hermitian Toeplitz matrix. Such matrices often appear in solving discretized hyperbolic differential equations. The preconditioners we considered here are the circulant matrixC _n and the skew-circulant matrixS _n whereA _n =1/2(C _n +S _n ). The convergence rate of the iterative method depends on the distribution of the singular values of the matricesC ^–1 _n A_n andS ^–1 _n A _n . For Toeplitz matricesA _n with entries which are Fourier coefficients of functions in the Wiener class, we show the invertibility ofC _n andS _n and prove that the singular values ofC ^–1 _n A _n andS ^–1 _n A _n are clustered around 1 for largen. Hence, if the conjugate gradient method is applied to solve the preconditioned systems, we expect fast convergence.     

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.     

On generalized successive overrelaxation methods for augmented linear systems

For the augmented system of linear equations, Golub, Wu and Yuan recently studied an SOR-like method (BIT 41(2001)71–85). By further accelerating it with another parameter, in this paper we present a generalized SOR (GSOR) method for the augmented linear system. We prove its convergence under suitable restrictions on the iteration parameters, and determine its optimal iteration parameters and the corresponding optimal convergence factor. Theoretical analyses show that the GSOR method has faster asymptotic convergence rate than the SOR-like method. Also numerical results show that the GSOR method is more effective than the SOR-like method when they are applied to solve the augmented linear system. This GSOR method is further generalized to obtain a framework of the relaxed splitting iterative methods for solving both symmetric and nonsymmetric augmented linear systems by using the techniques of vector extrapolation, matrix relaxation and inexact iteration. Besides, we also demonstrate a complete version about the convergence theory of the SOR-like method. Subsidized by The Special Funds For Major State Basic Research Projects (No. G1999032803) and The National Natural Science Foundation (No. 10471146), P.R. China     

Convergence of a generalized MSSOR method for augmented systems

Recently, Wu et al. [S.-L. Wu, T.-Z. Huang, X.-L. Zhao, A modified SSOR iterative method for augmented systems, J. Comput. Appl. Math. 228 (1) (2009) 424-433] introduced a modified SSOR (MSSOR) method for augmented systems. In this paper, we establish a generalized MSSOR (GMSSOR) method for solving the large sparse augmented systems of linear equations, which is the extension of the MSSOR method. Furthermore, the convergence of the GMSSOR method for augmented systems is analyzed and numerical experiments are carried out, which show that the GMSSOR method with appropriate parameters has a faster convergence rate than the MSSOR method with optimal parameters.     

A <Emphasis Type="Italic">V</Emphasis>-cycle Multigrid for multilevel matrix algebras: proof of optimality

We analyze the convergence rate of a multigrid method for multilevel linear systems whose coefficient matrices are generated by a real and nonnegative multivariate polynomial f and belong to multilevel matrix algebras like circulant, tau, Hartley, or are of Toeplitz type. In the case of matrix algebra linear systems, we prove that the convergence rate is independent of the system dimension even in presence of asymptotical ill-conditioning (this happens iff f takes the zero value). More precisely, if the d-level coefficient matrix has partial dimension n _r at level r, with , then the size of the system is , , and O(N(n)) operations are required by the considered V-cycle Multigrid in order to compute the solution within a fixed accuracy. Since the total arithmetic cost is asymptotically equivalent to the one of a matrix-vector product, the proposed method is optimal. Some numerical experiments concerning linear systems arising in 2D and 3D applications are considered and discussed.     

Semismooth Newton and Newton iterative methods for HJB equation

In this paper, some semismooth methods are considered to solve a nonsmooth equation which can arise from a discrete version of the well-known Hamilton-Jacobi-Bellman equation. By using the slant differentiability introduced by Chen, Nashed and Qi in 2000, a semismooth Newton method is proposed. The method is proved to have monotone convergence by suitably choosing the initial iterative point and local superlinear convergence rate. Moreover, an inexact version of the proposed method is introduced, which reduces the cost of computations and still preserves nice convergence properties. Some numerical results are also reported.     

An improved approximate Newton method for implicit Runge-Kutta formulas

Implicit Runge-Kutta (IRK) methods (such as the s-stage Radau IIA method with s=3,5, or 7) for solving stiff ordinary differential equation systems have excellent stability properties and high solution accuracy orders, but their high computing costs in solving their nonlinear stage equations have seriously limited their applications to large scale problems. To reduce such a cost, several approximate Newton algorithms were developed, including a commonly used one called the simplified Newton method. In this paper, a new approximate Jacobian matrix and two new test rules for controlling the updating of approximate Jacobian matrices are proposed, yielding an improved approximate Newton method. Theoretical and numerical analysis show that the improved approximate Newton method can significantly improve the convergence and performance of the simplified Newton method.     

A class of Uzawa-SOR methods for saddle point problems

In this paper, we consider a class of Uzawa-SOR methods for saddle point problems, and prove the convergence of the proposed methods. We solve a lower triangular system per iteration in the proposed methods, instead of solving a linear equation Az=b. Actually, the new methods can be considered as an inexact iteration method with the Uzawa as the outer iteration and the SOR as the inner iteration. Although the proposed methods cannot achieve the same convergence rate as the GSOR methods proposed by Bai et al. [Z.-Z. Bai, B.N. Parlett, Z.-Q. Wang, On generalized successive overrelaxation methods for augmented linear systems, Numer. Math. 102 (2005) 1-38], but our proposed methods have less workloads per iteration step. Experimental results show that our proposed methods are feasible and effective.     

A direct method to solve block banded block Toeplitz systems with non-banded Toeplitz blocks

A fast solution algorithm is proposed for solving block banded block Toeplitz systems with non-banded Toeplitz blocks. The algorithm constructs the circulant transformation of a given Toeplitz system and then by means of the Sherman-Morrison-Woodbury formula transforms its inverse to an inverse of the original matrix. The block circulant matrix with Toeplitz blocks is converted to a block diagonal matrix with Toeplitz blocks, and the resulting Toeplitz systems are solved by means of a fast Toeplitz solver.The computational complexity in the case one uses fast Toeplitz solvers is equal to ξ(m,n,k)=O(mn³)+O(k³n³) flops, there are m block rows and m block columns in the matrix, n is the order of blocks, 2k+1 is the bandwidth. The validity of the approach is illustrated by numerical experiments.