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.     

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.     

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.     

Quasi‐Toeplitz splitting iteration methods for unsteady space‐fractional diffusion equations

We construct a class of quasi‐Toeplitz splitting iteration methods to solve the two‐sided unsteady space‐fractional diffusion equations with variable coefficients. By making full use of the structural characteristics of the coefficient matrix, the method only requires computational costs of O(n log n) with n denoting the number of degrees of freedom. We develop an appropriate circulant matrix to replace the Toeplitz matrix as a preconditioner. We discuss the spectral properties of the quasi‐circulant splitting preconditioned matrix. Numerical comparisons with existing approaches show that the present method is both effective and efficient when being used as matrix splitting preconditioners for Krylov subspace iteration methods.     

Block band Toeplitz preconditioners derived from generating function approximations: analysis and applications

We are concerned with the study and the design of optimal preconditioners for ill-conditioned Toeplitz systems that arise from a priori known real-valued nonnegative generating functions f(x,y) having roots of even multiplicities. Our preconditioned matrix is constructed by using a trigonometric polynomial θ(x,y) obtained from Fourier/kernel approximations or from the use of a proper interpolation scheme. Both of the above techniques produce a trigonometric polynomial θ(x,y) which approximates the generating function f(x,y), and hence the preconditioned matrix is forced to have clustered spectrum. As θ(x,y) is chosen to be a trigonometric polynomial, the preconditioner is a block band Toeplitz matrix with Toeplitz blocks, and therefore its inversion does not increase the total complexity of the PCG method. Preconditioning by block Toeplitz matrices has been treated in the literature in several papers. We compare our method with their results and we show the efficiency of our proposal through various numerical experiments.This research was co-funded by the European Union in the framework of the program “Pythagoras I” of the “Operational Program for Education and Initial Vocational Training” of the 3rd Community Support Framework of the Hellenic Ministry of Education, funded by national sources (25%) and by the European Social Fund - ESF (75%). The work of the second and of the third author was partially supported by MIUR (Italian Ministry of University and Research), grant number 2004015437.     

Inverse product Toeplitz preconditioners for non-Hermitian Toeplitz systems

In this paper, we first propose product Toeplitz preconditioners (in an inverse form) for non-Hermitian Toeplitz matrices generated by functions with zeros. Our inverse product-type preconditioner is of the form T_F T_L^-1 T_U^-1T_F T_L^{-1} T_U^{-1} where T _F , T _L , and T _U are full, band lower triangular, and band upper triangular Toeplitz matrices, respectively. Our basic idea is to decompose the generating function properly such that all factors T _F , T _L , and T _U of the preconditioner are as well-conditioned as possible. We prove that under certain conditions, the preconditioned matrix has eigenvalues and singular values clustered around 1. Then we use a similar idea to modify the preconditioner proposed in Ku and Kuo (SIAM J Sci Stat Comput 13:1470–1487, 1992) to handle the zeros in rational generating functions. Numerical results, including applications to the computation of the stationary probability distribution of Markovian queuing models with batch arrival, are given to illustrate the good performance of the proposed preconditioners.     

Limit Distributions of Eigenvalues for Random Block Toeplitz and Hankel Matrices

Block Toeplitz and Hankel matrices arise in many aspects of applications. In this paper, we will research the distributions of eigenvalues for some models and get the semicircle law. Firstly we will give trace formulas of block Toeplitz and Hankel matrix. Then we will prove that the almost sure limit g_T^(m)\gamma_{T}^{(m)} (g_H^(m))(\gamma_{H}^{(m)}) of eigenvalue distributions of random block Toeplitz (Hankel) matrices exist and give the moments of the limit distributions where m is the order of the blocks. Then we will prove the existence of almost sure limit of eigenvalue distributions of random block Toeplitz and Hankel band matrices and give the moments of the limit distributions. Finally we will prove that g_T^(m)\gamma_{T}^{(m)} (g_H^(m))(\gamma_{H}^{(m)}) converges weakly to the semicircle law as m→∞.     

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.     

Toeplitz approximate inverse preconditioner for banded Toeplitz matrices

In this paper we introduce a new preconditioner for banded Toeplitz matrices, whose inverse is itself a Toeplitz matrix. Given a banded Hermitian positive definite Toeplitz matrixT, we construct a Toepliz matrixM such that the spectrum ofMT is clustered around one; specifically, if the bandwidth ofT is , all but eigenvalues ofMT are exactly one. Thus the preconditioned conjugate gradient method converges in +1 steps which is about half the iterations as required by other preconditioners for Toepliz systems that have been suggested in the literature. This idea has a natural extension to non-banded and non-Hermitian Toeplitz matrices, and to block Toeplitz matrices with Toeplitz blocks which arise in many two dimensional applications in signal processing. Convergence results are given for each scheme, as well as numerical experiments illustrating the good convergence properties of the new preconditioner.Partly supported by a travel fund from the Deutsche Forschungsgemeinschaft.Research supported in part by Oak Ridge Associated Universities grant no. 009707.     

BTTB preconditioners for BTTB systems

In this paper, we consider solving the BTTB system \({\cal T}_{m,n}[f] {\bf{x}} = {\bf{b}}\) by the preconditioned conjugate gradient (PCG) method, where \({\cal T}_{m,n}[f]\) denotes the m × m block Toeplitz matrix with n × n Toeplitz blocks (BTTB) generated by a (2π, 2π)-periodic continuous function f(x, y). We propose using the BTTB matrix \({\cal T}_{m,n}[1/f]\) to precondition the BTTB system and prove that only O(m)?+?O(n) eigenvalues of the preconditioned matrix \({\cal T}_{m,n}[1/f] {\cal T}_{m,n}[f]\) are not around 1 under the condition that f(x, y)?>?0. We then approximate 1/f(x, y) by a bivariate trigonometric polynomial, which can be obtained in O(m n log(m n)) operations by using the fast Fourier transform technique. Numerical results show that our BTTB preconditioner is more efficient than block circulant preconditioners.     

BTTB preconditioners for BTTB least squares problems

In this paper, we consider solving the least squares problem min_x‖b-Tx‖₂ by using preconditioned conjugate gradient (PCG) methods, where T is a large rectangular matrix which consists of several square block-Toeplitz-Toeplitz-block (BTTB) matrices and b is a column vector. We propose a BTTB preconditioner to speed up the PCG method and prove that the BTTB preconditioner is a good preconditioner. We then discuss the construction of the BTTB preconditioner. Numerical examples, including image restoration problems, are given to illustrate the efficiency of our BTTB preconditioner. Numerical results show that our BTTB preconditioner is more efficient than the well-known Level-1 and Level-2 circulant preconditioners.     

Constrained minimax approximation and optimal preconditioned for Toeplitz matrices

A good preconditioner is extremely important in order for the conjugate gradients method to converge quickly. In the case of Toeplitz matrices, a number of recent studies were made to relate approximation of functions to good preconditioners. In this paper, we present a new result relating the quality of the Toeplitz preconditionerC for the Toeplitz matrixT to the Chebyshev norm (f– g)/f, wheref and g are the generating functions forT andC, respectively. In particular, the construction of band-Toeplitz preconditioners becomes a linear minimax approximation problem. The case whenf has zeros (but is nonnegative) is especially interesting and the corresponding approximation problem becomes constrained. We show how the Remez algorithm can be modified to handle the constraints. Numerical experiments confirming the theoretical results are presented.     

SINE TRANSFORM MATRIX FOR SOLVING TOEPLITZ MATRIX PROBLEMS

1. IntroductionStrang[1] first studied the use of circulallt matrices C for solving systems of linear eqllationsTi x = b witha symmetric positive definite Toeplitz matrix.Numerous authors such as T.Chan[2],R.Chan,etc.[3],[4],[5], Tyrtyshnikov[6], Huckle[7] and T.Ku and C.Kuo[8] proposed differentfamilies of circulallt / skew- circulant precondit ioners.Appling the preconditioned conjugate gradient algorithm(PCGA) to solve the systems Ti x -b, we must find a preconditioner P such that P…     

Block ILU Preconditioners for a Nonsymmetric Block-Tridiagonal M-Matrix

We propose block ILU (incomplete LU) factorization preconditioners for a nonsymmetric block-tridiagonal M-matrix whose computation can be done in parallel based on matrix blocks. Some theoretical properties for these block ILU factorization preconditioners are studied and then we describe how to construct them effectively for a special type of matrix. We also discuss a parallelization of the preconditioner solver step used in nonstationary iterative methods with the block ILU preconditioners. Numerical results of the right preconditioned BiCGSTAB method using the block ILU preconditioners are compared with those of the right preconditioned BiCGSTAB using a standard ILU factorization preconditioner to see how effective the block ILU preconditioners are.     

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.     

The generalized superoptimal preconditioner

For any given n-by-n matrix A, a specific circulant preconditioner t_F(A) introduced by Tyrtyshnikov [E. Tyrtyshnikov, Optimal and super-optimal circulant preconditioners, SIAM J. Matrix Anal. Appl. 13 (1992) 459-473] is defined to be the solution of

     

Equilibrium problem for the eigenvalues of banded block Toeplitz matrices

We consider banded block Toeplitz matrices T_n with n block rows and columns. We show that under certain technical assumptions, the normalized eigenvalue counting measure of T_n for n → ∞ weakly converges to one component of the unique vector of measures that minimizes a certain energy functional. In this way we generalize a recent result of Duits and Kuijlaars for the scalar case. Along the way we also obtain an equilibrium problem associated to an arbitrary algebraic curve, not necessarily related to a block Toeplitz matrix. For banded block Toeplitz matrices, there are several new phenomena that do not occur in the scalar case: (i) The total masses of the equilibrium measures do not necessarily form a simple arithmetic series but in general are obtained through a combinatorial rule; (ii) The limiting eigenvalue distribution may contain point masses, and there may be attracting point sources in the equilibrium problem; (iii) More seriously, there are examples where the connection between the limiting eigenvalue distribution of T_n and the solution to the equilibrium problem breaks down. We provide sufficient conditions guaranteeing that no such breakdown occurs; in particular we show this if T_n is a Hessenberg matrix.     

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.     

Fastiterative methods for least squares estimations

Least squares estimations have been used extensively in many applications, e.g. system identification and signal prediction. When the stochastic process is stationary, the least squares estimators can be found by solving a Toeplitz or near-Toeplitz matrix system depending on the knowledge of the data statistics. In this paper, we employ the preconditioned conjugate gradient method with circulant preconditioners to solve such systems. Our proposed circulant preconditioners are derived from the spectral property of the given stationary process. In the case where the spectral density functions() of the process is known, we prove that ifs() is a positive continuous function, then the spectrum of the preconditioned system will be clustered around 1 and the method converges superlinearly. However, if the statistics of the process is unknown, then we prove that with probability 1, the spectrum of the preconditioned system is still clustered around 1 provided that large data samples are taken. For finite impulse response (FIR) system identification problems, our numerical results show that annth order least squares estimator can usually be obtained inO(n logn) operations whenO(n) data samples are used. Finally, we remark that our algorithm can be modified to suit the applications of recursive least squares computations with the proper use of sliding window method arising in signal processing applications.Research supported in part by HKRGC grant no. 221600070, ONR contract no. N00014-90-J-1695 and DOE grant no. DE-FG03-87ER25037.