A new algorithm for generalized Sylvester‐observer equation and its application to state and velocity estimations in vibrating systems

We propose a new algorithm for block‐wise solution of the generalized Sylvester‐observer equation XA?FXE = GC, where the matrices A, E, and C are given, the matrices X, F, and G need to be computed, and matrix E may be singular. The algorithm is based on an orthogonal decomposition of the triplet (A, E, C) into the observer‐Hessenberg‐triangular form. It is a natural generalization of the widely known observer‐Hessenberg algorithm for the Sylvester‐observer equation: XA?FX = GC, which arises in state estimation of a standard first‐order state‐space control system. An application of the proposed algorithm is made to state and velocity estimations of second‐order control systems modeling a wide variety of vibrating structures. For dense un‐structured data, the proposed algorithm is more efficient than the recently proposed SVD‐based algorithm of the authors. Copyright © 2010 John Wiley & Sons, Ltd.     

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.     

Numerically stable deflation of hessenberg and symmetric tridiagonal matrices

While numerically stable techniques have been available for deflating a fulln byn matrix, no satisfactory finite technique has been known which preserves Hessenberg form. We describe a new algorithm which explicitly deflates a Hessenberg matrix in floating point arithmetic by means of a sequence of plane rotations. When applied to a symmetric tridiagonal matrix, the deflated matrix is again symmetric tridiagonal. Repeated deflation can be used to find an orthogonal set of eigenvectors associated with any selection of eigenvalues of a symmetric tridiagonal matrix.     

Efficient eigenvalue computation for quasiseparable Hermitian matrices under low rank perturbations

In this paper we address the problem of efficiently computing all the eigenvalues of a large N×N Hermitian matrix modified by a possibly non Hermitian perturbation of low rank. Previously proposed fast adaptations of the QR algorithm are considerably simplified by performing a preliminary transformation of the matrix by similarity into an upper Hessenberg form. The transformed matrix can be specified by a small set of parameters which are easily updated during the QR process. The resulting structured QR iteration can be carried out in linear time using linear memory storage. Moreover, it is proved to be backward stable. Numerical experiments show that the novel algorithm outperforms available implementations of the Hessenberg QR algorithm already for small values of N.      

On orthogonal reduction to Hessenberg form with small bandwidth

Numerous algorithms in numerical linear algebra are based on the reduction of a given matrix A to a more convenient form. One of the most useful types of such reduction is the orthogonal reduction to (upper) Hessenberg form. This reduction can be computed by the Arnoldi algorithm. When A is Hermitian, the resulting upper Hessenberg matrix is tridiagonal, which is a significant computational advantage. In this paper we study necessary and sufficient conditions on A so that the orthogonal Hessenberg reduction yields a Hessenberg matrix with small bandwidth. This includes the orthogonal reduction to tridiagonal form as a special case. Orthogonality here is meant with respect to some given but unspecified inner product. While the main result is already implied by the Faber-Manteuffel theorem on short recurrences for orthogonalizing Krylov sequences (see Liesen and Strakoš, SIAM Rev 50:485–503, 2008), we consider it useful to present a new, less technical proof. Our proof utilizes the idea of a “minimal counterexample”, which is standard in combinatorial optimization, but rarely used in the context of linear algebra. The work of P. Tichy was supported by the Emmy Noether-Program of the Deutsche Forschungsgemeinschaft and by the GAAS grant IAA100300802.     

Non‐recursive solution of sparse block Hessenberg systems

A double‐phase algorithm, based on the block recursive LU decomposition, has been recently proposed to solve block Hessenberg systems with sparsity properties. In the first phase the information related to the factorization of A and required to solve the system, is computed and stored. The solution of the system is then computed in the second phase. In the present paper the algorithm is modified: the two phases are merged into a one‐phase version having the same computational cost and allowing a saving of storage. Moreover, the corresponding non‐recursive version of the new algorithm is presented, which is especially suitable to solve infinite systems where the coefficient matrix dimension is not a priori fixed and a subsequent size enlargement technique is used. A special version of the algorithm, well suited to deal with block Hessenberg matrices having also a block band structure, is presented. Theoretical asymptotic bounds on the computational costs are proved. They indicate that, under suitable sparsity conditions, the proposed algorithms outperform Gaussian elimination. Numerical experiments have been carried out, showing the effectiveness of the algorithms when the size of the system is of practical interest. Copyright © 2004 John Wiley & Sons, Ltd.     

Hessenberg matrix for sums of Hermitian positive definite matrices and weighted shifts

In this work, we introduce an algebraic operation between bounded Hessenberg matrices and we analyze some of its properties. We call this operation m-sum and we obtain an expression for it that involves the Cholesky factorization of the corresponding Hermitian positive definite matrices associated with the Hessenberg components.This work extends a method to obtain the Hessenberg matrix of the sum of measures from the Hessenberg matrices of the individual measures, introduced recently by the authors for subnormal matrices, to matrices which are not necessarily subnormal.Moreover, we give some examples and we obtain the explicit formula for the m-sum of a weighted shift. In particular, we construct an interesting example: a subnormal Hessenberg matrix obtained as the m-sum of two not subnormal Hessenberg matrices.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

Conjugate-normal matrices with conjugate-normal submatrices

In studying the reduction of a complex n × n matrix A to its Hessenberg form by the Arnoldi algorithm, T. Huckle discovered that an irreducible Hessenberg normal matrix with a normal leading principal m × m submatrix, where 1 < m < n, actually is tridiagonal. We prove a similar assertion for the conjugate-normal matrices, which play the same role in the theory of unitary congruences as the conventional normal matrices in the theory of unitary similarities. This fact is stated as a purely matrix-theoretic theorem, without any reference to Arnoldi-like algorithms. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 346, 2007, pp. 21–25.     

Computing powers of arbitrary Hessenberg matrices

An efficient algorithm for the computation of powers of an n × n arbitrary lower Hessenberg matrix is presented. Numerical examples are used to show the computational details. A comparison of the algorithm with two other methods of matrix multiplication proposed by Brent and by Winograd is included. Related algorithms were proposed earlier by Datta and Datta for lower Hessenberg matrices with unit super-diagonal elements, and by Barnett for the companion matrix.     

Efficient and stable solution of structured Hessenberg linear systems arising from difference equations

This paper is concerned with the efficient solution of (block) Hessenberg linear systems whose coefficient matrix is a Toeplitz matrix in (block) Hessenberg form plus a band matrix. Such problems arise, for instance, when we apply a computational scheme based on the use of difference equations for the computation of many significant special functions and quantities occurring in engineering and physics. We present a divide‐and‐conquer algorithm that combines some recent techniques for the numerical treatment of structured Hessenberg linear systems. Our approach is computationally efficient and, moreover, in many practical cases it can be shown to be componentwise stable. Copyright © 2000 John Wiley & Sons, Ltd.     

A note on the solution of not balanced banded Toeplitz systems

A direct algorithm is presented for the solution of linear systems having banded Toeplitz coefficient matrix with unbalanced bandwidths. It is derived from the cyclic reduction algorithm, it makes use of techniques based on the displacement rank and it relies on the Morrison–Sherman–Woodbury formula. The algorithm always equals and sometimes outperforms the already known direct ones in terms of asymptotic computational cost. The case where the coefficient matrix is a block banded block Toeplitz matrix in block Hessenberg form is analyzed as well. The algorithm is numerically stable if applied to M‐matrices that are point diagonally dominant by columns. Copyright © 2007 John Wiley & Sons, Ltd.     

The Drazin Inverse of Hessenberg Matrices

The Drazin inverse of a lower Hessenberg matrix is considered. If $A$ is a singular lower Hessenberg matrix and $a_{i,i+1}=\neq 0,i=1,2,\cdots,n-1$, then $A^D$ can be given, and expressed explicitly by elements of $A$. The structure of the Drazin inverse of a lower Hessenberg matrix is also studied.     

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     

Computation of the quasi-stationary distributions inM(n)/GI/1/K andGI/M(n)/1/K queues

In this paper, we provide numerical means to compute the quasi-stationary (QS) distributions inM/GI/1/K queues with state-dependent arrivals andGI/M/1/K queues with state-dependent services. These queues are described as finite quasi-birth-death processes by approximating the general distributions in terms of phase-type distributions. Then, we reduce the problem of obtaining the QS distribution to determining the Perron-Frobenius eigenvalue of some Hessenberg matrix. Based on these arguments, we develop a numerical algorithm to compute the QS distributions. The doubly-limiting conditional distribution is also obtained by following this approach. Since the results obtained are free of phase-type representations, they are applicable for general distributions. Finally, numerical examples are given to demonstrate the power of our method.     

Implicit QR algorithms for palindromic and even eigenvalue problems

In the spirit of the Hamiltonian QR algorithm and other bidirectional chasing algorithms, a structure-preserving variant of the implicit QR algorithm for palindromic eigenvalue problems is proposed. This new palindromic QR algorithm is strongly backward stable and requires less operations than the standard QZ algorithm, but is restricted to matrix classes where a preliminary reduction to structured Hessenberg form can be performed. By an extension of the implicit Q theorem, the palindromic QR algorithm is shown to be equivalent to a previously developed explicit version. Also, the classical convergence theory for the QR algorithm can be extended to prove local quadratic convergence. We briefly demonstrate how even eigenvalue problems can be addressed by similar techniques. D. S. Watkins partly supported by Deutsche Forschungsgemeinschaft through Matheon, the DFG Research Center Mathematics for key technologies in Berlin.     

Imposing symmetry in augmented linear systems

This paper discusses the methods of imposing symmetry in the augmented system formulation (ASF) for least‐squares (LS) problems. A particular emphasis is on upper Hessenberg problems, where the challenge lies in leaving all zero‐by‐definition elements of the LS matrix unperturbed. Analytical solutions for optimal perturbation matrices are given, including upper Hessenberg matrices. Finally, the upper Hessenberg LS problems represented by unsymmetric ASF that indicate a normwise backward stability of the problem (which is not the case in general) are identified. It is observed that such problems normally arise from Arnoldi factorization (for example, in the generalized minimal residual (GMRES) algorithm). The problem is illustrated with a number of practical (arising in the GMRES algorithm) and some ‘purpose‐built’ examples. Copyright © 2014 John Wiley & Sons, Ltd.     

Properties of Hadamard product of inverse M‐matrices

This paper concerns with the properties of Hadamard product of inverse M‐matrices. Structures of tridiagonal inverse M‐matrices and Hessenberg inverse M‐matrices are analysed. It is proved that the product A ○ A^T satisfies Willoughby's necessary conditions for being an inverse M‐matrix when A is an irreducible inverse M‐matrix. It is also proved that when A is either a Hessenberg inverse M‐matrix or a tridiagonal inverse M‐matrix then A ○ A^T is an inverse M‐matrix. Based on these results, the conjecture that A ○ A^T is an inverse M‐matrix when A is an inverse M‐matrix is made. Unfortunately, the conjecture is not true. Copyright © 2004 John Wiley Sons, Ltd.