Fast Wavelet Transform for Toeplitz Matrices and Property Analysis

Fast wavelet transform algorithms for Toeplitz matrices are proposed in this paper. Distinctive from the well known discrete trigonometric transforms, such as the discrete cosine transform （DCT） and the discrete Fourier transform （DFT） for Toeplitz matrices, the new algorithms are achieved by compactly supported wavelet that preserve the character of a Toeplitz matrix after transform, which is quite useful in many applications involving a Toeplitz matrix. Results of numerical experiments show that the proposed method has good compression performance similar to using wavelet in the digital image coding. Since the proposed algorithms turn a dense Toeplitz matrix into a band-limited form, the arithmetic operations required by the new algorithms are O（N） that are reduced greatly compared with O（N log N） by the classical trigonometric transforms.     

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.     

On the solutions of the equation AXB = C under Toeplitz‐like and Hankel matrices constraint

In this paper, we are mainly concerned with 2 types of constrained matrix equation problems of the form AXB=C, the least squares problem and the optimal approximation problem, and we consider several constraint matrices, such as general Toeplitz matrices, upper triangular Toeplitz matrices, lower triangular Toeplitz matrices, symmetric Toeplitz matrices, and Hankel matrices. In the first problem, owing to the special structure of the constraint matrix , we construct special algorithms; necessary and sufficient conditions are obtained about the existence and uniqueness for the solutions. In the second problem, we use von Neumann alternating projection algorithm to obtain the solutions of problem. Then we give 2 numerical examples to demonstrate the effectiveness of the algorithms.     

<Literal>smt</Literal>: a Matlab toolbox for structured matrices

The full exploitation of the structure of large scale algebraic problems is often crucial for their numerical solution. Matlab is a computational environment which supports sparse matrices, besides full ones, and allows one to add new types of variables (classes) and define the action of arithmetic operators and functions on them. The smt toolbox for Matlab introduces two new classes for circulant and Toeplitz matrices, and implements optimized storage and fast computational routines for them, transparently to the user. The toolbox, available in Netlib, is intended to be easily extensible, and provides a collection of test matrices and a function to compute three circulant preconditioners, to speed up iterative methods for linear systems. Moreover, it incorporates a simple device to add to the toolbox new routines for solving Toeplitz linear systems.     

A note on the spectral distribution of toeplitz matrices

An elementary and direct proof of the Szegö formula is given, for both eigen and singular values. This proof, which is based on tools from linear algebra and does not rely on the theory of Fourier series, simultaneously embraces multilevel Toeplitz matrices, block Toeplitz matrices and combinations of them. The assumptions on the generating

function f are as weak as possible; indeedf is a matrix-valued function of p variables, and it is only supposed to be integrable. In the case of singular values f(x), and hence the block p-level Toeplitz matrices it generates, are not even supposed to be square matrices. Moreover, in the asymptotic formulas for eigen and singular values the test functions involved are not required to have compact support.     

The structured distance to normality of banded Toeplitz matrices

Spectral properties of normal (2k+1)-banded Toeplitz matrices of order n, with k≤⌊ n/2⌋, are described. Formulas for the distance of (2k+1)-banded Toeplitz matrices to the algebraic variety of similarly structured normal matrices are presented.     

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 Proposal for Toeplitz Matrix Calculations

In contrast to the usual (and successful) direct methods for Toeplitz systems Ax = b, we propose an algorithm based on the conjugate gradient method. The preconditioner is a circulant, so that all matrices have constant diagonals and all matrix-vector multiplications use the Fast Fourier Transform. We also suggest a technique for the eigenvalue problem, where current methods are less satisfactory. If the first indications are supported by further experiment, this new approach may have useful applications—including nearly Toeplitz systems, and parallel computations.     

Convergence of the Multigrid Method of Ill-conditioned Block Toeplitz Systems

We study the solutions of block Toeplitz systems A _mn u = b by the multigrid method (MGM). Here the block Toeplitz matrices A _mn are generated by a nonnegative function f (x,y) with zeros. Since the matrices A _mn are ill-conditioned, the convergence factor of classical iterative methods will approach 1 as the size of the matrices becomes large. These classical methods, therefore, are not applicable for solving ill-conditioned systems. The MGM is then proposed in this paper. For a class of block Toeplitz matrices, we show that the convergence factor of the two-grid method (TGM) is uniformly bounded below 1 independent of mn and the full MGM has convergence factor depending only on the number of levels. The cost per iteration for the MGM is of O(mn log mn) operations. Numerical results are given to explain the convergence rate.     

Quasi-interpolants from spline interpolation operators

For bi-infinite Toeplitz matrices, it is easy to see that thekth partial sum of the Neumann series reproduces polynomials of orderk There is no guarantee, however, that the spectral radius is less than 1. A principal result of this paper is to show that for the spline interpolation Toeplitz case the spectral radius is less than 1 whenA is invertible and the main diagonal is the central diagonal. This is not true for all totally positive Toeplitz matrices as shown by an example in Section 2.Communicated by Charles A. Micchelli.     

An optimal bound for inverses of triangular matrices with monotone entries

This article provides a new bound for 1-norms of inverses of positive triangular matrices with monotonic column entries. The main theorem refines a recent inequality established in Vecchio and Mallik [Bounds on the inverses of non-negative lower triangular Toeplitz matrices with monotonicity properties, Linear Multilinear Alg., 55 (2007), pp. 365–379]. The results are shown to be in a sense best possible under the given constraints.     

On certain decompositions of complex inverse Toeplitz matrices and related fast algorithms for solving linear systems with Toeplitz coefficient matrices

Formulas for inverting nonsingular Toeplitz matrices with complex entries are derived. These formulas either refine known ones or are new. They make it possible to develop economical algorithms for calculating products of inverse Toeplitz matrices with vectors.     

On algebras of Toeplitz fuzzy matrices

In this paper, necessary and sufficient conditions are given for a product of Toeplitz fuzzy matrices to be Toeplitz. As an application, a criterion for normality of Toeplitz fuzzy matrices is derived and conditions are deduced for symmetric idempotency of Toeplitz fuzzy matrices. We discuss similar results for Hankel fuzzy matrices. Keywords: Fuzzy matrix, Toeplitz and Hankel matrices.     

On the properties of matrices defining some classes of BVMs

Summary It is known that the matrices defining the discrete problem generated by a k-step Boundary Value Method (BVM) have a quasi-Toeplitz band structure [7]. In particular, when the boundary conditions are skipped, they become Toeplitz matrices. In this paper, by introducing a characterization of positive definiteness for such matrices, we shall prove that the Toeplitz matrices which arise when using the methods in the classes of BVMs known as Generalized BDF and Top Order Methods have such property. Mathematics Subject Classification (2000):65L06, 47B35, 15A48Work supported by G.N.C.S.     

Nearness results for real tridiagonal 2‐Toeplitz matrices

In this article, we extend the results for Toeplitz matrices obtained by Noschese, Pasquini, and Reichel. We study the distance d, measured in the Frobenius norm, of a real tridiagonal 2‐Toeplitz matrix T to the closure of the set formed by the real irreducible tridiagonal normal matrices. The matrices in , whose distance to T is d, are characterized, and the location of their eigenvalues is shown to be in a region determined by the field of values of the operator associated with T, when T is in a certain class of matrices that contains the Toeplitz matrices. When T has an odd dimension, the eigenvalues of the closest matrices to T in are explicitly described. Finally, a measure of nonnormality of T is studied for a certain class of matrices T. The theoretical results are illustrated with examples. In addition, known results in the literature for the case in which T is a Toeplitz matrix are recovered.     

Weak Convergence in Circulant Matrices

Necessary and sufficient conditions for convergence in distribution of products of i.i.d. d× d random circulant matrices are established here. The important role played by matrices in SO(d) is pointed out, and the validity of this result is shown to also hold for a class of Toeplitz matrices.     

New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices

The problem of solving linear equations, or equivalently of inverting matrices, arises in many fields. Efficient recursive algorithms for finding the inverses of Toeplitz or displacement-type matrices have been known for some time. By introducting a way of characterizing matrices in terms of their “distance” from being Toeplitz, a natural extension of these algorithms is obtained. Several new inversion formulas for the representation of the inverse of non-Toeplitz matrices are also presented.     

On the asymptotics of all eigenvalues of Hermitian Toeplitz band matrices

While extreme eigenvalues of large Hermitian Toeplitz matrices have been studied in detail for a long time, much less is known about individual inner eigenvalues. This paper explores the behavior of the jth eigenvalue of an n-by-n banded Hermitian Toeplitz matrix as n goes to infinity and provides asymptotic formulas that are uniform in j for 1 ≤ j ≤ n. The real-valued generating function of the matrices is assumed to increase strictly from its minimum to its maximum and then to decrease strictly back from the maximum to the minimum, having nonzero second derivatives at the minimum and the maximum.     

Circulant Preconditioners for Indefinite Toeplitz Systems

In recent papers circulant preconditioners were proposed for ill-conditioned Hermitian Toeplitz matrices generated by 2-periodic continuous functions with zeros of even order. It was show that the spectra of the preconditioned matrices are uniformly bounded except for a finite number of outliers and therefore the conjugate gradient method, when applied to solving these circulant preconditioned systems, converges very quickly. In this paper, we consider indefinite Toeplitz matrices generated by 2-periodic continuous functions with zeros of odd order. In particular, we show that the singular values of the preconditioned matrices are essentially bounded. Numerical results are presented to illustrate the fast convergence of CGNE, MINRES and QMR methods.This revised version was published online in October 2005 with corrections to the Cover Date.