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.     

Practical Band Toeplitz Preconditioning and Boundary Layer Effects

In the last decade many efficient iterative solvers for n×n Hermitian positive definite Toeplitz systems have been devised. Many of them are based on band Toeplitz preconditioners: they are optimal but require the knowledge of the zeros of the underlying generating function. In some cases this information is available and in some cases is not. In [27] an economic numerical procedure for finding these zeros within a given precision has been devised. Here we provide conditions on the approximation error of these zeros in order to maintain the optimality that is a convergence rate independent of the dimension n of the considered linear systems.     

On the convergence of the minimum residual HSS iteration method

Recently, by applying the minimum residual technique to the Hermitian and skew-Hermitian splitting (HSS) iteration scheme, a minimum residual HSS (MRHSS) iteration method was proposed for solving non-Hermitian positive definite linear systems. Although the MRHSS iteration method is very efficient, it is conditionally convergent. In this work, we further study the convergence of the MRHSS iteration method, and show that it can unconditionally convergent if its parameters are determined by minimizing a new norm of the residual. Numerical results verify that the MRHSS method discussed in this work is also very efficient.     

On the positive definite solutions of nonlinear matrix equation X + A⋆ X−δA = Q

In this paper we consider the positive definite solutions of nonlinear matrix equation X + A^⋆X^−δA = Q, where δ ∈ (0, 1], which appears for the first time in [S.M. El-Sayed, A.C.M. Ran, On an iteration methods for solving a class of nonlinear matrix equations, SIAM J. Matrix Anal. Appl. 23 (2001) 632–645]. The necessary and sufficient conditions for the existence of a solution are derived. An iterative algorithm for obtaining the positive definite solutions of the equation is discussed. The error estimations are found.     

On the Hermitian positive definite solutions of nonlinear matrix equation X + A∗XA = Q

Nonlinear matrix equation X^s + A∗X^−tA = Q, where A, Q are n × n complex matrices with Q Hermitian positive definite, has widely applied background. In this paper, we consider the Hermitian positive definite solutions of this matrix equation with two cases: s ? 1, 0 < t ? 1 and 0 < s ? 1, t ? 1. We derive necessary conditions and sufficient conditions for the existence of Hermitian positive definite solutions for the matrix equation and obtain some properties of the solutions. We also propose iterative methods for obtaining the extremal Hermitian positive definite solution of the matrix equation. Finally, we give some numerical examples to show the efficiency of the proposed iterative methods.     

Optimal Parameters for 2-cyclic AOR

Assume A∈C^n×n is a 2-cyclic consistently ordered matrix and J is denoted as its associated block Jacobi iteration matrix. We consider the 2-cyclic AOR method for solving the consistent linear systems Ax=b. In the case that σ(J²) is either nonnegative or nonpositive, we give detailed discussion and derive definite expressions on optimal parameters and spectral radius by efficient method. Moreover, we give some numerical examples.     

Inverse generating function approach for the preconditioning of Toeplitz‐block systems

As proposed by R. H. Chan and M. K. Ng (1993), linear systems of the form T [ f ] x = b , where T [ f ] denotes the n×n Toeplitz matrix generated by the function f, can be solved using iterative solvers with as a preconditioner. This article aims at generalizing this approach to the case of Toeplitz‐block matrices and matrix‐valued generating functions F . We prove that if F is Hermitian positive definite, most eigenvalues of the preconditioned matrix T [ F ⁻¹]T[ F ] are clustered around one. Numerical experiments demonstrate the performance of this preconditioner.     

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.     

Inverses of tridiagonal Toeplitz and periodic matrices with applications to mechanics

The linear algebraic equation Ax = b with tridiagonal coefficient matrix of A is solved by the analytical matrix inversion. An explicit formula is known if A is a Toeplitz matrix. New formulas are presented for the following cases: (1) A is of Toeplitz type except that A(1, 1) and A(n, n) are different from the remaining diagonal elements. (2) A is p-periodic (p > 1), by which is meant that in each of the three bands of A a group of p elements is periodically repeated. (3) The tridiagonal matrix A is composed of periodic submatrices of different periods. In cases (2) and(3) the problem of matrix inversion is reduced to a second-order difference equation with periodic coefficients. The solution is based on Floquet's theorem. It is shown that for p = 1 the formulae found for periodic matrices reduce to special forms valid for Toeplitz matrices. The results are applied to problems of elastostatics and of vibration theory.     

关于广义鞍点问题的HSS迭代方法的收缩因子(英文)

白中治等提出了解非埃尔米特正定线性方程组的埃尔米特和反埃尔米特分裂(HSS)迭代方法(Bai Z Z,Golub G H,Ng M K.Hermitian and skew-Hermitian splitting methodsfor non-Hermitian positive definite linear systems.SIAM J.Matrix Anal.Appl.,2003,24:603-626).本文精确地估计了用HSS迭代方法求解广义鞍点问题时在加权2-范数和2-范数下的收缩因子.在实际的计算中,正是这些收缩因子而不是迭代矩阵的谱半径,本质上控制着HSS迭代方法的实际收敛速度.根据文中的分析,求解广义鞍点问题的HSS迭代方法的收缩因子在加权2-范数下等于1,在2-范数下它会大于等于1,而在某种适当选取的范数之下,它则会小于1.最后,用数值算例说明了理论结果的正确性.     

Positive definite solutions of the nonlinear matrix equation X + AXA = Q (q > 0)

In this paper, the nonlinear matrix equation X + A^∗X^qA = Q (q > 0) is investigated. Some necessary and sufficient conditions for existence of Hermitian positive definite solutions of the nonlinear matrix equations are derived. An effective iterative method to obtain the positive definite solution is presented. Some numerical results are given to illustrate the effectiveness of the iterative methods.     

Preconditioning strategies for asymptotically ill-conditioned block Toeplitz systems

A particular class of preconditioners for the conjugate gradient method and other iterative methods is proposed for the solution of linear systemsA _n,mx=b, whereA _n,m is ann×n positive definite block Toeplitz matrix withm×m Toeplitz blocks. In particular we propose a sparse preconditionerP _n,m such that the condition number of the preconditioned matrix turns out to be less than a suitable constant independent of bothn andm, even if the condition number ofA _n,m tends to . This leads to iterative methods which require a number of steps independent ofm andn in order to reduce the error by a given factor.     

Preconditioners Based on Fit Techniques for the Iterative Regularization in the Image Deconvolution Problem

For large-scale image deconvolution problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n²) operations per iteration, where n² is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n² log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of O(n²) operations per iteration. A numerical experimentation shows that the fit preconditioners are competitive with the regularizing Chan preconditioner, both in the regularizing efficiency and the computational cost. AMS subject classification (2000) 65F10, 65F22.Received October 2003. Accepted December 2004. Communicated by Lars Eldén.     

Matrices, moments and quadrature II; How to compute the norm of the error in iterative methods

In this paper, we study the numerical computation of the errors in linear systems when using iterative methods. This is done by using methods to obtain bounds or approximations of quadratic formsu ^T A ⁻¹ u whereA is a symmetric positive definite matrix andu is a given vector. Numerical examples are given for the Gauss-Seidel algorithm. Moreover, we show that using a formula for theA-norm of the error from Dahlquist, Golub and Nash [1978] very good bounds of the error can be computed almost for free during the iterations of the conjugate gradient method leading to a reliable stopping criterion. The work of the first author was partially supported by NSF Grant CCR-950539.     

Preconditioners for Ill-Conditioned Toeplitz Matrices

This paper is concerned with the solution of systems of linear equations A _N x = b, where denotes a sequence of positive definite Hermitian ill-conditioned Toeplitz matrices arising from a (real-valued) nonnegative generating function f C ₂ with zeros. We construct positive definite Hermitian preconditioners M _N such that the eigenvalues of M _N ^–1 A _N are clustered at 1 and the corresponding PCG-method requires only O(N log N) arithmetical operations to achieve a prescribed precision. We sketch how our preconditioning technique can be extended to symmetric Toeplitz systems, doubly symmetric block Toeplitz systems with Toeplitz blocks and non-Hermitian Toeplitz systems. Numerical tests confirm the theoretical expectations.     

Preconditioned HSS method for large multilevel block Toeplitz linear systems via the notion of matrix‐valued symbol

We perform a spectral analysis of the preconditioned Hermitian/skew‐Hermitian splitting (PHSS) method applied to multilevel block Toeplitz linear systems in which the coefficient matrix T_n(f) is associated with a Lebesgue integrable matrix‐valued function f. When the preconditioner is chosen as a Hermitian positive definite multilevel block Toeplitz matrix T_n(g), the resulting sequence of PHSS iteration matrices M_n belongs to the generalized locally Toeplitz class. In this case, we are able to compute the symbol ?(f,g) describing the asymptotic eigenvalue distribution of M_nwhen n→∞ and the matrix size diverges. By minimizing the infinity norm of the spectral radius of the symbol ?(f,g), we are also able to identify effective PHSS preconditioners T_n(g) for the matrix T_n(f). A number of numerical experiments are presented and commented, showing that the theoretical results are confirmed and that the spectral analysis leads to efficient PHSS methods. Copyright © 2015 John Wiley & Sons, Ltd.     

Solving Toeplitz Least Squares Problems by Means of Newton's Iteration

We extend the algorithm of [4], based on Newton's iteration and on the concept of -displacement rank, to the computation of the generalized inverse A ⁺ of an m×n Toeplitz matrix A. We introduce new strategies for the dynamical control of the truncation level at each step of the iteration. Numerical experiments and an application to a problem of image restoration are shown. An object-oriented implementation in C++ is described.     

Contractive maps on normed linear spaces and their applications to nonlinear matrix equations

In this paper we will give necessary and sufficient conditions under which a map is a contraction on a certain subset of a normed linear space. These conditions are already well known for maps on intervals in R. Using the conditions and Banach’s fixed point theorem we can prove a fixed point theorem for operators on a normed linear space. The fixed point theorem will be applied to the matrix equation X = I_n + A^∗f(X)A, where f is a map on the set of positive definite matrices induced by a real valued map on (0, ∞). This will give conditions on A and f under which the equation has a unique solution in a certain set. We will consider two examples of f in detail. In one example the application of the fixed point theorem is the first step in proving that the equation has a unique positive definite solution under the conditions on A.     

A note on Stewart's theorem for definite matrix pairs

Let A and B be n×n Hermitian matrices. The matrix pair (A, B) is called definite pair and the corresponding eigenvalue problem βAx = αBx is definite if c(A, B) ≡ inf_{6x6= 1}{|^H(A+iB)x|} > 0. In this note we develop a uniform upper bound for differences of corresponding eigenvalues of two definite pairs and so improve a result which is obtained by G.W. Stewart [2]. Moreover, we prove that this upper bound is a projective metric in the set of n × n definite pairs.