A note on structured pseudospectra

In this note, we study the notion of structured pseudospectra. We prove that for Toeplitz, circulant, Hankel and symmetric structures, the structured pseudospectrum equals the unstructured pseudospectrum. We show that this is false for Hermitian and skew-Hermitian structures. We generalize the result to pseudospectra of matrix polynomials. Indeed, we prove that the structured pseudospectrum equals the unstructured pseudospectrum for matrix polynomials with Toeplitz, circulant, Hankel and symmetric structures. We conclude by giving a formula for structured pseudospectra of real matrix polynomials. The particular type of perturbations used for these pseudospectra arise in control theory.     

带多重右边的不定最小二乘问题的条件数

本文研究了带多重右边的不定最小二乘问题的条件数,给出了范数型、混合型及分量型条件数的表达式,同时,也给出了相应的结构条件数的表达式.所考虑的结构矩阵包含Toeplitz 矩阵、Hankel矩阵、对称矩阵、三对角矩阵等线性结构矩阵与Vandermonde矩阵、Cauchy矩阵等非线性结构矩阵.数值例子显示结构条件数总是紧于非结构条件数.     

Structured mixed and componentwise condition numbers of some structured matrices

Structured matrices, such as Cauchy, Vandermonde, Toeplitz, Hankel, and circulant matrices, are considered in this paper. We apply a Kronecker product-based technique to deduce the structured mixed and componentwise condition numbers for the matrix inversion and for the corresponding linear systems.     

Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

In this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log²n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given.     

On inversion of square matrices partitioned into non-square blocks

Inversion theorems for structured block matrices with non-square blocks are presented. The considered classes contain Toeplitz, Toeplitz plus Hankel and Van der Monde type matrices.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

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.     

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.     

Matrix representations of split Bezoutians

Inverses of symmetric (or skewsymmetric) Toeplitz matrices as well as of centrosymmetric (or centro-skewsymmetric) Toeplitz-plus-Hankel matrices can be represented as sums of two split Bezoutians which are highly structured matrices since all of their rows and columns are symmetric or skewsymmetric vectors. Thus it is desirable to find matrix representations for split Bezoutians B. This is the main aim of the present paper.Recursion formulas for the entries of B are presented, bases of very simple split Bezoutians or of sparse matrices are constructed, and B is represented as a corresponding linear combination. Moreover, matrix representations of Gohberg/Semencul type are established.     

Localization of eigenvalues of polynomial matrices

We consider the problem of localization of eigenvalues of polynomial matrices. We propose sufficient conditions for the spectrum of a regular matrix polynomial to belong to a broad class of domains bounded by algebraic curves. These conditions generalize the known method for the localization of the spectrum of polynomial matrices based on the solution of linear matrix inequalities. We also develop a method for the localization of eigenvalues of a parametric family of matrix polynomials in the form of a system of linear matrix inequalities.     

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.     

Linear codes using skew polynomials with automorphisms and derivations

In this work the definition of codes as modules over skew polynomial rings of automorphism type is generalized to skew polynomial rings, whose multiplication is defined using an automorphism and a derivation. This produces a more general class of codes which, in some cases, produce better distance bounds than module skew codes constructed only with an automorphism. Extending the approach of Gabidulin codes, we introduce new notions of evaluation of skew polynomials with derivations and the corresponding evaluation codes. We propose several approaches to generalize Reed-Solomon and BCH codes to module skew codes and for two classes we show that the dual of such a Reed-Solomon type skew code is an evaluation skew code. We generalize a decoding algorithm due to Gabidulin for the rank metric and derive families of Maximum Distance Separable and Maximum Rank Distance codes.     

Common multiples and common divisors of matrix polynomials, II. Vandermonde and resultant matrices

In this paper explicit formulas are given for least common multiples and greatest common divisors of a finite number of matrix polynomials in terms of the coefficients of the given polynomials. An important role is played by block matrix generalizations of the classical Vandermonde and resultant matrices. Special attention is given to the evaluation of the degrees and other characteristics. Applications to matrix polynomial equations and factorization problems are made.     

On Distinguished Solutions of Truncated Matricial Hamburger Moment Problems

We study two slightly different versions of the truncated matricial Hamburger moment problem. A central topic is the construction and investigation of distinguished solutions of both moment problems under consideration. These solutions turn out to be nonnegative Hermitian q × q Borel measures on the real axis which are concentrated on a finite number of points. These points and the corresponding masses will be explicitly described in terms of the given data. Furthermore, we investigate a particular class of sequences (s_j)^∞_{j = 0} of complex q × q matrices for which the corresponding infinite matricial Hamburger moment problem has a unique solution. Our approach is mainly algebraic. It is based on the use of particular matrix polynomials constructed from a nonnegative Hermitian block Hankel matrix. These matrix polynomials are immediate generalizations of the monic orthogonal matrix polynomials associated with a positive Hermitian block Hankel matrix. We generalize a classical theorem due to Kronecker on infinite Hankel matrices of finite rank to block Hankel matrices and discuss its consequences for the nonnegative Hermitian case.     

Polynomial numerical hulls of matrix polynomials,II

In this article, we study some algebraic and geometrical properties of polynomial numerical hulls of matrix polynomials and joint polynomial numerical hulls of a finite family of matrices (possibly the coefficients of a matrix polynomial). Also, we study polynomial numerical hulls of basic A-factor block circulant matrices. These are block companion matrices of particular simple monic matrix polynomials. By studying the polynomial numerical hulls of the Kronecker product of two matrices, we characterize the polynomial numerical hulls of unitary basic A-factor block circulant matrices.     

S-matrices

A new class of so called S-matrices is introduced which allows investigating links between various known classes of matrices such as Vandermonde matrices, Hankel matrices, companion matrices, etc. For complex S-matrices, the problem of decomposition into a quasidirect sum (a sum for which the sum of the ranks of the summands equals the rank of the given matrix) of indecomposable complex S-matrices is completely solved, and the uniqueness of such a decomposition is proved.     

Structured perturbations of group inverse and singular linear system with index one

In this paper, we study the normwise perturbation theory of singular linear structured system with index one. The structures under investigation are Toeplitz, circulant, Hankel matrices. We show that the structured condition number is smaller than unstructured condition number. For specific right-hand side, we present the condition number for structured system.     

Tensored polynomial models

The theme of the present paper is to introduce and study two different versions of tensor products of functional models, one over the underlying field and the other over the corresponding algebra of polynomials, as well as related models based on the Kronecker product of polynomial matrices. In the process, we study the Sylvester equation and its reduction to a polynomial matrix equation. We analyse the relation between the two tensor products and use this to elucidate the role of the Anderson-Jury generalized Bezoutians in this context.     

Algebras in matrix spaces with displacement structure

We introduce the problem of the location of the algebras contained in a matrix space with displacement structure. We present some partial solutions of the problem that unify and generalize various results obtained so far for the spaces of Toeplitz, Loewner and Toeplitz plus Hankel matrices.