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.     

A New Inertia Theorem for Stein Equations,Inertia of Invertible Hermitian Block Toeplitz Matrices and Matrix Orthogonal Polynomials

In this paper we present an inertia result for Stein equations with an indefinite right hand side. This result is applied to establish connnections between the inertia of invertible hermitian block Toeplitz matrices and associated orthogonal polynomials.     

广义块Toeplitz特征值问题的基于sine变换的预处理子

在求块Toeplitz矩阵束（Amn，Bmn）特征值的Lanczos过程中，通过对移位块Toepltz矩阵Amn-ρBmn进行基于sine变换的块预处理，从而改进了位移块Toeplitz矩阵的谱分布，加速了Lanczos过程的收敛速度．该块预处理方法能通过快速算法有效快速执行．本文证明了预处理后Lanczos过程收敛迅速，并通过实验证明该算法求解大规模矩阵问题尤其有效．     

分块r-循环Toeplitz矩阵的特征值方程

给出了分块 r-循环 Toeplitz矩阵特征方程的一个求法 ,推广了文 [1 ]的结果 .     

块Toeplitz三角阵求逆及块Toeplitz三角线性方程组求解的复杂性

In this paper, it is showed that the computational complexity of inversion of block triangular Toeplitz matrix U= (U₀, U₁,…, U_n-1 ) is O (m²nlogn + m³), as well as solution of block triangla r Toeplitz linear systems, where U 's are m×m mat rices. By using this results, we reduce arithmetic operations of division of polynomials from O(nlog²n) to O(nlogn).     

四元数体上Hermite矩阵的最小化问题

该文建立了四元数矩阵对的标准相关分解(CCD-Q). 借助CCD-Q, GSVD-Q 和有限维内积空间中的投影定理, 该文得到了基于四元数矩阵方程$AXB=C$的Hermite矩阵最小化问题解的表达式.     

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→∞.     

The Cayley Method and the Inverse Eigenvalue Problem for Toeplitz Matrices

Despite the fact that symmetric Toeplitz matrices can have arbitrary eigenvalues, the numerical construction of such a matrix having prescribed eigenvalues remains to be a challenge. A two-step method using the continuation idea is proposed in this paper. The first step constructs a centro-symmetric Jacobi matrix with the prescribed eigenvalues in finitely many steps. The second step uses the Cayley transform to integrate flows in the linear subspace of skew-symmetric and centro-symmetric matrices. No special geometric integrators are needed. The convergence analysis is illustrated for the case of n = 3. Numerical examples are presented.     

On the Approximation Numbers for the Finite Sections of Block Toeplitz Matrices

In this paper we discuss the asymptotic distribution of theapproximation numbers of the finite sections for a Toeplitzoperator and µ R, witha continuous matrix-valued generating function a. We prove thatthe approximation numbers of the finite sections T_n(a) = P_nT(a)P_nhave the k-splitting property, provided T(a) is a Fredholm operatoron . 2000 Mathematics SubjectClassification 47B35 (primary), 15A18, 47A58, 47A75, 65F20 (secondary).     

The First Order Asymptotics of the Extreme Eigenvectors of Certain Hermitian Toeplitz Matrices

The paper is concerned with Hermitian Toeplitz matrices generated by a class of unbounded symbols that emerge in several applications. The main result gives the third order asymptotics of the extreme eigenvalues and the first order asymptotics of the extreme eigenvectors of the matrices as their dimension increases to infinity. This work was partially supported by CONACYT projects 60160 and 80504, Mexico.     

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.     

反厄米特型Toeplitz线性方程组的反厄米特循环预处理子

本文主要研究了带位移的反厄米特型Toeplitz线性方程组Anx=b的一个新的反厄米特循环预处理子Cn,其中矩阵An的元素是函数f（θ）=a0＋ig（θ）的傅里叶系数．如果g（θ）是Wiener类实值函数,则矩阵Cn非奇异;且当n足够大时,矩阵（Cn^-1An）·（Cn^-1An）的谱以1为聚点,数值实验进一步显示了我们的预处理子是有效的．     

The best circulant preconditioners for Hermitian Toeplitz systems II: The multiple-zero case

Summary. In [10,14], circulant-type preconditioners have been proposed for ill-conditioned Hermitian Toeplitz systems that are generated by nonnegative continuous functions with a zero of even order. The proposed circulant preconditioners can be constructed without requiring explicit knowledge of the generating functions. It was shown that the spectra of the preconditioned matrices are uniformly bounded except for a fixed number of outliers and that all eigenvalues are uniformly bounded away from zero. Therefore the conjugate gradient method converges linearly when applied to solving the circulant preconditioned systems. In [10,14], it was claimed that this result can be the case where the generating functions have multiple zeros. The main aim of this paper is to give a complete convergence proof of the method in [10,14] for this class of generating functions. Received October 19, 1999 / Revised version received May 2, 2001 / Published online October 17, 2001     

无限广义块Toeplitz和Hankel矩阵求逆的统一方法

利用 Sylvester位移方程的统一办法给出所谓的无限广义块Toeplitz和 Hankel矩阵的求逆公式 .     

Analysis of the Structured Total Least Squares Problem for Hankel/Toeplitz Matrices

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) approach when structured matrices are involved and a similarly structured rank deficient approximation of that matrix is desired. In many of those cases the STLS approach yields a Maximum Likelihood (ML) estimate as opposed to, e.g., TLS.In this paper we analyze the STLS problem for Hankel matrices (the theory can be extended in a straightforward way to Toeplitz matrices, block Hankel and block Toeplitz matrices). Using a particular parametrisation of rank-deficient Hankel matrices, we show that this STLS problem suffers from multiple local minima, the properties of which depend on the parameters of the new parametrisation. The latter observation makes initial estimates an important issue in STLS problems and a new initialization method is proposed. The new initialization method is applied to a speech compression example and the results confirm the improved performance compared to other previously proposed initialization methods.     

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.