Matrix computations and polynomial root-finding with preprocessing

Solution of homogeneous linear systems of equations is a basic operation of matrix computations. The customary algorithms rely on pivoting, orthogonalization and SVD, but we employ randomized preprocessing instead. This enables us to accelerate the solution dramatically, both in terms of the estimated arithmetic cost and the observed CPU time. The approach is effective in the cases of both general and structured input matrices and we extend it and its computational advantages to the solution of nonhomogeneous linear systems of equations, matrix eigen-solving, the solution of polynomial and secular equations, and approximation of a matrix by a nearby matrix that has a smaller rank or a fixed structure (e.g., of the Toeplitz or Hankel type). Our analysis and extensive experiments show the power of the presented algorithms.     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

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.     

A parallel method for fast and practical high-order newton interpolation

We present parallel algorithms for the computation and evaluation of interpolating polynomials. The algorithms use parallel prefix techniques for the calculation of divided differences in the Newton representation of the interpolating polynomial. Forn+1 given input pairs, the proposed interpolation algorithm requires only 2 [log(n+1)]+2 parallel arithmetic steps and circuit sizeO(n ²), reducing the best known circuit size for parallel interpolation by a factor of logn. The algorithm for the computation of the divided differences is shown to be numerically stable and does not require equidistant points, precomputation, or the fast Fourier transform. We report on numerical experiments comparing this with other serial and parallel algorithms. The experiments indicate that the method can be very useful for very high-order interpolation, which is made possible for special sets of interpolation nodes.Supported in part by the National Science Foundation under Grant No. NSF DCR-8603722.Supported by the National Science Foundation under Grants No. US NSF MIP-8410110, US NSF DCR85-09970, and US NSF CCR-8717942 and AT&T under Grant AT&T AFFL67Sameh.     

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.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Tensor properties of multilevel Toeplitz and related matrices

A general proposal is presented for fast algorithms for multilevel structured matrices. It is based on investigation of their tensor properties and develops the idea recently introduced by Kamm and Nagy in the block Toeplitz case. We show that tensor properties of multilevel Toeplitz matrices are related to separation of variables in the corresponding symbol, present analytical tools to study the latter, expose truncation algorithms preserving the structure, and report on some numerical results confirming advantages of the proposal.     

Algorithms for solving Hermite interpolation problems using the Fast Fourier Transform

We present a method for computing the Hermite interpolation polynomial based on equally spaced nodes on the unit circle with an arbitrary number of derivatives in the case of algebraic and Laurent polynomials. It is an adaptation of the method of the Fast Fourier Transform (FFT) for this type of problems with the following characteristics: easy computation, small number of operations and easy implementation.In the second part of the paper we adapt the algorithm for computing the Hermite interpolation polynomial based on the nodes of the Tchebycheff polynomials and we also study Hermite trigonometric interpolation problems.     

Structured eigenvalue condition numbers and linearizations for matrix polynomials

This work is concerned with eigenvalue problems for structured matrix polynomials, including complex symmetric, Hermitian, even, odd, palindromic, and anti-palindromic matrix polynomials. Most numerical approaches to solving such eigenvalue problems proceed by linearizing the matrix polynomial into a matrix pencil of larger size. Recently, linearizations have been classified for which the pencil reflects the structure of the original polynomial. A question of practical importance is whether this process of linearization significantly increases the eigenvalue sensitivity with respect to structured perturbations. For all structures under consideration, we show that this cannot happen if the matrix polynomial is well scaled: there is always a structured linearization for which the structured eigenvalue condition number does not differ much. This implies, for example, that a structure-preserving algorithm applied to the linearization fully benefits from a potentially low structured eigenvalue condition number of the original matrix polynomial.     

Averaging operators for exponential splittings

Averaging operations are considered in connection with exponential splitting methods. Toeplitz plus Hankel related matrices are resplit by applying appropriate averaging operators leading to a hierarchy of structured matrices. With the resulting parts, the option of using exponential splitting methods becomes available. A related, seemingly important group of unitary unipotents is looked at. Based on a formula due to Lenard, a very fast iterative method to find the nearest Toeplitz plus Hankel matrix in the Frobenius norm is devised.     

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.     

Matrix orthogonal Laurent polynomials on the unit circle and Toda type integrable systems

Matrix orthogonal Laurent polynomials in the unit circle and the theory of Toda-like integrable systems are connected using the Gauss–Borel factorization of two, left and a right, Cantero–Morales–Velázquez block moment matrices, which are constructed using a quasi-definite matrix measure. A block Gauss–Borel factorization problem of these moment matrices leads to two sets of biorthogonal matrix orthogonal Laurent polynomials and matrix Szeg? polynomials, which can be expressed in terms of Schur complements of bordered truncations of the block moment matrix. The corresponding block extension of the Christoffel–Darboux theory is derived. Deformations of the quasi-definite matrix measure leading to integrable systems of Toda type are studied. The integrable theory is given in this matrix scenario; wave and adjoint wave functions, Lax and Zakharov–Shabat equations, bilinear equations and discrete flows — connected with Darboux transformations. We generalize the integrable flows of the Cafasso's matrix extension of the Toeplitz lattice for the Verblunsky coefficients of Szeg? polynomials. An analysis of the Miwa shifts allows for the finding of interesting connections between Christoffel–Darboux kernels and Miwa shifts of the matrix orthogonal Laurent polynomials.     

Base tensorielle des matrices de Hankel (ou de Toeplitz) Applications

Summary The set of all Hankel (or Toeplitz) matrices of dimensionn, is shown to possess tensorial bases: bases made ofn rank one matrices. Four families of such tensorial bases are possible. From this result, we deduce that the following computations can be performed with a number of multiplications of ordern instead of ordern ²: evaluation of the 2n+1 coefficients of the polynomial product of two polynomials of degreen, evaluation of the inverse of a lower triangular toeplitz matrix, evaluation of the quotient and of the remainder in the division of a polynomial of degree 2n by a polynomial of degreen.     

Computations in differential and difference modules

Constructive methods based on the Gröbner bases theory have been used many times in commutative algebra over the past 20 years, in particular, they allow the computation of such important invariants of manifolds given by systems of algebraic equations as their Hilbert polynomials. In differential and difference algebra, the analogous roles play characteristic sets.In this paper, algorithms for computations in differential and difference modules, which allow for the computation of characteristic sets (Gröbner bases) in differential, difference, and polynomial modules and differential (difference) dimension polynomials, are described. The algorithms are implemented in the algorithmic language REFAL.     

Deconvolution and Regularization with Toeplitz Matrices

By deconvolution we mean the solution of a linear first-kind integral equation with a convolution-type kernel, i.e., a kernel that depends only on the difference between the two independent variables. Deconvolution problems are special cases of linear first-kind Fredholm integral equations, whose treatment requires the use of regularization methods. The corresponding computational problem takes the form of structured matrix problem with a Toeplitz or block Toeplitz coefficient matrix. The aim of this paper is to present a tutorial survey of numerical algorithms for the practical treatment of these discretized deconvolution problems, with emphasis on methods that take the special structure of the matrix into account. Wherever possible, analogies to classical DFT-based deconvolution problems are drawn. Among other things, we present direct methods for regularization with Toeplitz matrices, and we show how Toeplitz matrix–vector products are computed by means of FFT, being useful in iterative methods. We also introduce the Kronecker product and show how it is used in the discretization and solution of 2-D deconvolution problems whose variables separate.     

On the computation of the rank of block bidiagonal Toeplitz matrices

In the present paper we study the computation of the rank of a block bidiagonal Toeplitz (BBT) sequence of matrices. We propose matrix-based, numerical and symbolical, updating and direct methods, computing the rank of BBT matrices and comparing them with classical procedures. The methods deploy the special form of the BBT sequence, significantly reducing the required flops and leading to fast and efficient algorithms. The numerical implementation of the algorithms computes the numerical rank in contrast with the symbolical implementation, which guarantees the computation of the exact rank of the matrix. The combination of numerical and symbolical operations suggests a new approach in software mathematical computations denoted as hybrid computations.     

Efficient computation of Fourier transforms on compact groups

This article genralizes the fast Fourier transform algorithm to the computation of Fourier transforms on compact Lie groups. The basic technique uses factorization of group elements and Gel'fand-Tsetlin bases to simplify the computations, and may be extended to treat the computation of Fourier transforms of finitely supported distributions on the group. Similar transforms may be defined on homogeneous spaces; in that case we show how special function properties of spherical functions lead to more efficient algorithms. These results may all be viewed as generalizations of the fast Fourier transform algorithms on the circle, and of recent results about Fourier transforms on finite groups. Acknowledgements and Notes. This paper was written while the author was supported by the Max-Planck-Institut für Mathematik, Bonn, Germany.     

Fast block Toeplitz orthogonalization

Summary Algorithms are presented which compute theQR factorization of a block-Toeplitz matrix inO(n) ² block-operations, wheren is the block-order of the matrix and a block-operation is a multiplication, inversion or a set of Householder operations involving one or two blocks. The algorithms are in general analogous to those presented in the scalar Toeplitz case in a previous paper, but the basic operation is the Householder transform rather than the Givens transform, and the computation of the Householder coefficients and other working matrices requires special treatment. Two algorithms are presented-the first computes onlyR explicitly and the second computes bothQ andR.     

Matrix measures on the unit circle, moment spaces, orthogonal polynomials and the Geronimus relations

We study the moment space corresponding to matrix measures on the unit circle. Moment points are characterized by non-negative definiteness of block Toeplitz matrices. This characterization is used to derive an explicit representation of orthogonal polynomials with respect to matrix measures on the unit circle and to present a geometric definition of canonical moments. It is demonstrated that these geometrically defined quantities coincide with the Verblunsky coefficients, which appear in the Szegö recursions for the matrix orthogonal polynomials. Finally, we provide an alternative proof of the Geronimus relations which is based on a simple relation between canonical moments of matrix measures on the interval [−1, 1] and the Verblunsky coefficients corresponding to matrix measures on the unit circle.