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.     

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.     

Every Matrix is a Product of Toeplitz Matrices

We show that every \(n\,\times \,n\) matrix is generically a product of \(\lfloor n/2 \rfloor + 1\) Toeplitz matrices and always a product of at most \(2n+5\) Toeplitz matrices. The same result holds true if the word ‘Toeplitz’ is replaced by ‘Hankel,’ and the generic bound \(\lfloor n/2 \rfloor + 1\) is sharp. We will see that these decompositions into Toeplitz or Hankel factors are unusual: We may not, in general, replace the subspace of Toeplitz or Hankel matrices by an arbitrary \((2n-1)\)-dimensional subspace of \({n\,\times \,n}\) matrices. Furthermore, such decompositions do not exist if we require the factors to be symmetric Toeplitz or persymmetric Hankel, even if we allow an infinite number of factors.     

Spectral and Computational Analysis of Block Toeplitz Matrices Having Nonnegative Definite Matrix-Valued Generating Functions

It is well known that the generating function f L ¹([–, ], ) of a class of Hermitian Toeplitz matrices A _n(f) _n describes very precisely the spectrum of each matrix of the class. In this paper we consider n × n Hermitian block Toeplitz matrices with m × m blocks generated by a Hermitian matrix-valued generating function f L ¹([–, ], C ^m×m ). We extend to this case some classical results by Grenander and Szegö holding when m = 1 and we generalize the Toeplitz preconditioning technique introduced in the scalar case by R. H. Chan and F. Di Benedetto, G. Fiorentino and S. Serra. Finally, concerning the spectra of the preconditioned matrices, some asymptotic distribution properties are demonstrated and, in particular, a Szegö-style theorem is proved. A few numerical experiments performed at the end of the paper confirm the correctness of the theoretical analysis.     

The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases

This paper investigates a restricted version of the Quadratic Assignment Problem (QAP), where one of the coefficient matrices is an Anti-Monge matrix with non-decreasing rows and columns and the other coefficient matrix is a symmetric Toeplitz matrix. This restricted version is called the Anti-Monge—Toeplitz QAP. There are three well-known combinatorial problems that can be modeled via the Anti-Monge—Toeplitz QAP: (Pl) The Turbine Problem, i.e. the assignment of given masses to the vertices of a regular polygon such that the distance of the center of gravity of the resulting system to the center of the polygon is minimized. (P2) The Traveling Salesman Problem on symmetric Monge distance matrices. (P3) The arrangement of data records with given access probabilities in a linear storage medium in order to minimize the average access time. We identify conditions on the Toeplitz matrixB that lead to a simple solution for the Anti-Monge—Toeplitz QAP: The optimal permutation can be given in advance without regarding the numerical values of the data. The resulting theorems generalize and unify several known results on problems (P1), (P2), and (P3). We also show that the Turbine Problem is NP-hard and consequently, that the Anti-Monge—Toeplitz QAP is NP-hard in general. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Dedicated to the memory of Gene LawlerThis research has been supported by the Spezialforschungsbereich F 003 Optimierung und Kontrolle, Projektbereich Diskrete Optimierung.     

On the Singular Values of Generalized Toeplitz Matrices

For a bounded function defined on , let be the set of singular values of the (n + 1) x (n + 1) matrix whose (j, k)-entries are equal to

Toeplitz operators on weightedl p spaces and associated asymptotics

Asymptotic information is found in this paper for finite Toeplitz matrices generated by a piecewise continuous function. The eigenvalues for certain finite matrices are shown to lie near the range of the generating function. An asymptotic formula for f( _i ) where _i are the eigenvalues is also given. The basic technique of the paper is to get the above type of asymptotic information by studying the ordinary Toeplitz operators on weightedl _p spaces.     

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.     

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.     

On the Zeros of Eigenpolynomials of Hermitian Toeplitz Matrices

This article refines a result of Delsarte, Genin, Kamp (Circuits Syst Signal Process 3:207–223, 1984), and Delsarte and Genin (Springer Lect Notes Control Inf Sci 58:194–213, 1984), regarding the number of zeros on the unit circle of eigenpolynomials of complex Hermitian Toeplitz matrices and generalized Caratheodory representations of such matrices. This is achieved by exploring a key observation of Schur (Über einen Satz von C. Carathéodory. Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften, pp. 4–15, 1912) stated in his proof of a famous theorem of Carathéodory (Rendiconti del Circolo Matematico di Palermo 32:193–217, 1911). In short, Schur observed that companion matrices corresponding to eigenpolynomials of Hermitian Toeplitz matrices H define isometries with respect to (spectrum shifted) submatrices of H. Looking at possible normal forms of these isometries leads directly to the results. This geometric, conceptual approach can be generalized to Hermitian or symmetric Toeplitz matrices over arbitrary fields. Furthermore, as a byproduct, Iohvidov’s law in the jumps of the ranks and the connection between the Iohvidov parameter and the Witt index are established for such Toeplitz matrices.     

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 and Wiener-Hopf determinants with piecewise continuous symbols

The asymptotics for determinants of Toeplitz and Wiener-Hopf operators with piecewise continuous symbols are obtained in this paper. If W_α(σ) is the Wiener-Hopf operator defined on L₂(0, α) with piecewise continuous symbol σ having a finite number of discontinuities at ξ_r, then under appropriate conditions it is shown that det W_α(σ) ˜ G(σ)^α α^Σλ_r2K(σ), where

Full-size image

is a completely determined constant. An analogous result is obtained for Toeplitz operators. The main point of the paper is to obtain a result in the Wiener-Hopf case since the Toeplitz case had been treated earlier. In the Toeplitz case it was discovered that one could obtain asymptotics fairly easily for symbols with several singularities if, for each singularity one could find a single example of a symbol with a singularity of that kind whose associated asymptotics were known. Fortunately in the Toeplitz case such asymptotics were known. The difficulty in the Wiener-Hopf case is that there was not a single singular case where the determinant was explicitly known. This problem was overcome by using the fact that Wiener-Hopf determinants when discretized become Toeplitz determinants whose entries depend on the size of the matrix. No theorem on Toeplitz matrices can be applied directly but these theorems are modified to obtain the desired results.     

Spectral Distribution Results Beyond the Algebra Generated by Variable-Coefficient Toeplitz Sequences: The GLT Approach

We show that, under suitable assumptions on the function \(a:[0,1]^2\times [-\pi ,\pi ]\rightarrow \mathbb C\), the sequence of variable-coefficient Toeplitz matrices generated by a is a generalized locally Toeplitz (GLT) sequence with symbol \(a(x,x,\theta )\). This property, in combination with the theory of GLT sequences, allows us to derive a lot of spectral distribution (Szeg?-type) results for various sequences of matrices, including those obtained from algebraic and non-algebraic operations on variable-coefficient Toeplitz sequences.     

Toeplitz and Hankel matrices on ℂ n

It is known that the characterizations of the Toeplitz operatorT onH ² and also the Hankel operatorH onH ² by using the simple unilateral shiftT _z . Recently, some characterization of the normal Toeplitz matrix truncated on ⁿ is given by D.R.Farenick, M. Krupnik, N. Krupnik and W. Y. Lee [1] and, independently, by T.Ito [2]. In this paper, we shall give some characterizations of the Toeplitz matrix and also the Hankel matrix truncated on ⁿ .Dedicated to Professor Masanori Fukamiya on his 88th birthday     

$$\mathcal $$ working precision inverses for symmetric tridiagonal Toeplitz matrices with $$\mathcal O(1)$$O(1) floating point calculations

A well known numerical task is the inversion of large symmetric tridiagonal Toeplitz matrices, i.e., matrices whose entries equal a on the diagonal and b on the extra diagonals (\(a, b\in \mathbb R\)). The inverses of such matrices are dense and there exist well known explicit formulas by which they can be calculated in \(\mathcal O(n^2)\). In this note we present a simplification of the problem that has proven to be rather useful in everyday practice: If \(\vert a\vert > 2\vert b\vert \), that is, if the matrix is strictly diagonally dominant, its inverse is a band matrix to working precision and the bandwidth is independent of n for sufficiently large n. Employing this observation, we construct a linear time algorithm for an explicit tridiagonal inversion that only uses \(\mathcal O(1)\) floating point operations. On the basis of this simplified inversion algorithm we outline the cornerstones for an efficient parallelizable approximative equation solver.     

A Widom like formula for some Toeplitz plus Hankel determinants

A well known Widom formula expresses the determinant of a Toeplitz matrix _Tn$T_n$ with Laurant polynomial symbol f in terms of the zeros of f. We give similar formulae for some even Toeplitz plus Hankel matrices. The formulae are based on an analytic representation of the determinant of such matrices in terms of Chebyshev polynomials.     

A catalog of minimally nonideal matrices

This paper describes a backtracking algorithm for the enumeration of nonisomorphic minimally nonideal (n ×n) matrices that are not degenerate projective planes. The application of this algorithm forn 12 yielded 20 such matrices, adding 5 matrices to the 15 previously known. For greater dimensions,n = 14 andn = 17, 13 new matrices are given. For nonsquare matrices, 38 new minimally nonindeal matrices are described.Research supported by FNRS grant. Switzerland, while visiting Carnegie Mellon University, Pittsburgh, PA 15213.     

Commutative <Emphasis Type="Italic">C</Emphasis>*-Algebras of Toeplitz Operators on the Unit Ball,I. Bargmann-Type Transforms and Spectral Representations of Toeplitz Operators

Extending known results for the unit disk, we prove that for the unit ball there exist n+2 different cases of commutative C*-algebras generated by Toeplitz operators, acting on weighted Bergman spaces. In all cases the bounded measurable symbols of Toeplitz operators are invariant under the action of certain commutative subgroups of biholomorphisms of the unit ball. This work was partially supported by CONACYT Projects 46936 and 44620, México.