An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

On the convergence properties of the orthogonal similarity transformations to tridiagonal and semiseparable (plus diagonal) form

In this paper, we will compare the convergence properties of three basic reduction methods, by placing them in a general framework. It covers the reduction to tridiagonal, semiseparable and semiseparable plus diagonal form. These reductions are often used as the first step in the computation of the eigenvalues and/or eigenvectors of arbitrary matrices. In this way, the calculation of the eigenvalues using, for example, the QR-algorithm reduces in complexity. First we will investigate the convergence properties of these three reduction algorithms. It will be shown that for the partially reduced matrices at step k of any of these reduction algorithms, the lower right k × k (already reduced) sub-block will have the Lanczos–Ritz values, w.r.t. a certain starting vector. It will also be shown that the reductions to semiseparable and to semiseparable plus diagonal form have an extra convergence behavior a special type of subspace iteration is performed on the lower right k × k submatrix, which contains these Ritz-values. Secondly we look in more detail at the behavior of the involved subspace iteration. It will be shown that the reduction method can be interpreted as a nested type of multi-shift iteration. Theoretical results will be presented, making it possible to predict the convergence behavior of these reduction algorithms. Also a theoretical bound on the convergence rate is presented. Finally we illustrate by means of numerical examples, how it is possible to tune the convergence behavior such that it can become a powerful tool for certain applications.     

Orthogonal similarity transformation of a symmetric matrix into a diagonal-plus-semiseparable one with free choice of the diagonal

In this paper we describe an orthogonal similarity transformation for transforming arbitrary symmetric matrices into a diagonal-plus-semiseparable matrix, where we can freely choose the diagonal. Very recently an algorithm was proposed for transforming arbitrary symmetric matrices into similar semiseparable ones. This reduction is strongly connected to the reduction to tridiagonal form. The class of semiseparable matrices can be considered as a subclass of the diagonalplus- semiseparable matrices. Therefore we can interpret the proposed algorithm here as an extension of the reduction to semiseparable form. A numerical experiment is performed comparing thereby the accuracy of this reduction algorithm with respect to the accuracy of the traditional reduction to tridiagonal form, and the reduction to semiseparable form. The experiment indicates that all three reduction algorithms are equally accurate. Moreover it is shown in the experiments that asymptotically all the three approaches have the same complexity, i.e. that they have the same factor preceding the n³ term in the computational complexity. Finally we illustrate that special choices of the diagonal create a specific convergence behavior. The research was partially supported by the Research Council K.U.Leuven, project OT/05/40 (Large rank structured matrix computations), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors.     

A small note on the scaling of symmetric positive definite semiseparable matrices

In this paper we will adapt a known method for diagonal scaling of symmetric positive definite tridiagonal matrices towards the semiseparable case. Based on the fact that a symmetric, positive definite tridiagonal matrix satisfies property A, one can easily construct a diagonal matrix such that has the lowest condition number over all matrices , for any choice of diagonal matrix . Knowing that semiseparable matrices are the inverses of tridiagonal matrices, one can derive similar properties for semiseparable matrices. Here, we will construct the optimal diagonal scaling of a semiseparable matrix, based on a new inversion formula for semiseparable matrices. Some numerical experiments are performed. In a first experiment we compare the condition numbers of the semiseparable matrices before and after the scaling. In a second numerical experiment we compare the scalability of matrices coming from the reduction to semiseparable form and matrices coming from the reduction to tridiagonal form. *The research was partially supported by the Research Council K.U. Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann–Hilbert problems, random matrices and Padé–Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister's Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The scientific responsibility rests with the authors. The second author participates in the SCCM program, Gates 2B, Stanford University, CA, USA and is also partially supported by the NSF. The first author visited the second one with a grant by the Fund for Scientific Research–Flanders (Belgium).     

Fast inversion algorithms for diagonal plus semiseparable matrices

Here are considered matrices represented as a sum of diagonal and semiseparable ones. These matrices belong to the class of structured matrices which arises in numerous applications. FastO(N) algorithms for their inversion were developed before under additional restrictions which are a source of instability. Our aim is to eliminate these restrictions and to develop reliable and stable numerical algorithms. In this paper we obtain such algorithms with the only requirement that the considered matrix is invertible and its determinant is not close to zero. The case of semiseparable matrices of order one was considered in detail in an earlier paper of the authors.     

基于反Krylov矩阵正交分解的半可分矩阵

在本文中，我们证明了对一个反Krylov矩阵作QR分解后，利用得到的正交矩阵可以将一个具有互异特征值的对称矩阵转化为一个半可分矩阵的形式，这个结果表明了反Krylov矩阵与半可分矩阵之间的联系．另外，我们还证明了这类对称半可分矩阵在QR达代下矩阵结构保持不变性．     

Using semiseparable matrices to compute the SVD of a general matrix product/quotient

In this work we reduce the computation of the singular values of a general product/quotient of matrices to the computation of the singular values of an upper triangular semiseparable matrix. Compared to the reduction into a bidiagonal matrix the reduction into semiseparable form exhibits a nested subspace iteration. Hence, when there are large gaps between the singular values, these gaps manifest themselves already during the reduction algorithm in contrast to the bidiagonal case.     

A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

REPRINT OF: A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

Kronecker's canonical form and the QZ algorithm

This paper examines the behavior of the QZ algorithm which is to be expected when A?λB is close to a singular pencil. The predicted results are fully confirmed by practical experience of using the QZ algorithm on examples of this kind.     

A Lanczos‐type algorithm for the QR factorization of regular Cauchy matrices

We present a fast algorithm for computing the QR factorization of Cauchy matrices with real nodes. The algorithm works for almost any input matrix, does not require squaring the matrix, and fully exploits the displacement structure of Cauchy matrices. We prove that, if the determinant of a certain semiseparable matrix is non‐zero, a three term recurrence relation among the rows or columns of the factors exists. Copyright © 2002 John Wiley & Sons, Ltd.     

Fast algorithms for hierarchically semiseparable matrices

Semiseparable matrices and many other rank‐structured matrices have been widely used in developing new fast matrix algorithms. In this paper, we generalize the hierarchically semiseparable (HSS) matrix representations and propose some fast algorithms for HSS matrices. We represent HSS matrices in terms of general binary HSS trees and use simplified postordering notation for HSS forms. Fast HSS algorithms including new HSS structure generation and HSS form Cholesky factorization are developed. Moreover, we provide a new linear complexity explicit ULV factorization algorithm for symmetric positive definite HSS matrices with a low‐rank property. The corresponding factors can be used to solve the HSS systems also in linear complexity. Numerical examples demonstrate the efficiency of the algorithms. All these algorithms have nice data locality. They are useful in developing fast‐structured numerical methods for large discretized PDEs (such as elliptic equations), integral equations, eigenvalue problems, etc. Some applications are shown. Copyright © 2009 John Wiley & Sons, Ltd.     

On single and double Soules matrices

Until now the concept of a Soules basis matrix of sign patternN consisted of an orthogonal matrix R∈R^n,n, generated in a certain way from a positive n-vector, which has the property that for any diagonal matrix Λ = diag(λ₁, … , λ_n), with λ₁ ? ? ? λ_n ? 0, the symmetric matrix A = RΛR^T has nonnegative entries only. In the present paper we introduce the notion of a pair of double Soules basis matrices of sign patternN which is a pair of matrices (P, Q), each in R^n,n, which are not necessarily orthogonal and which are generated in a certain way from two positive vectors, but such that PQ^T = I and such that for any of the aforementioned diagonal matrices Λ, the matrix A = PΛQ^T (also) has nonnegative entries only. We investigate the interesting properties which such matrices A have.As a preamble to the above investigation we show that the iterates, , generated in the course of the QR-algorithm when it is applied to A = RΛR^T, where R is a Soules basis matrix of sign pattern N, are again symmetric matrices generated by the Soules basis matrices R_k of sign pattern N which are themselves modified as the algorithm progresses.Our work here extends earlier works by Soules and Elsner et al.     

On the Unitary Similarity of Matrix Families

The classical Specht criterion for the unitary similarity between two complex n × n matrices is extended to the unitary similarity between two normal matrix sets of cardinality m. This property means that the algebra generated by a set is closed with respect to the conjugate transpose operation. Similar to the well-known result of Pearcy that supplements Specht's theorem, the proposed extension can be made a finite criterion. The complexity of this criterion depends on n as well as the length l of the algebras under analysis. For a pair of matrices, this complexity can be significantly lower than that of the Specht--Pearcy criterion.     

An Implicit Q Theorem for Hessenberg-like Matrices

The implicit Q theorem for Hessenberg matrices is a widespread and powerful theorem. It is used in the development of, for example, implicit QR algorithms to compute the eigendecomposition of Hessenberg matrices. Moreover it can also be used to prove the essential uniqueness of orthogonal similarity transformations of matrices to Hessenberg form. The theorem is also valid for symmetric tridiagonal matrices, proving thereby also in the symmetric case its power. Currently there is a growing interest to so-called semiseparable matrices. These matrices can be considered as the inverses of tridiagonal matrices. In a similar way, one can consider Hessenberg-like matrices as the inverses of Hessenberg matrices. In this paper, we formulate and prove an implicit Q theorem for the class of Hessenberg-like matrices. We introduce the notion of strongly unreduced Hessenberg-like matrices and also a method for transforming matrices via orthogonal transformations to this form is proposed. Moreover, as the theorem is valid for Hessenberg-like matrices it is also valid for symmetric semiseparable matrices. The research was partially supported by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister’s Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). This research was partially supported by by MIUR, grant number 2004015437 (third author). The scientific responsibility rests with the authors.     

Orthogonal similarity transformation into block‐semiseparable matrices of semiseparability rank k

Very recently, an algorithm, which reduces any symmetric matrix into a semiseparable one of semi‐ separability rank 1 by similar orthogonality transformations, has been proposed by Vandebril, Van Barel and Mastronardi. Partial execution of this algorithm computes a semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the Lanczos' process applied to the original matrix. Also a kind of nested subspace iteration is performed at each step. In this paper, we generalize the above results and propose an algorithm to reduce any symmetric matrix into a similar block‐semiseparable one of semiseparability rank k, with k ∈ ?, by orthogonal similarity transformations. Also in this case partial execution of the algorithm computes a block‐semiseparable matrix whose eigenvalues are the Ritz‐values obtained by the block‐Lanczos' process with k starting vectors, applied to the original matrix. Subspace iteration is performed at each step as well. Copyright © 2005 John Wiley & Sons, Ltd.     

Bounds on the kth multi-g base index of nearly reducible sign pattern matrices

Li et al. [On the period and base of a sign pattern matrix, Linear Algebra Appl. 212/213 (1994) 101-120.] extended the concepts of the base and period from nonnegative matrices to powerful sign pattern matrices. Then, Shao and You [Bound on the basis of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285-300.] extended the concepts of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. In this paper we mainly study the kth multi-g base index for non-powerful primitive nearly reducible sign pattern matrices. We obtain sharp upper bounds, together with a complete characterization of the equality cases of the kth multi-g base index for primitive nearly reducible generalized sign pattern matrices. We also show that there exist “gaps” in the kth multi-g base index set of the classes of such matrices.     

On the minimal number of matrices which form a locally hypercyclic, non-hypercyclic tuple

In this paper we extend the notion of a locally hypercyclic operator to that of a locally hypercyclic tuple of operators. We then show that the class of hypercyclic tuples of operators forms a proper subclass to that of locally hypercyclic tuples of operators. What is rather remarkable is that in every finite dimensional vector space over R or C, a pair of commuting matrices exists which forms a locally hypercyclic, non-hypercyclic tuple. This comes in direct contrast to the case of hypercyclic tuples where the minimal number of matrices required for hypercyclicity is related to the dimension of the vector space. In this direction we prove that the minimal number of diagonal matrices required to form a hypercyclic tuple on Rn is n+1, thus complementing a recent result due to Feldman.     

The generalized singular value decomposition and the general (A-λB)-problem

In the study of the canonical structure of matrix pencilsA-B, the column and row nullities ofA andB and the possible common nullspaces give information about the Kronecker structure ofA-B. It is shown how to extract the significant information concerning these nullspaces from the generalized singular value decomposition (GSVD) of the matrix pair (A, B), These properties are the basis for the RGSVD-algorithm that will be published elsewhere [9]. An algorithm for the numerical computation of the transformation matrices (V, X), used in an equivalence transformationV ^H (A-B)X, is presented and discussed. A generalizedQZ-decomposition (GQZD) of a matrix pair (A, B) is also formulated, giving a unitary equivalent transformationV ^H (A-B)Q. If during the computationsX gets too illconditioned we switch to the GQZD, sacrificing a simple diagonal structure of the transformedB-part in order to maintain stability.Dedicated to Germund Dahlquist, on the occasion of his 60th birthday.     

A <Emphasis Type="Italic">QR</Emphasis>–method for computing the singular values via semiseparable matrices

Summary. The standard procedure to compute the singular value decomposition of a dense matrix, first reduces it into a bidiagonal one by means of orthogonal transformations. Once the bidiagonal matrix has been computed, the QR–method is applied to reduce the latter matrix into a diagonal one. In this paper we propose a new method for computing the singular value decomposition of a real matrix. In a first phase, an algorithm for reducing the matrix A into an upper triangular semiseparable matrix by means of orthogonal transformations is described. A remarkable feature of this phase is that, depending on the distribution of the singular values, after few steps of the reduction, the largest singular values are already computed with a precision depending on the gaps between the singular values. An implicit QR–method for upper triangular semiseparable matrices is derived and applied to the latter matrix for computing its singular values. The numerical tests show that the proposed method can compete with the standard method (using an intermediate bidiagonal matrix) for computing the singular values of a matrix.Mathematics Subject Classification (2000): 65F15, 15A18The research of the first two authors was partially supported by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Ministers Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). The work of the third author was partially supported by MIUR, grant number 2002014121. The scientific responsibility rests with the authors.Acknowledgments.We thank the referees for their suggestions which increased the readability of the paper.