BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZ MATRICES FROM SINC METHODS

We give general expressions, analyze algebraic properties and derive eigenvalue bounds for a sequence of Toeplitz matrices associated with the sinc discretizations of various orders of differential operators. We demonstrate that these Toeplitz matrices can be satisfactorily preconditioned by certain banded Toeplitz matrices through showing that the spectra of the preconditioned matrices are uniformly bounded. In particular, we also derive eigenvalue bounds for the banded Toeplitz preconditioners. These results are elementary in constructing high-quality structured preconditioners for the systems of linear equations arising from the sinc discretizations of ordinary and partial differential equations, and are useful in analyzing algebraic properties and deriving eigenvalue bounds for the corresponding preconditioned matrices. Numerical examples are given to show effectiveness of the banded Toeplitz preconditioners.     

The conditioning of Toeplitz band matrices

In this paper, practical conditions to check the well-conditioning of a family of nonsingular Toeplitz band matrices are obtained. All the results are based on the location of the zeros of a polynomial associated with the given family of Toeplitz matrices.The same analysis is also used to derive uniform componentwise bounds for the entries of the inverse matrices in such family.     

Fast Structured Matrix Computations: Tensor Rank and Cohn–Umans Method

We discuss a generalization of the Cohn–Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn–Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen’s tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix–vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block Toeplitz–Toeplitz block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn–Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix–matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability.     

Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available, and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. This paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz‐type matrices.     

Conservative solution of the Fokker–Planck equation for stochastic chemical reactions

In this paper we discuss multigrid methods for ill-conditioned symmetric positive definite block Toeplitz matrices. Our block Toeplitz systems are general in the sense that the individual blocks are not necessarily Toeplitz, but we restrict our attention to blocks of small size. We investigate how transfer operators for prolongation and restriction have to be chosen such that our multigrid algorithms converge quickly. We point out why these transfer operators can be understood as block matrices as well and how they relate to the zeroes of the generating matrix function. We explain how our new algorithms can also be combined efficiently with the use of a natural coarse grid operator. We clearly identify a class of ill-conditioned block Toeplitz matrices for which our algorithmic ideas are suitable. In the final section we present an outlook to well-conditioned block Toeplitz systems and to problems of vector Laplace type. In the latter case the small size blocks can be interpreted as degrees of freedom associated with a node. A large number of numerical experiments throughout the article confirms convincingly that our multigrid solvers lead to optimal order convergence. AMS subject classification (2000) 65N55, 65F10     

Asymptotic Formulas for Determinants of a Sum of Finite Toeplitz and Hankel Matrices

The purpose of this paper is to describe asymptotic formulas for determinants of a sum of finite Toeplitz and Hankel matrices with singular generating functions. The formulas are similar to those of the analogous problem for finite Toeplitz matrices for a certain class of symbols. However, the appearance of the Hankel matrices changes the nature of the asymptotics in some instances depending on the location of the singularities. Several concrete examples are also described in the paper.     

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.     

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.     

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.     

Bounds on the inverses of nonnegative triangular matrices with monotonicity properties

Some bounds on the entries and on the norm of the inverse of triangular matrices with nonnegative and monotone entries are found. All the results are obtained by exploiting the properties of the fundamental matrix of the recurrence relation which generates the sequence of the entries of the inverse matrix. One of the results generalizes a theorem contained in a recent article of one of the authors about Toeplitz matrices.     

Bounds on the inverses of nonnegative triangular matrices with monotonicity properties

Some bounds on the entries and on the norm of the inverse of triangular matrices with nonnegative and monotone entries are found. All the results are obtained by exploiting the properties of the fundamental matrix of the recurrence relation which generates the sequence of the entries of the inverse matrix. One of the results generalizes a theorem contained in a recent article of one of the authors about Toeplitz matrices.     

A note on approximations of traces of products of truncated Toeplitz matrices

The paper establishes error orders for integral limit approximations to the traces of products of truncated Toeplitz matrices generated by integrable real symmetric functions defined on the unit circle. These approximations and the corresponding error bounds are of importance in the statistical analysis of discrete-time stationary processes (asymptotic distributions and large deviations of Toeplitz type quadratic forms, estimation of the spectral parameters and functionals, asymptotic expansions of the estimators, etc.). The results improve the rates obtained by the authors in an earlier paper.     

关于Toeplitz矩阵的某些注记

In this paper,we study real symmetric Toeplitz matrices commutable with tridi-agonal matrices, present more detailed results than those in [1], and extend them to non-symmetric Toeplitz matrices. Also, complex Toeplitz matrices, especially the corresponding matrices of lower order, are discussed.     

Multivariate Polynomials,Duality, and Structured Matrices

We first review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate polynomials. Then we define some natural extensions of such classes of matrices based on their correlation to multivariate polynomials. We describe the correlation in terms of the associated operators of multiplication in the polynomial ring and its dual space, which allows us to generalize these structures to the multivariate case. Multivariate Toeplitz, Hankel, and Vandermonde matrices, Bezoutians, algebraic residues, and relations between them are studied. Finally, we show some applications of this study to rootfinding problems for a system of multivariate polynomial equations, where the dual space, algebraic residues, Bezoutians, and other structured matrices play an important role. The developed techniques enable us to obtain a better insight into the major problems of multivariate polynomial computations and to improve substantially the known techniques of the study of these problems. In particular, we simplify and/or generalize the known reduction of the multivariate polynomial systems to the matrix eigenproblem, the derivation of the Bézout and Bernshtein bounds on the number of the roots, and the construction of multiplication tables. From the algorithmic and computational complexity point, we yield acceleration by one order of magnitude of the known methods for some fundamental problems of solving multivariate polynomial systems of equations.     

Automorphisms on the Toeplitz Algebra with Piecewise Continuous Symbol on the Unit Ball

In this paper, we obtain a Fredholm index formula for Toeplitz operators whose symbols are certain piecewise continuous function matrices on the unit ball. Moreover, using this formula, we discuss the automorphisms on the corresponding Toeplitz algebra     

A unifying approach to abstract matrix algebra preconditioning

In earlier papers Tyrtyshnikov [42] and the first author [14] considered the analysis of clustering properties of the spectra of specific Toeplitz preconditioned matrices obtained by means of the best known matrix algebras. Here we generalize this technique to a generic Banach algebra of matrices by devising general preconditioners related to “convergent” approximation processes [36]. Finally, as case study, we focus our attention on the Tau preconditioning by showing how and why the best matrix algebra preconditioners for symmetric Toeplitz systems can be constructed in this class. Received April 25, 1997 / Revised version received March 13, 1998     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

Fluctuations of eigenvalues and second order Poincaré inequalities

Linear statistics of eigenvalues in many familiar classes of random matrices are known to obey gaussian central limit theorems. The proofs of such results are usually rather difficult, involving hard computations specific to the model in question. In this article we attempt to formulate a unified technique for deriving such results via relatively soft arguments. In the process, we introduce a notion of ‘second order Poincaré inequalities’: just as ordinary Poincaré inequalities give variance bounds, second order Poincaré inequalities give central limit theorems. The proof of the main result employs Stein’s method of normal approximation. A number of examples are worked out, some of which are new. One of the new results is a CLT for the spectrum of gaussian Toeplitz matrices.