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.     

On backward errors of structured polynomial eigenproblems solved by structure preserving linearizations

We derive explicit computable expressions of structured backward errors of approximate eigenelements of structured matrix polynomials including symmetric, skew-symmetric, Hermitian, skew-Hermitian, even and odd polynomials. We determine minimal structured perturbations for which approximate eigenelements are exact eigenelements of the perturbed polynomials. We also analyze structured pseudospectra of a structured matrix polynomial and establish a partial equality between unstructured and structured pseudospectra. Finally, we analyze the effect of structure preserving linearizations of structured matrix polynomials on the structured backward errors of approximate eigenelements and show that structure preserving linearizations which minimize structured condition numbers of eigenvalues also minimize the structured backward errors of approximate eigenelements.     

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.     

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.     

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

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

Pseudospectra of Matrix Polynomials that Are Expressed in Alternative Bases

Spectra and pseudospectra of matrix polynomials are of interest in geometric intersection problems, vibration problems, and analysis of dynamical systems. In this note we consider the effect of the choice of polynomial basis on the pseudospectrum and on the conditioning of the spectrum of regular matrix polynomials. In particular, we consider the direct use of the Lagrange basis on distinct interpolation nodes, and give a geometric characterization of “good” nodes. We also give some tools for computation of roots at infinity via a new, natural, reversal. The principal achievement of the paper is to connect pseudospectra to the well-established theory of Lebesgue functions and Lebesgue constants, by separating the influence of the scalar basis from the natural scale of the matrix polynomial, which allows many results from interpolation theory to be applied. This work was partially funded by the Natural Sciences and Engineering Research Council of Canada, and by the MITACS Network of Centres of Excellence.     

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.     

Condition Numbers for Structured Least Squares Problems

This paper studies the normwise perturbation theory for structured least squares problems. The structures under investigation are symmetric, persymmetric, skewsymmetric, Toeplitz and Hankel. We present the condition numbers for structured least squares. AMS subject classification (2000) 15A18, 65F20, 65F25, 65F50     

On pseudospectra of matrix polynomials and their boundaries

In the first part of this paper (Sections 2-4), the main concern is with the boundary of the pseudospectrum of a matrix polynomial and, particularly, with smoothness properties of the boundary. In the second part (Sections 5-6), results are obtained concerning the number of connected components of pseudospectra, as well as results concerning matrix polynomials with multiple eigenvalues, or the proximity to such polynomials.

     

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.     

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.     

Limiting spectral distributions of some band matrices

We use the method of moments to establish the limiting spectral distribution (LSD) of appropriately scaled large dimensional random symmetric circulant, reverse circulant, Toeplitz and Hankel matrices which have suitable band structures. The input sequence used to construct these matrices is assumed to be either i.i.d. with mean zero and variance one or independent and appropriate finite fourth moment. The class of LSD includes the normal and the symmetrized square root of chi-square with two degrees of freedom. In several other cases, explicit forms of the limit do not seem to be obtainable but the limits can be shown to be symmetric and their second and the fourth moments can be calculated with some effort. Simulations suggest some further properties of the limits.     

An eigenvalue problem for a symmetric Toeplitz matrix

An algorithm is developed which determines eigenvalues for a symmetric Toeplitz matrix. To this end, we substantiate the generality of eigenvalues problems for a symmetric Toeplitz matrix and for a persymmetric Hankel one. The latter is reduced to an eigenvalue problem for a persymmetric Jacobi matrix. In the even order case, the problem reduces to a Jacobi matrix with halved order.     

Convolution Operators on Expanding Polyhedra: Limits of the Norms of Inverse Operators and Pseudospectra

We consider matrix convolution operators with integrable kernels on expanding polyhedra. We study their connection with convolution operators on the cones at the vertices of polyhedra. We prove that the norm of the inverse operator on a polyhedron tends to the maximum of the norms of the inverse operators on the cones, and the pseudospectrum tends to the union of the corresponding pseudospectra. The study bases on the local method adapted to this kind of problems.     

A distance bound for pseudospectra of matrix polynomials

In this note, we obtain a lower bound for the distance between the pseudospectrum of a matrix polynomial and a given point that lies out of it, generalizing a known result on pseudospectra of matrices.     

Randomized preprocessing versus pivoting

It is known that without pivoting Gaussian elimination can run significantly faster (particularly for matrices that have structures of Toeplitz or Hankel types), but becomes numerically unsafe. The known remedies take their toll, e.g., symmetrization squares the condition number of the input matrix. Can we fix the problem without such a punishment? Taking this challenge we combine randomized preconditioning techniques with iterative refinement and prove that this combination is expected to make pivoting-free Gaussian elimination numerically safe while keeping it fast. For matrices having structures of Toeplitz or Hankel types transition to Gaussian elimination with no pivoting decreases arithmetic time bound from cubic to nearly linear, and our tests show dramatic decrease of the CPU time as well.     

Formal orthogonal polynomials and Hankel/Toeplitz duality

For classical polynomials orthogonal with respect to a positive measure supported on the real line, the moment matrix is Hankel and positive definite. The polynomials satisfy a three term recurrence relation. When the measure is supported on the complex unit circle, the moment matrix is positive definite and Toeplitz. Then they satisfy a coupled Szeg recurrence relation but also a three term recurrence relation. In this paper we study the generalization for formal polynomials orthogonal with respect to an arbitrary moment matrix and consider arbitrary Hankel and Toeplitz matrices as special cases. The relation with Padé approximation and with Krylov subspace iterative methods is also outlined.This research was supported by the National Fund for Scientific Research (NFWO), project Lanczos, grant #2.0042.93.     

On zero-pattern invariant properties of structured matrices

It is interesting that inverse M-matrices are zero-pattern (power) invariant. The main contribution of the present work is that we characterize some structured matrices that are zero-pattern (power) invariant. Consequently, we provide necessary and sufficient conditions for these structured matrices to be inverse M-matrices. In particular, to check if a given circulant or symmetric Toeplitz matrix is an inverse M-matrix, we only need to consider its pattern structure and verify that one of its principal submatrices is an inverse M-matrix.     

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     

Spectral Norm of Circulant-Type Matrices

We first discuss the convergence in probability and in distribution of the spectral norm of scaled Toeplitz, circulant, reverse circulant, symmetric circulant, and a class of k-circulant matrices when the input sequence is independent and identically distributed with finite moments of suitable order and the dimension of the matrix tends to ∞.