A block bidiangonal form for block companion matrices

The problem of the linear factorization of a polynomial matrix is related with a similarity condition linking the block companion matrix and a block upper bidiagonal matrix constructed from a chain of solvents. This result is the applied to the solution of differential and difference linear matrix equations.     

A block algorithm for computing antitriangular factorizations of symmetric matrices

Any symmetric matrix can be reduced to antitriangular form in finitely many steps by orthogonal similarity transformations. This form reveals the inertia of the matrix and has found applications in, e.g., model predictive control and constraint preconditioning. Originally proposed by Mastronardi and Van Dooren, the existing algorithm for performing the reduction to antitriangular form is primarily based on Householder reflectors and Givens rotations. The poor memory access pattern of these operations implies that the performance of the algorithm is bound by the memory bandwidth. In this work, we develop a block algorithm that performs all operations almost entirely in terms of level 3 BLAS operations, which feature a more favorable memory access pattern and lead to better performance. These performance gains are confirmed by numerical experiments that cover a wide range of different inertia.     

Equilibrium problem for the eigenvalues of banded block Toeplitz matrices

We consider banded block Toeplitz matrices T_n with n block rows and columns. We show that under certain technical assumptions, the normalized eigenvalue counting measure of T_n for n → ∞ weakly converges to one component of the unique vector of measures that minimizes a certain energy functional. In this way we generalize a recent result of Duits and Kuijlaars for the scalar case. Along the way we also obtain an equilibrium problem associated to an arbitrary algebraic curve, not necessarily related to a block Toeplitz matrix. For banded block Toeplitz matrices, there are several new phenomena that do not occur in the scalar case: (i) The total masses of the equilibrium measures do not necessarily form a simple arithmetic series but in general are obtained through a combinatorial rule; (ii) The limiting eigenvalue distribution may contain point masses, and there may be attracting point sources in the equilibrium problem; (iii) More seriously, there are examples where the connection between the limiting eigenvalue distribution of T_n and the solution to the equilibrium problem breaks down. We provide sufficient conditions guaranteeing that no such breakdown occurs; in particular we show this if T_n is a Hessenberg matrix.     

Bounds for eigenvalues of symmetric block Jacobi scaled matrices

The paper presents upper bounds for the largest eigenvalue of a block Jacobi scaled symmetric positive-definite matrix which depend only on such parameters as the block semibandwidth of a matrix and its block size. From these bounds we also derive upper bounds for the smallest eigenvalue of a symmetric matrix with identity diagonal blocks. Bibliography: 4 titles. Translated by L. Yu. Kolotilina. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 18–25.     

An analysis of the HR algorithm for computing the eigenvalues of a matrix

The HR algorithm, a method of computing the eigenvalues of a matrix, is presented. It is based on the fact that almost every complex square matrix A can be decomposed into a product A = HR of a so-called pseudo-Hermitian matrix H and an upper triangular matrix R. This algorithm is easily seen to be a generalization of the well-known QR algorithm. It is shown how it is related to the power method and inverse iteration, and for special matrices the connection between the LR and HR algorithms is indicated.     

A fast implicit QR eigenvalue algorithm for companion matrices

An implicit version of the shifted QR eigenvalue algorithm given in Bini et al. [D.A. Bini, Y. Eidelman, I. Gohberg, L. Gemignani, SIAM J. Matrix Anal. Appl. 29(2) (2007) 566-585] is presented for computing the eigenvalues of an n×n companion matrix using O(n²) flops and O(n) memory storage. Numerical experiments and comparisons confirm the effectiveness and the stability of the proposed method.     

A norm-reducing Jacobi-like algorithm for the eigenvalues of non-normal matrices

A new norm decreasing Jacobi-like method for reducing a non-normal matrix to a normal one is described. The method is an improved version of the Huang-Gregory's procedure [6], in which certain norm reducing non-optimal steps are replaced by the optimal ones, which correspond no more to regular matrix transformations. The method renders itself particularly effective in dealing with defective matrices of special forms. Theory and experiments alike indicate that this algorithm is in all computational aspects — accuracy, convergence rate, computing time, complexity of the computer program — better or at least as good as the original one.Both procedures, the original and the improved one, end in all of the authors computed examples with the diagonal matrix containing the eigenvalues of the non-normal initial matrix.     

Fast computation of eigenvalues of companion,comrade, and related matrices

The class of eigenvalue problems for upper Hessenberg matrices of banded-plus-spike form includes companion and comrade matrices as special cases. For this class of matrices a factored form is developed in which the matrix is represented as a product of essentially 2×2 matrices and a banded upper-triangular matrix. A non-unitary analogue of Francis’s implicitly-shifted QR algorithm that preserves the factored form and consequently computes the eigenvalues in O(n ²) time and O(n) space is developed. Inexpensive a posteriori tests for stability and accuracy are performed as part of the algorithm. The results of numerical experiments are mixed but promising in certain areas. The single-shift version of the code applied to companion matrices is much faster than the nearest competitor.     

A modified Leverrier-Faddeev algorithm for matrices with multiple eigenvalues

The Leverrier algorithm as modified by Faddeev gives the characteristic equation of a matrix A, its inverse, and the eigenvector corresponding to a simple eigenvalue λ of A. These results are extended (1) to give a generalized inverse when A is not of full rank and (2) to examine the modification required when λ is a multiple eigenvalue.     

A fast algorithm for computing the pseudospectra of Toeplitz matrices

The concept of pseudospectra was introduced by Trefethen during the 1990s and became a popular tool to explain the behavior of non-normal matrices. In this paper, we propose a fast algorithm for computing the pseudospectra of Toeplitz matrices by using fast Toeplitz QR factorization. Numerical experiments are given to illustrate the efficiency of the new algorithm.     

On the extreme eigenvalues of hermitian (block) toeplitz matrices

We are concerned with the behavior of the minimum (maximum) eigenvalue λ₀⁽ⁿ⁾ (λ_n⁽ⁿ⁾) of an (n + 1) × (n + 1) Hermitian Toeplitz matrix T_n(ƒ) where ƒ is an integrable real-valued function. Kac, Murdoch, and Szegö, Widom, Parter, and R. H. Chan obtained that λ₀⁽ⁿ⁾ — min ƒ = O(1/n^2k) in the case where ƒ C^2k, at least locally, and ƒ — inf ƒ has a zero of order 2k. We obtain the same result under the second hypothesis alone. Moreover we develop a new tool in order to estimate the extreme eigenvalues of the mentioned matrices, proving that the rate of convergence of λ₀⁽ⁿ⁾ to inf ƒ depends only on the order ρ (not necessarily even or integer or finite) of the zero of ƒ — inf ƒ. With the help of this tool, we derive an absolute lower bound for the minimal eigenvalues of Toeplitz matrices generated by nonnegative L¹ functions and also an upper bound for the associated Euclidean condition numbers. Finally, these results are extended to the case of Hermitian block Toeplitz matrices with Toeplitz blocks generated by a bivariate integrable function ƒ.     

On relative perturbation theory for eigenvalues and eigenvectors of block operator matrices

We are concerned with singularly perturbed spectral problems which appear in engineering sciences. Typically under the influence of a singular perturbation the model can be approximated by a simpler, perturbation independent model. Such reduced model is usually better amenable to analytic or numeric analysis. However, the question of the quality of approximation has to be answered. Frequently, correctors which yield an improved solution–capturing important phenomena which the reduced model does not “see”–to the original problems are required. We tackle both question for self-adjoint eigenvalue/eigenvector problems posed in a general Hilbert space. Our technique is constructive and is based on methods (relative perturbation theory) of modern Numerical Linear Algebra. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Generalized qd algorithm for block band matrices

The generalized qd algorithm for block band matrices is an extension of the block qd algorithm applied to a block tridiagonal matrix. This algorithm is applied to a positive definite symmetric block band matrix. The result concerning the behavior of the eigenvalues of the first and the last diagonal block of the matrix containing the entries q ^(k) which was obtained in the tridiagonal case is still valid for positive definite symmetric block band matrices. The eigenvalues of the first block constitute strictly increasing sequences and those of the last block constitute strictly decreasing sequences. The theorem of convergence, given in Draux and Sadik (Appl Numer Math 60:1300?C1308, 2010), also remains valid in this more general case.     

A breakdown-free algorithm for computing the determinants of periodic tridiagonal matrices

Numerical Algorithms - In this paper, we present a new breakdown-free recursive algorithm for computing the determinants of periodic tridiagonal matrices via a three-term recurrence. Even though...     

An approach for computing eigenvalues of discrete symplectic boundary-value problems

We propose a new method for calculating eigenvalues of discrete symplectic boundaryvalue problems. This method is based on the discrete oscillation theory and on a modification of the Abramov double sweep method for discrete self-adjoint boundary-value problems.     

A block algorithm for computing rank-revealing QR factorizations

We present a block algorithm for computing rank-revealing QR factorizations (RRQR factorizations) of rank-deficient matrices. The algorithm is a block generalization of the RRQR-algorithm of Foster and Chan. While the unblocked algorithm reveals the rank by peeling off small singular values one by one, our algorithm identifies groups of small singular values. In our block algorithm, we use incremental condition estimation to compute approximations to the nullvectors of the matrix. By applying another (in essence also rank-revealing) orthogonal factorization to the nullspace matrix thus created, we can then generate triangular blocks with small norm in the lower right part ofR. This scheme is applied in an iterative fashion until the rank has been revealed in the (updated) QR factorization. We show that the algorithm produces the correct solution, under very weak assumptions for the orthogonal factorization used for the nullspace matrix. We then discuss issues concerning an efficient implementation of the algorithm and present some numerical experiments. Our experiments show that the block algorithm is reliable and successfully captures several small singular values, in particular in the initial block steps. Our experiments confirm the reliability of our algorithm and show that the block algorithm greatly reduces the number of triangular solves and increases the computational granularity of the RRQR computation.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38. The second author was also sponsored by a travel grant from the Knud Højgaards Fond.This work was partially completed while the author was visiting the IBM Scientific Center in Heidelberg, Germany.     

An efficient method for computing the inverse of arrowhead matrices

In this paper we propose a simple and effective method to find the inverse of arrowhead matrices which often appear in wide areas of applied science and engineering such as wireless communications systems, molecular physics, oscillators vibrationally coupled with Fermi liquid, and eigenvalue problems. A modified Sherman–Morrison inverse matrix method is proposed for computing the inverse of an arrowhead matrix. The effectiveness of the proposed method is illustrated and numerical results are presented along with comparative results.