On some classes of structured matrices with algebraic trigonometric eigenvalues

Diagonal plus semiseparable matrices are constructed, the eigenvalues of which are algebraic numbers expressed by simple closed trigonometric formulas.     

Rounding Error Analysis in Solving M-Matrix Linear Systems of Block Hessenberg Form

The problem of solving large M-matrix linear systems with sparse coefficient matrix in block Hessenberg form is here addressed. In previous work of the authors a divide-and-conquer strategy was proposed and a backward error analysis of the resulting algorithm was presented showing its effectiveness for the solution of computational problems of queueing theory and Markov chains. In particular, it was shown that for block Hessenberg M-matrices the algorithm is weakly backward stable in the sense that the computed solution is the exact solution of a nearby linear system, where the norm of the perturbation is proportional to the condition number of the coefficient matrix. In this note a better error estimate is given by showing that for block Hessenberg M-matrices the algorithm is even backward stable.     

Chebyshev rational interpolation

The Lanczos method and its variants can be used to solve efficiently the rational interpolation problem. In this paper we present a suitable fast modification of a general look-ahead version of the Lanczos process in order to deal with polynomials expressed in the Chebyshev orthogonal basis. The proposed approach is particularly suited for approximating analytic functions by means of rational interpolation at certain nodes located on the boundary of an elliptical region of the complex plane. In fact, in this case it overcomes some of the numerical difficulties which limited the applicability of the look-ahead Lanczos process for determining the coefficients both of the numerators and of the denominators with respect to the standard power basis. This revised version was published online in August 2006 with corrections to the Cover Date.     

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     

Implicit QR for rank-structured matrix pencils

A fast implicit QR algorithm for eigenvalue computation of low rank corrections of Hermitian matrices is adjusted to work with matrix pencils arising from zerofinding problems for polynomials expressed in Chebyshev-like bases. The modified QZ algorithm computes the generalized eigenvalues of certain $N\times N$ rank structured matrix pencils using $O(N^2)$ flops and $O(N)$ memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

From approximating to interpolatory non-stationary subdivision schemes with the same generation properties

In this paper we describe a general, computationally feasible strategy to deduce a family of interpolatory non-stationary subdivision schemes from a symmetric non-stationary, non-interpolatory one satisfying quite mild assumptions. To achieve this result we extend our previous work (Conti et al., Linear Algebra Appl 431(10):1971?C1987, 2009) to full generality by removing additional assumptions on the input symbols. For the so obtained interpolatory schemes we prove that they are capable of reproducing the same space of exponential polynomials as the one generated by the original approximating scheme. Moreover, we specialize the computational methods for the case of symbols obtained by shifted non-stationary affine combinations of exponential B-splines, that are at the basis of most non-stationary subdivision schemes. In this case we find that the associated family of interpolatory symbols can be determined to satisfy a suitable set of generalized interpolating conditions at the set of the zeros (with reversed signs) of the input symbol. Finally, we discuss some computational examples by showing that the proposed approach can yield novel smooth non-stationary interpolatory subdivision schemes possessing very interesting reproduction properties.     

Direct and Inverse Eigenvalue Problems for Diagonal-Plus-Semiseparable Matrices

In this paper we study both direct and inverse eigenvalue problems for diagonal-plus-semiseparable (dpss) matrices. In particular, we show that the computation of the eigenvalues of a symmetric dpss matrix can be reduced by a congruence transformation to solving a generalized symmetric definite tridiagonal eigenproblem. Using this reduction, we devise a set of recurrence relations for evaluating the characteristic polynomial of a dpss matrix in a stable way at a linear time. This in turn allows us to apply divide-and-conquer eigenvalue solvers based on functional iterations directly to dpss matrices without performing any preliminary reduction into a tridiagonal form. In the second part of the paper, we exploit the structural properties of dpss matrices to solve the inverse eigenvalue problem of reconstructing a symmetric dpss matrix from its spectrum and some other informations. Finally, applications of our results to the computation of a QR factorization of a Cauchy matrix with real nodes are provided.