qd-TYPE METHODS FOR QUASISEPARABLE MATRICES* ROBERTO BEVILACQUA†, ENRICO BOZZO‡,ANDGIANNA M. DEL CORSO†
Abstract. In the last few years many numerical techniques for computing eigenvalues of structured rank matrices have been proposed. Most of them are based on QR iterations since, in the symmetric case, the rank structure is preserved and high accuracy is guaranteed. In the unsymmetric case, however, the QR algorithm destroys the rank structure, which is instead preserved if LR iterations are used. We consider a wide class of quasiseparable matrices which can be represented in terms of the same parameters involved in their Neville factorization. This class, if assumptions are made to prevent possible breakdowns, is closed under LR steps. Moreover, we propose an implicit shifted LR method with a linear cost per step, which resembles the qd method for tridiagonal matrices. We show that for totally nonnegative quasiseparable matrices the algorithm is stable and breakdowns cannot occur if the Laguerre shift, or other shift strategy preserving nonnegativity, is used. Computational evidence shows that good accuracy is obtained also when applied to symmetric positive definite matrices.
Key words. qd algorithms, LR for eigenvalues, quasiseparable matrices AMS subject classification. 65F15
DOI. 10.1137/100794481
1. Introduction. In the recent literature quasiseparable matrices have received a great deal of interest (see [8], [9], [4], and references therein). In fact, matrices with this structure appear naturally in many application fields such as systems theory, signal pro-cessing, or integral equations. Also covariance matrices, or matrices involved in multi-variate statistics or discretization of elliptic PDEs, often have the quasiseparable structure.
The class of quasiseparable matrices includes many important matrices such as com-panion matrices of polynomials, tridiagonal matrices and their inverses (Green’s qua-siseparable), unitary Hessenberg matrices, and banded matrices. In [8] the class is proved to be closed under inversion, and a linear complexity inversion method is proposed.
An interesting research topic is the development of fast algorithms, both for the solution of linear systems and for eigenvalue and eigenvector computations, taking ad-vantage of the representation of the matrix in terms of a small number of parameters. The main purpose of this paper is to propose an LR scheme for eigenvalue compu-tations of a quasiseparable matrix not necessarily Hermitian. In fact, for unsymmetric quasiseparable matrices, it is well known that the QR algorithm destroys the rank struc-ture with an increase of the cost of the computation of the eigenvalues. The LR algo-rithm, on the contrary, maintains the rank structure providing a valid alternative once the stability is guaranteed. The main objection to the use of LR iterations is the possible instability. However, Fernando and Parlett [10] and Parlett in [17] suggested applying the LR algorithm to symmetric positive definite tridiagonal matrices, showing the good
*Received by the editors May 7, 2010; accepted for publication (in revised form) by M. Van Barel April 19, 2011; published electronically DATE. This research was partially supported by the Italian Ministry for Education, University and Scientific Research under program PRIN 2008: 20083KLJEZ.
http://www.siam.org/journals/simax/x-x/79448.html
†Department of Computer Science, Università di Pisa, Largo Pontecorvo, 3, 56127 Pisa, Italy (bevilacq@di. unipi.it, delcorso@di.unipi.it).
‡Department of Mathematics and Computer Science, Università di Udine, Via delle Scienze, 206, 33100 Udine, Italy (enrico.bozzo@uniud.it).
performance and stability of the qd-type methods over the standard QR method. The idea behind qd-type algorithms, first proposed by Rutishauser [20], is to represent tridiagonal matrices as the product of the bidiagonal factors of the LU fac-torization and to update the bidiagonal factors with formulas requiring only quotients and sums. The algorithm is highly accurate and has become one of LAPACK’s main tools for computing eigenvalues of symmetric tridiagonal matrices. Since many interest-ing algorithms for semiseparable and quasiseparable matrices have been derived from similar techniques employed on tridiagonal matrices (see, for example [16], [19], [23]), our idea is to design an algorithm inspired by the qd-type algorithms. While these algo-rithms for tridiagonals perform well on symmetric positive definite matrices, it turns out that the methods we propose in this paper achieve a high accuracy and stability when applied to totally nonnegative (TN) quasiseparable matrices.
The association between TN and quasiseparable matrices was recently made by Do-pico, Bella, and Olshevsky in two different talks [6], [7] and by Gemignani in [14]. They presented necessary and sufficient conditions to verify if a quasiseparable matrix is TN, and they proposed fast and stable algorithms for the solution of linear systems. In [14] the more general case of order-r semiseparable matrices has been exploited.
A historical example of a TN and quasiseparable matrix is the discrete Green func-tion for a string with both ends fastened [11].
For TN matrices, we are able to prove that the algorithms here proposed for the computation of the eigenvalues are subtraction-free and turn out to be very effective when combined with the Laguerre shift strategy. The formulation of the algorithms in terms of recurrences, where some intermediate variables are introduced to avoid pos-sible cancellations, makes these methods similar to the qd-type algorithms for tridiago-nal matrices. For quasiseparable, TN matrices Gemignani in [14], following an idea of Koev [15], sketched an algorithm for the reduction into a similar tridiagonal form. We extend this algorithm for the matrices that we call Neville-representable (see section 3), showing the effectiveness when associated with a qd scheme.
The paper is organized as follows. In section 2 some preliminary definitions and results are provided. In section 3 the class of Neville-representable quasiseparable ma-trices is introduced, and structural results for the L and R factors of the LU factorization of matrices in this class are given. A complete characterization of the class of the Neville-representable quasiseparable matrices is given in terms of the generators of the quasi-separable matrix. Section 4 contains a description of the shifted LR iterations and the-oretical results about the preservation of the structure. The study of the numerical stability and of the computational cost of the proposed methods is addressed in section 5. In section 6, as an alternative for the computation of the eigenvalue, we show a tridia-gonalization procedure that can be followed by qd-type iterations as well as any other eigensolver for unsymmetric tridiagonal matrices. Section 7 contains the numerical ex-periments. In particular, we tested our methods on both random unsymmetric matrices and TN matrices. The results show a good performance in terms of time required and accuracy achieved, also for matrices not TN. A comparison for symmetric matrices with EIGSSDroutine1—implementing implicit QR steps—is performed, showing the better
behavior of our methods still achieving a comparable accuracy.
2. Preliminary results. In this section we present some preliminary results that will be useful in the remaining parts of the paper.
1
EIGSSD is a function included in the MATLAB package SSPACK, accompanying the book [25], and it is available online athttp://www.cs.kuleuven.be/~mase/.
In the paper we will use the MATLAB-like notation to denote the lower (upper) triangular part of a matrix. In particular, trilðA; kÞ denotes the lower triangular part of the matrix A below and including the kth diagonal, that is, trilðA; kÞ ¼ faijjj−
i≤ kg, and triuðA; kÞ denotes the upper triangular part of the matrix A above and in-cluding the kth diagonal, that is, triuðA; kÞ ¼ faijjj − i ≥ kg. Note that the index k in
these definitions can also be negative; hence k¼ 0 is the main diagonal, k > 0 is above the main diagonal, and k < 0 is below the main diagonal. Similarly diagðv; kÞ denotes the matrix with the elements of vector v on the kth diagonal. We denote by vi∶jthe partial
product of the entries of vector v, from index i to index j, that is, vi∶j¼ viviþ1 · · · vj,
where i≤ j.
DEFINITION1. An n× n matrix S is called a semiseparable matrix if the following
properties are satisfied:
rank Sði∶n; 1∶iÞ ≤ 1; rank Sð1∶i; i∶nÞ ≤ 1 for i ¼ 1; : : : ; n − 1:
All semiseparable matrices S¼ ðsijÞ can be represented by using six vectors u, v, t,
p, q, and r in this way (see Definition 2.14 in [24]):
sij¼ 8 < : uiti−1∶jvj; 1≤ j < i ≤ n; uivi¼ piqi; 1≤ j ¼ i ≤ n; piri∶j−1qj; 1≤ i < j ≤ n: ð2:1Þ
DEFINITION2. A matrix S is called a generator-representable semiseparable matrix if
there exist four vectors u, v, p, and q such that
sij¼ 8 < : uivj; 1≤ j < i ≤ n; uivi¼ piqi; 1≤ j ¼ i ≤ n; piqj; 1≤ i < j ≤ n: ð2:2Þ
In the case S is irreducible, t and r in (2.1)can be chosen as unit vectors, and S is then generator-representable. If some ti or ri is zero, S is reducible. However, if S is
reducible but symmetric or triangular, then it can always be expressed as the direct sum of two or more generator-representable matrices. See [2] for the details.
The class of matrices that can be represented as the sum of a semiseparable and a diagonal matrix is called the class of the semiseparable plus diagonal matrices.
In this paper a generalization of the semiseparable plus diagonal matrices is con-sidered, that is, the class of quasiseparable matrices introduced in [8], [21].
There are many definitions of quasiseparable matrices [24]. The most general is the following.
DEFINITION3. An n× n matrix S is called a quasiseparable matrix if the following
conditions are satisfied:
rank Sði þ 1∶n; 1∶iÞ ≤ 1; rank Sð1∶i; i þ 1∶nÞ ≤ 1 for i ¼ 1; : : : ; n − 1: This definition captures semiseparable matrices, tridiagonal matrices, and semise-parable plus diagonal matrices. Note that singular matrices as well as block diagonal matrices are included in the class, while this does not happen if other definitions are chosen.
A very convenient way to represent quasiseparable matrices is the one introduced in [5], [8]. The Givens-vector representation as well as the generator representation can both be considered as special cases of this quasiseparable representation [24].
An unsymmetric quasiseparable matrix A can be expressed by means of 7n− 8 para-meters, as follows: A¼ 0 B B B B B B B B B B @ δ1 q2p1 q3r2p1 q4r3∶2p1 · · · qnrn−1∶2p1 u2v1 δ2 q3p2 q4r3p2 · · · qnrn−1∶3p2 u3t2v1 u3v2 δ3 q4p3 · · · qnrn−1∶4p3 u4t3∶2v1 u4t3v2 u4v3 . . . .. . .. . .. . .. . δn−1 qnpn−1 untn−1∶2v1 untn−1∶3v2 untn−1∶4v3 · · · unvn−1 δn 1 C C C C C C C C C C A : ð2:3Þ
Note that the redundancy of parameters allows us to express quasiseparable matrices with zero subblocks. The relevance of this representation is proved by the following the-orem proven in [24].
THEOREM1. A matrix A is quasiseparable if and only if it is representable as in (2.3).
In what follows, we prove some preliminary results about representations of qua-siseparable matrices, which will be useful in the remaining part of the paper.
COROLLARY 2. A quasiseparable matrix A can be decomposed as A¼ SðuÞþ Q,
where Q is a lower triangular matrix and
SðuÞ¼ 2 6 6 6 4 0 .. . Sn−1 0 0 0 · · · 0 3 7 7 7 5:
Sn−1 is anðn − 1Þ × ðn − 1Þ symmetric semiseparable matrix, representable with
para-meters q ¼ ðq2; : : : ; qnÞT, p ¼ ðp1; : : : ; pn−1ÞT, r ¼ ðr2; : : : ; rn−1ÞT, and in view of the
symmetry, u ¼ q, v ¼ p, and t ¼ r (see (2.3)). Similarly A ¼ SðlÞþ P, where SðlÞembeds a symmetric semiseparable matrix of size n− 1 with zeros in the first row and in the last column, and P is upper triangular.
Proof. From (2.3) we see that the upper rightðn − 1Þ × ðn − 1Þ minor of A has a semiseparable structure (2.1) in the upper triangular part. We set Sn−1¼ triuðA; 1Þþ
trilðAT;−2Þ. Matrix Q is defined as the difference between A and SðuÞ, and it is easy to
see that it is lower triangular. ▯
LEMMA3. If a quasiseparable matrix A is such that ri≠ 0 for i ¼ 2; : : : ; n − 1 in the
representation (2.3), then A can be decomposed into the sum of a lower triangular matrix and a rank-one matrix.
Proof. Using Corollary 2, A¼ SðuÞþ Q. If ri≠ 0, we can define the vectors ^q and ^p
as follows: 8 > > < > > : ^q1¼ 0; ^q2¼ q2; ^qi¼ qiri−1ri−2 · · · r2; i¼ 3; : : : ; n; 8 > > < > > : ^p1¼ p1; ^pi¼ pi∕ ðriri−1 · · · r2Þ; i ¼ 2; : : : ; n − 1; ^pn¼ 0:
We have SðuÞ¼ ^p ^qT þ Z, where Z is a lower triangular matrix. Then A ¼ ^p ^qTþ K with
K ¼ Q þ Z, and then it is the sum of the rank-one matrix ^p ^qT and the lower triangular
matrix K . ▯
3. The Neville representation. Neville elimination is a classical elimination technique which, differently from the standard Gaussian method, uses consecutive rows (columns) to reduce a matrix into an upper (lower) triangular form. When this elim-ination can be completely accomplished over rows and columns to reduce the matrix to diagonal form without interchanges, its formulation in terms of Gauss elementary ma-trices allows us to represent the matrix as the product of OðnÞ bidiagonal matrices. These factors give the Neville representation of the matrix, which is called Neville-representable. Neville elimination for rank-structured matrices is considered in [14].
In this section we introduce a subclass of quasiseparable matrices which are Neville-representable.
We first present some general results about the LU factorization of a quasiseparable matrix, and then we consider the Neville representation of a quasiseparable matrix, showing conditions for its existence.
With the LU factorization, the standard factorization of a matrix into the product of a unit lower triangular matrix and of an upper triangular matrix is meant. In the following, we will denote with L unit lower triangular matrices and with R unit upper triangular matrices.
THEOREM4. Let A be a quasiseparable matrix, and assume there exist L, R, and D
such that A¼ LDR, where L and R are unit lower and upper triangular and D is diag-onal. Then L and R can be chosen having quasiseparable structure. Moreover, L and R can be represented, according to (2.3), with the same parameters ui, ti, qi, riappearing
in the representation of A.
Proof. Since A is LU -factorizable, if A is nonsingular, then it is also strongly non-singular, and the thesis follows from a known result, which states that in this case L and R must be quasiseparable (see [24, p. 171]).
In the case A is singular, we have that at least one of the diagonal entries diof D is
zero. Writing A¼ SðlÞþ P, where SðlÞ is strictly lower triangular and quasiseparable, and P is upper triangular, we have LD¼ AR−1¼ SðlÞR−1þ PR−1, and looking at the trilðLD; −1Þ ¼ trilðSðlÞR−1;−1Þ, we see that LD is quasiseparable, and the genera-tors can be expressed in terms of the generagenera-tors of A. In detail, denote by u, v, t the generators of the lower triangular part of A, by ~u, ~v, ~t the generators of trilðLD; −1Þ, and by wij the (i, j)th entry of R−1, we can take, e.g.,
~
ui¼ ui; ~ti¼ ti; ~vi¼
Xi j¼1
ti∶jþ1vjwji:
Thus L can be chosen, in infinitely many ways, as a unit lower triangular semiseparable matrix, generated by the same ~u, ~~v, ~t, where ~~vidi¼ ~vi.
Similarly, R can be chosen as a unit upper triangular semiseparable matrix, gener-ated by the same q, r generating the upper triangular part of A. ▯
Now we will consider a set of quasiseparable matrices which are Neville-represen-table. A Neville-representable matrix can be expressed as a product of this form (see [12]):
where D is diagonal, and the factors LðiÞ, RðiÞare unit bidiagonal, lower and upper, re-spectively, with zero entries in these positions:
LðiÞkþ1;k¼ RðiÞk;kþ1¼ 0 for k ¼ 1; : : : ; i − 1:
DEFINITION4. LetS be the set of matrices A admitting the following factorization:
A¼ LsL1DR1Rs; ð3:1Þ where L−1s ¼ 0 B B B B B B @ 1 −x1 1 −x2 1 . . . . . . −xn−1 1 1 C C C C C C A ; L1¼ 0 B B B B B B @ 1 −a1 1 −a2 1 . . . . . . −an−1 1 1 C C C C C C A ; R1¼ 0 B B B B B B @ 1 −b1 1 −b2 . . . . . . 1 −bn−1 1 1 C C C C C C A ; R−1s ¼ 0 B B B B B B @ 1 −y1 1 −y2 . . . . . . 1 −yn−1 1 1 C C C C C C A ;
and D is a diagonal matrix.
It is straightforward to see that the matrices introduced by Definition 4 are LU -fac-torizable and quasiseparable. Moreover, they are also Neville-representable, because if we set
LðiÞ¼ I þ diagðxiei;−1Þ; RðiÞ¼ I þ diagðyiei; 1Þ; i ¼ n − 1; : : : ; 2;
Lð1Þ ¼ ðI þ diagðx1e1;−1ÞÞL1; Rð1Þ¼ R1ðI þ diagðy1e1; 1ÞÞ;
where eiis the ith vector of the canonical basis of Rn−1, we have
A¼ LsL1DR1Rs¼ Lðn−1Þ · · · Lð1ÞDRð1Þ · · · Rððn−1ÞÞ;
that is, the Neville representation of A. Therefore (3.1) can be seen as a variant of the Neville representation. The factorization (3.1) is not unique: even when A is strongly nonsingular and the products L¼ LsL1 and R¼ R1Rs are uniquely determined, there
are infinitely many values of x1, a1, b1, y1giving the same matrices Lð1Þ and Rð1Þ, and
therefore the same A. They can be freely chosen according to the conditions x1− a1¼
l21 and y1− b1 ¼ r12.
Nevertheless, there are LU -factorizable quasiseparable matrices which are not Neville-representable. For instance, the matrix
A¼ 0 @10 11 11 1 1 1 1 A
is factorizable A¼ LDR, where L¼ 0 @10 01 00 1 0 1 1 A;
but we cannot find any xiand aisuch that LsL1¼ L.
DEFINITION5. Let S1 be the set of matrices in S for which there exists a choice of
parameters in the representation (2.3) satisfying the following conditions: (a) ui≠ 0 for i ¼ 2; 3; : : : n;
(b) qi≠ 0 for i ¼ 2; 3; : : : ; n.
Remark 1. One can see some ambiguity in Definition 5 ofS1, due to the fact that the
same quasiseparable matrix has infinitely many representations (2.3). For instance, a quasiseparable matrix having zero entries only in the last row is inS1, because it can be
represented according to (2.3) with un¼ 1, tn−1¼ vn−1¼ δn¼ 0, but it can also be
represented with un ¼ δn¼ 0 for arbitrary choices of tn−1and vn−1. Two simple
equiva-lent conditions for a matrix inS to be in S1 are the following:
(i) if there is an entry aij¼ 0 in the strictly lower triangular part, then akj¼ 0
for k¼ i þ 1; : : : ; n;
(ii) if there is an entry aij¼ 0 in the strictly upper triangular part, then aik¼ 0
for k¼ j þ 1; : : : ; n.
A quasiseparable matrix which violates (i) or (ii) cannot be represented with all nonzero uiand qi. We could overcome the question by saying that the matrices inS1are all those
that admit a representation (2.3) with ui¼ qi¼ 1 for every i, as we will see in
Corol-lary 6.
THEOREM 5. The classS coincides with the class S1.
Proof. We prove the theorem by showing thatS ⊆ S1 andS1⊆ S.
Let us start by proving that if A∈ S, then A ∈ S1. First, A is factorizable A¼ LDR with L¼ LsL1and R¼ R1Rs. To prove that A is quasiseparable it is sufficient to prove
that it is quasiseparable in the lower and upper triangular parts.
Observe that Lsis semiseparable, and in fact the rank-one structure propagates to
the main diagonal. We distinguish two cases according to the possible reducibility of Ls.
If Lsis irreducible, then all xi≠ 0. Hence it can be written as Ls¼ ¯u¯vTþ P, where
¯
ui¼Qi−1
k¼1xk, ¯vi¼ ¯u−1i ; P is a strictly upper triangular matrix with superdiagonal
en-tries pi;iþ1 ¼ x−1i . Writing the bidiagonal matrix L1 as L1¼ I − diagða; −1Þ, we have
A¼ ð ¯u¯vT þ PÞðI − diagða; −1ÞÞDR
¼ ð ¯u¯vT þ P − ¯u¯vTdiagða; −1Þ − Pdiagða; −1ÞÞDR
¼ ¯uð¯vT − ¯vTdiagða; −1ÞÞDR þ ðP − Pdiagða; −1ÞÞDR:
Setting ~vT ¼ ð¯vT− ¯vTdiagða; −1ÞÞDR and ~P ¼ ðP − Pdiagða; −1ÞÞDR, we have that
A¼ ¯u~vT þ ~P. ~P is an upper triangular matrix having −a
idix−1i as ith diagonal entry.
So A is the sum of a rank-one matrix and an upper triangular matrix, and hence its lower triangular part is quasiseparable. In a similar way we can show that A has the upper triangular part with a quasiseparable structure. Note that all the entries of ¯u are non-zero, since ¯ui¼
Qi−1
k¼1xk. Hence, condition (a) of Definition 5 is satisfied.
If Lsis reducible, then one or more xi¼ 0. For simplicity let us consider only the case
for which xi¼ 0 and xj≠ 0 for all j ≠ i. The generalization to multiple blocks is
expressed as the direct sum of generator-representable semiseparable matrices. In this case Ls¼ L
ð1Þ s
L
Lð2Þs , where Lð1Þs and Lð2Þs are generator-representable semiseparable
ir-reducible matrices of sizes n1and n2, respectively, and hence Lð1Þs ¼ uð1Þvð1ÞT þ P1, and
Lð2Þs ¼ uð2Þvð2ÞTþ P2, with P1and P2being strictly upper triangular matrices. Moreover,
uð1Þand uð2Þhave no zero entries; since uð1Þi vð1Þi ¼ 1, uð2Þi vð2Þi ¼ 1. Let us partition all the relevant matrices according to the partitioning of Ls; thus we have D¼ D1
L D2, and R¼ R1Rs¼ R11 R12 0 R22 : In the same way as before we get
A¼ uð1Þwð1ÞT 0 κuð2ÞeT n1 u ð2Þwð2ÞT þ P11 P12 0 P22 ;
where en1 is the n1th vector of the canonical basis in R
n1, κ ¼ −vð2Þ
1 dn1ai, w
ð1ÞT¼
ðvð1ÞT− vð1ÞTdiagðað1∶i−1Þ; −1ÞÞD
1R11, and wð2ÞT¼ ðvð2ÞT − vð2ÞTdiagðaði þ 1∶n − 1Þ;
−1ÞÞD2R22þ κeTn1R12. Moreover, P11 and P22 are upper triangular matrices. Note that
the block in positionð2; 1Þ of A is null except for the last column, and this column is pro-portional to uð2Þ. Then trilðA; 0Þ is quasiseparable, and the following is a possible choice of generators for A: tj¼ 0 for j¼ i; 1 for j≠ i; uj¼ ( uð1Þj for 1≤ j ≤ i; uð2Þj−i for iþ 1 ≤ j ≤ n; vj¼ 8 > > < > > : wð1Þj for 1≤ j < i; κ for j¼ i; wð2Þj−i for jþ 1 ≤ j ≤ n.
Clearly all uj’s are nonzero. A similar proof can be given for the upper triangular part of A.
Let us prove thatS1⊆ S; that is, for every quasiseparable, LU-factorizable matrix
with ui≠ 0 and qi≠ 0, we can find parameters x, a, b, y, d such that A ¼ LsL1DR1Rs.
By assumption we have A¼ LDR, where L is unit lower triangular, D diagonal, and R is unit upper triangular. We want to prove that it is possible to factorize L as LsL1and
R as R1Rs. By Theorem 4, we have that L and R can be chosen quasiseparable, so in
detail, L¼ 0 B B B B B B B B B @ 1 ~ u2~v1 1 ~ u3~t2~v1 u~3~v2 1 ~ u4~t3∶2~v1 u~4~t3~v2 u~4~v3 1 .. . .. . .. . . . . ~ un~tn−1∶2~v1 u~n~tn−1∶3~v2 u~n~tn−1∶4~v3 · · · u~n~vn−1 1 1 C C C C C C C C C A ;
where ~ui≠ 0 since ~ui¼ ui, which are assumed to be nonzero. It is now easy to prove that L can be factorized as the product of Lsand L1by observing that the Neville elimination
I− diagðx; −1Þ having the Neville multipliers as codiagonal entries, i.e., xi−1¼
− ~ui~ti−1∕ ~ui−1, i¼ 3; : : : ; n.
Reasoning in the same way for the upper triangular part of A we can complete the proof. ▯
The following corollary shows how a matrix inS, represented as in Definition 4, can be represented by means of the generators appearing in (2.3).
COROLLARY 6. If A∈ S, then it can be represented, according to (2.3), with
ui¼ qi¼ 1, i ¼ 2; : : : ; n, ti¼ xi, ri¼ yi, i¼ 2; : : : ; n − 1, with the same xi, yi,
i¼ 1; 2; : : : ; n − 1 as in Definition 4.
Proof. By direct inspection, a simple choice for the parameters involved in the re-presentations of the semiseparable matrices L and R of the factorization A¼ LDR is the following:
ui¼ 1; vi¼ xi− ai; i¼ 2; : : : ; n; ti¼ xi; i¼ 2; : : : ; n − 1 for L;
qi¼ 1; pi¼ yi− bi; i¼ 2; : : : ; n; ri¼ yi; i¼ 2; : : : ; n − 1 for R.
Theorem 4 says that the parameters ui, ti, qi, and ri for A can be taken from the
re-presentions of L and R. ▯
It is easy to prove thatS contains all quasiseparable, Neville-representable matrices.
THEOREM 7. Any quasiseparable Neville-representable matrix is inS.
Proof. SinceS ¼ S1, we show that a Neville-representable quasiseparable matrix
must be inS1. Assume by contradiction this is not true; then by Remark 1, one of
con-ditions (i), (ii) would not be obeyed, say, (i). This means that there exist, in the strictly lower triangular part, some aij¼ 0 with aiþ1;j≠ 0, and, as a consequence of the rank
structure, all the entries in the ith row of the strictly lower triangular part would be zero. Then the ith row could not be used to eliminate the (iþ 1)th one, and the Neville row elimination would fail. But this would cause a contradiction. ▯
3.1. Quasiseparable TN matrices. Neville elimination is deeply connected with TN matrices [15], [12], [13].
DEFINITION6. A matrix A is called TN if all its minors of any order are nonnegative.
THEOREM8. If A∈ S is representable as in Definition 4, and xi; yi≥ 0, ai; bi≤ 0,
and di≥ 0, then A is TN.
Proof. In the standard hypothesis, A is TN, since it is the product of TN matrices. ▯
In the nonsingular case, Theorem 8 (and its converse) was proved in [14]. Remark 2. We can easily recognize matrices inS diagonally similar to TN matrices. The general condition is that xiyi≥ 0, di≥ 0, aibi≥ 0 with aixi≤ 0.
The class of TN matrices has nice properties that resemble those of positive semi-definite Hermitian matrices; in particular, its eigenvalues are real and nonnegative. Another similarity between the two classes of matrices is that also for TN matrices we can give an interlacing theorem [11], [1].
THEOREM9. Let A be TN with eigenvaluesλ1 ≥ λ2 · · ·≥ λn. Suppose Ak is a k× k
submatrix of A lying in rows and columns with consecutive indices and having eigenva-lues ~λ1≥ ~λ2 · · ·≥ ~λk. Then
4. On the shifted LR algorithm. In this section we present the shifted LR algo-rithm acting implicitly on the representation (3.1) of A. The shifted LR method proceeds iteratively as follows.2. Let Að0Þ¼ A; we obtain the sequence of matrices AðkÞin this way:
AðkÞ¼ LðkÞDðkÞRðkÞ;
Aðkþ1Þ¼ LðkÞ−1AðkÞLðkÞ− σkþ1I¼ DðkÞRðkÞLðkÞ− σkþ1I ; k¼ 0; 1; : : : ;
ð4:1Þ
where, for every k, the parameterσkþ1is chosen in accordance with some shift strategy to accelerate convergence.3Usually, instead of computing explicitly the factorization of
AðkÞand multiplying the factors in reverse order according to (4.1), we proceed implicitly performing the transition AðkÞ→ Aðkþ1Þin terms of their Neville representations. Note that Aðkþ1Þis no more similar to AðkÞ because at each step we subtract a shift, but we never restore it. This means that we have to accumulate the shifts during the computa-tion and add them back once the approximacomputa-tion of each eigenvalue becomes available. An important result is that the quasiseparable structure is preserved under LR steps.
THEOREM10. If Að0Þ¼ A is quasiseperable and LU-factorizable, then the matrix Að1Þ
built by (4.1) is quasiseparable.
Proof. Let A¼ LDR. We want to prove that the matrix Að1Þ¼ DRL is still qua-siseparable, although the possible symmetry of A is not preserved. Since the addition of a scalar matrix does not affect the quasiseparable structure, we can assume that no shift is performed for notational simplicity. By Corollary 2, there exists a symmetric semisepar-able matrix SðuÞ and a lower triangular matrix Q such that A¼ SðuÞþ Q, so we have Að1Þ¼ L−1AL¼ L−1ðSðuÞþ QÞL. As remarked in section 2, if SðuÞis irreducible, then it is generator-representable; otherwise it is the direct sum of generator-representable ma-trices. Assume that SðuÞ is irreducible, and therefore SðuÞ¼ pqTþ X, where X is a
strictly lower triangular matrix. Then Að1Þ ¼ L−1pqTLþ L−1X Lþ L−1QL. Setting
~
p ¼ L−1p, ~q ¼ LTq, ~Q¼ L−1ðX þ QÞL, we have Að1Þ ¼ ~p ~q þ ~Q. Then the minors taken
out of the strictly upper triangular part of Að1Þhave rank at most one. In the case SðuÞis reducible, we can use the same arguments for each of the irreducible diagonal blocks, obtaining that Að1Þ is reducible too and is quasiseparable in the upper triangular part. Similarly, if D is nonsingular, we can prove that Að1Þ has the quasiseparable struc-ture in the strictly lower triangular part. If D is singular, consider the matrix B¼ RL which is quasiseparable because it is a special case of the theorem with D¼ I . Now, the quasiseparable structure is preserved by multiplication by a diagonal matrix D. ▯ In this section we present two different methods for performing an implicit LR step through the updating of the parameters involved in the representation of matrices inS (see Definition 4). The first, presented in section 4.1, works on the parameters ai, bi, xi,
yi, and di, and the second one, described in section 4.2, considers the aggregated
para-meters mi¼ xiyiand takes advantage of the fact that there are some quantities that are
invariant during the steps, as explained in the following corollary.
COROLLARY 11. Let A be a quasiseparable matrix in S. If xi≠ 0 and yi≠ 0 for
i¼ 1; : : : ; n − 1, we can define the quantities
hi¼ aidi xi ; ki¼ bidi yi ; i¼ 1; : : : ; n − 1: ð4:2Þ 2
The superscript notation ·ðiÞwill be used only for depicting LR steps performed on matrices. We will omit this superscript as much as possible to avoid overloading the notation.
3
In section 4.3 we describe in detail the choice of the Laguerre shift, which is particularly well suited when dealing with TN matrices.
These quantities are invariant under LR steps without shift.
Proof. By Corollary 6, in the representation (2.3) of A we have that ri≠ 0 for
i¼ 2; : : : ; n − 1. By Lemma 3, A ¼ ^p^qT þ K, where K is lower triangular. Consider
the diagonal entries of A, which for the previous equality are given by the sum of the diagonal entries of ^p ^qT and the diagonal entries of K , say k
i. This means
δi¼ piqiþ ki. We have Að1Þ¼ L−1AL¼ L−1ð ^p^qT þ KÞL. Since L is unit lower
trian-gular, we have that the diagonal entries of the lower triangular term L−1K L are still equal to ki and remain constant during all the iterative steps.
SetΔ ¼ dgðKÞ. The matrix B ¼ A − Δ has a semiseparable structure in the upper triangular part, which extends to the main diagonal. Since A¼ LsL1DR1Rs, B can be
expressed as
B ¼ A − Δ ¼ LsT Rs;
ð4:3Þ
where T ¼ L1DR1− L−1s ΔR−1s is tridiagonal. The upper triangular matrix Rsis a
semi-separable upper triangular matrix satisfying Lemma 3; then it can be written as Rs¼ ~p ~qT þ ~K , where ~K is strictly lower triangular. Substituting in (4.3) we find
B¼ LsT ~p ~qT þ LsT ~K ;
thus we see that the diagonal of B agrees with the rank-one structure in the upper tri-angular part only if the lower tritri-angular matrix LsT ~K has all zeros as diagonal entries,
and this happens only if T is lower bidiagonal. By equating to zero the upper codiagonal entries of T¼ L1DR1− L−1s ΔR−1s , we readily obtain ki¼
dibi
yi.
Repeating the same reasoning for the lower triangular part of A, we obtain that hi¼
diai
xi are invariants too. ▯
4.1. A qd-type method. In this section we show how to obtain, starting from a matrix A¼ AðkÞinS, expressed as A ¼ LsL1DR1Rs, the new representation of Aðkþ1Þ¼
DR1RsLsL1− σkþ1I in terms of the updated parameters, that is, Aðkþ1Þ¼ ¯¯Ls¯¯L1¯¯D ¯¯R1¯¯Rs,
given that Aðkþ1Þ∈ S.
The entire procedure consists in updating the parameters xi, yi, di, ai, bi which define quasiseparable matrices inS. The updating process starts with the computation of ~A¼ DR1RsLsL1and replaces products of the type RL with products of the type LDR,
where D is diagonal. In particular, we have
~ A¼ DR1ðRsLsÞL1¼ DR1ð ¯LsE ¯RsÞL1 ð4:4Þ ¼ ðDR1L¯sÞE ¯RsL1¼ 𠯯LsF ¯R1ÞE ¯RsL1 ð4:5Þ ¼ ¯¯LsF ¯R1ðE ¯RsL1Þ ¼ ¯¯LsF ¯R1ð ¯L1G¯¯RsÞ; ð4:6Þ
where D¼ diagðdiÞ, E ¼ diagðeiÞ, F ¼ diagðfiÞ, and G ¼ diagðgiÞ are diagonal
ma-trices. Equations (4.4), (4.5), (4.6) make sense if the intermediate matrices RsLs,
DR1L¯s, and E ¯RsL1 are all LU -factorizable. Anyway, if the procedure described by
Aðkþ1Þ¼ ¯¯LsF ¯R1L¯1G¯¯Rs− σkþ1I ¼ ¯¯Ls¯¯L1¯¯D ¯¯R1¯¯Rs;
ð4:7Þ
where ¯¯D is diagonal.
The assumptions required by the updating (4.4), (4.5), (4.6), besides the prelimin-ary request for Aðkþ1Þto be inS, are satisfied for all TN matrices, with a suitable choice of the shift parameter (see section 4.3).
Let us describe the updating process of equality (4.4). Set ¯
LsE ¯Rs¼ RsLs
for a suitable nonsingular diagonal matrix E. If we rewrite the above equation as ¯
R−1s E−1L¯−1s ¼ L−1s R−1s , where all the matrices involved are bidiagonal or diagonal, and we define the auxiliary variables
αi¼ e−1i − xi−1yi−1; i¼ 1; : : : ; n − 1;
αn¼ 1;
ð4:8Þ
we obtain the following recurrences: 8 < : e−1i ¼ αiþ xi−1yi−1; i¼ n; : : : ; 2 ; αi−1 ¼ αi∕ e−1i ; i¼ n; : : : ; 2; e−11 ¼ α1: ð4:9Þ
The first recurrence of (4.9) for determining the e−1i is obtained from the definition of the auxiliary variablesαi, while the recurrence for the computation of the αicomes from
equating the diagonal entries of the tridiagonal matrices ¯R−1s E−1L¯−1s and L−1s R−1s .
By equating the codiagonal entries we get that the entries of ¯L−1s and ¯R−1s can be
com-puted as follows:
¯xi¼ xi∕ e−1iþ1; i¼ 1; : : : ; n − 1;
¯yi¼ yi∕ e−1iþ1; i¼ 1; : : : ; n − 1:
The updating described in (4.5) consists of
¯¯LsF ¯R1 ¼ DR1L¯s
for a suitable nonsingular diagonal matrix F . Again we can use the fact that the inverse of matrices of type Lsis bidiagonal. We have F ¯R1L¯−1s ¼ ¯¯L
−1
s DR1, and setting
βi¼ 1 − bi¯xi; i¼ 1; : : : ; n − 1;
we obtain the following recurrences for the diagonal entries of F : 8 < : f1¼ d1β1; fi¼ diβi∕ βi−1; i¼ 2; : : : ; n − 1; fn¼ dn∕ βn−1;
and the final ¯¯xi describing ¯¯Ls,
The intermediate entries of ¯R1 are
¯b1¼ b1∕ β1;
¯bi¼ biβi∕ βi−1; i¼ 2; : : : ; n − 1:
Let us describe step (4.6), that is, ¯
L1G¯¯Rs¼ E ¯RsL1: If we rewrite the above equation as ¯R−1s E−1L¯1¼ L1¯¯R
−1
s G−1, and defining the auxiliary
variables
γi¼ 1 − ¯yiai; i¼ 1; : : : ; n − 1;
we obtain the following recurrences for the diagonal entries of G: 8 < : g1¼ γ1∕ e−11 ; gi¼ γi∕ ðγi−1e−1i Þ; i ¼ 2; : : : ; n − 1; gn ¼ 1∕ ðγn−1e−1n Þ:
The final entries of ¯¯Rs are computed as follows:
¯¯yi¼ ¯yigiþ1∕ e−1iþ1; i¼ 1; : : : ; n − 1;
while the intermediate entries of ¯L1 are
¯ai¼ ai∕ ðe−1iþ1giÞ; i¼ 1; : : : ; n − 1:
It remains to describe the final updating which involves the terms in the brackets in (4.7). If no shift is chosen, then Aðkþ1Þ¼ Að1Þ, so ¯¯L1, ¯¯D, and ¯¯R1 have to be found such
that
¯¯L1¯¯D ¯¯R1¼ F ¯R1L¯1G:
ð4:10Þ
The final matrices¯¯L1and ¯¯R1can be computed introducing auxiliary variablesδidefined
as
δi¼ ¯¯di− ¯ai¯bifigi; i¼ 1; : : : ; n − 1;
δn¼ ¯¯dn:
We have the following recurrences for the final ¯¯D: 8 > > > < > > > : δ1¼ f1g1; ¯¯di¼ δiþ ¯ai¯bifigi; i¼ 1; : : : ; n − 1;
δiþ1¼ δifiþ1giþ1∕ ¯¯di; i¼ 1; : : : ; n − 1;
¯¯dn¼ δn:
ð4:11Þ
The entries of ¯¯L1 and ¯¯R1 can then be obtained as follows:
¯¯ai¼ ¯aifiþ1gi∕ ¯¯di; i¼ 1; : : : ; n − 1:
ð4:12Þ
¯¯bi¼ ¯bifigiþ1∕ ¯¯di; i¼ 1; : : : ; n − 1:
In case of shiftσ ¼ σkþ1, note that Aðkþ1Þ¼ Að1Þ− σI can be expressed as ¯¯LsF ¯R1L¯1G¯¯Rs− σI ¼ ¯¯LsðF ¯R1L¯1G− σ ¯¯L −1 s ¯¯R −1 s Þ ¯¯Rs:
So we must modify only the updating of the variables ¯¯ai,¯¯biand ¯¯didescribed by (4.12),
(4.13), and (4.11). In particular, (4.10) becomes ¯¯L1¯¯D ¯¯R1¼ F ¯R1L¯1G− σ ¯¯L
−1 s ¯¯R
−1 s ;
and ¯¯L1, ¯¯D, and ¯¯R1 can be computed by means of the following recurrences, whereδiis
defined as before as
δi¼ ¯¯di− ¯ai¯bifigi; i¼ 1; : : : ; n − 1;
δn ¼ ¯¯dn:
The recurrences replacing (4.11) are 8 > > > > > < > > > > > : δ1¼ f1g1− σ; ¯¯di¼ δiþ ¯ai¯bifigi; i¼ 1; : : : ; n − 1;
δiþ1¼ fiþ1giþ1δi∕ ¯¯di− σð1 þ ¯¯xið¯¯yi− ¯¯biÞ − fiþ1gi¯ai¯¯yi∕ ¯¯diÞ; i ¼ 1; : : : ; n − 1;
¯¯dn¼ δn:
ð4:14Þ
The new ¯¯aiand ¯¯bi can be obtained as follows:
¯¯ai¼ ð¯aifigiþ1− σ¯¯xiÞ∕ ¯¯di; i¼ 1; : : : ; n − 1:
ð4:15Þ
¯¯bi¼ ð¯bifiþ1gi− σ¯¯yiÞ∕ ¯¯di; i¼ 1; : : : ; n − 1:
ð4:16Þ
Alternatively, one can first compute ¯¯aiand ¯¯biwith (4.15) and (4.16), and then express
δiþ1 as
δiþ1¼ fiþ1giþ1δi∕ ¯¯di− σð1 þ ¯¯yið¯¯xi− ¯¯aiÞ − figiþ1¯bi¯¯xi∕ ¯¯diÞ; i¼ 1; : : : ; n − 1:
Remark 3. We denoted the method described in this section as belonging to the family of qd algorithms [20], [10], [17]. The reason is that it has similar characteristics, since the definition of the auxiliary variablesαi, δi makes it possible, with some sign
hypotheses (see Theorem 13), to get rid of subtractions which are hidden in the auxiliary parameters; only divisions, multiplications, and sums are needed (except for the shift). 4.2. Working with invariants: Another qd-type method. In Corollary 11 we proved that if xi≠ 0 and yi≠ 0 for all i ¼ 1; : : : ; n − 1, then the quantities hiand ki
defined as in (4.2) are invariant under LR steps. This observation allows us to rewrite the previous recurrences using these quantities. The new algorithm, described by Algo-rithm 1, although applicable only to a subclass of matrices inS, has a lower computa-tional cost, as we will see in section 5.
The new recurrences consider the aggregated quantities mi¼ xiyi, the invariants ki,
hi, and the diagonal entries di. Note that the use of invariants allows us to simplify the
This procedure should be combined with an effective shift strategy. A particularly con-venient choice for the shift is described in section 4.3.
As in the recurrences presented in section 4.1, we see that we still need auxiliary variables αi and δi, but the aggregation of parameters xi and yi into mi allows us
to reduce the number of recurrences. This method does not have a natural matrix for-mulation, but it is easy to verify its correctness by merging the recurrences for the up-dating of xi and yi to get the updating formula for mi.
ALGORITHM1. m; h;k;d←LRstepm;h;k;d;σ. αn←1; for i¼ n to 2 do e−1i ←αi− mi−1;fAuxiliary variablesg; αi−1←αi∕ e−1i end for e−11 ←α1; for i¼ 1 to n − 1 do pi←ð1 − kimi die−1iþ1Þð1 − himi
die−1iþ1Þ; fAuxiliary variablesg
end for
for i¼ 1 to n − 1 do ¯¯
mi←mipiþ1diþ1∕ ðpidie−2iþ1Þ; fUpdating of mig
end for δ1←p1d1∕ e−11 − σ; for i¼ 1 to n − 1 do ¯¯di←δiþ hikimi∕ ðdie−1iþ1Þ; fUpdating of dig δiþ1←δipiþ1diþ1∕ ðpi¯¯die−1iþ1Þ − σð1 þ ¯¯mið1 þ ðσ − ðhiþ kiÞÞ∕ ¯¯diÞÞ; end for
¯¯dn←δn; fUpdating of the last dng
for i¼ 1 to n − 1 do ¯¯hi←hi− σ;
¯¯ki←ki− σ.
end for
4.3. The Laguerre shift. The choice of an adequate shift strategy is always of crucial importance for the convergence. Various shift strategies have been proposed, ranging from the classical Rayleigh shift defined as the entry in position (n, n), to the Wilkinson shift in the case the matrix might have complex eigenvalues [27]. In this section we describe in detail a shift technique known as Laguerre shift [27], [18] which has shown to be particularly well suited in the case of quasiseparable matrices with real positive eigenvalues.
In particular, the shiftσ ¼ σkþ1in (4.14) is chosen in accordance with the following formula: σ ¼ n sðkÞ1 þ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ðn − 1ÞðnsðkÞ2 − ðs ðkÞ 1 Þ 2 Þ q ; ð4:17Þ
where sðkÞ1 ¼ traceððAðkÞÞ−1Þ and s2¼ traceððAðkÞÞ−2Þ. The choice of the Laguerre shift
guarantees that the eigenvalues are computed in an ordered way since 0 <σ ≤ μn,
We start from AðkÞ factorized as
AðkÞ¼ LsL1DR1Rs;
so we need the diagonal entries cii of
C¼ ðAðkÞÞ−1¼ R−1s R1−1D−1L−11 L−1s :
In the case xi, yi≠ 0, using the invariants4by direct computation, we have
8 > > < > > : cnn¼ d−1n ; cn−1;n−1¼ d−1n−1þ d−1n mn−1ðhn−1d−1n−1− 1Þðkn−1d−1n−1− 1Þ; cii ¼ d−1i þ ðd−1iþ1þPn−1 r¼iþ1ð Qr j¼iþ1mjhjkjd−2j Þd−1rþ1Þmiðhid−1i − 1Þðkid−1i − 1Þ; i¼ n − 2; : : : ; 1: Setting tn−1¼ d−1n mn−1;
ti¼ ðd−1iþ1þPnr¼iþ1−1 ðQrj¼iþ1mjhjkjd−2j Þd−1rþ1Þmi; i¼ n − 2; : : : ; 1;
the requested trace s1 can be computed with about 14n flops in this way:
8 > > > < > > > : cnn¼ d−1n ; tn−1¼ d−1n mn−1; ti¼ ðtiþ1hiþ1kiþ1d−1iþ1þ 1Þmid−1iþ1; i¼ n − 2; : : : ; 1; cii¼ d−1i þ tiðhid−1i − 1Þðkid−1i − 1Þ; i ¼ n − 1; : : : ; 1; s1¼ traceðCÞ ¼ Pn i cii: Since s2¼ traceðC2Þ ¼ Pn i¼1c2iiþ 2 Pn−1
j¼1Pni¼jþ1cijcji, the sum of all the products
cijcji has to be computed. Let us start from those involving codiagonal entries
ci;i−1ci−1;i, which have the form
8 > > > > > > < > > > > > > : cn;n−1cn−1;n¼ mn−1ðhn−1d−1n−1− 1Þðkn−1d−1n−1− 1Þd−2n ; cn−1;n−2cn−2;n−1¼ ð1 þ hn−1mn−1d−1n ðkn−1d−1n−1− 1ÞÞð1 þ kn−1mn−1d−1n ðhn−1d−1n−1− 1ÞÞ mn−2ðhn−2d−1n−2− 1Þðkn−2d−1n−2− 1Þd−2n−1;
ci;i−1ci−1;i¼ ð1 þ himiðkid−1i − 1Þðd−1iþ1þ
Pn−1 r¼iþ1d−1rþ1Qrj¼iþ1mjhjkjd−1j ÞÞ ð1 þ kimiðhid−1i − 1Þðd−1iþ1þ Pn−1 r¼iþ1d−1rþ1Qrj¼iþ1mjhjkjd−1j ÞÞ mi−1ðhi−1d−1i−1− 1Þðki−1d−1i−1− 1Þd−2i ; i¼ n − 2; : : : ; 2: If we set 8 > > > > > > < > > > > > > : t 0n−1¼ ð1 þ hn−1mn−1d−1n ðkn−1d−1n−1− 1ÞÞ; t 0 0n−1¼ ð1 þ kn−1mn−1d−1n ðhn−1d−1n−1− 1ÞÞ; t 0i¼ ð1 þ himiðkid−1i − 1Þðd−1iþ1þ Pn−1 r¼iþ1d−1rþ1 Qr j¼iþ1mjhjkjd−1j ÞÞ; i¼ n − 2; : : : ; 2; t 0 0i ¼ ð1 þ kimiðhid−1i − 1Þðd−1iþ1þ Pn−1 r¼iþ1d−1rþ1Qrj¼iþ1mjhjkjd−1j ÞÞ; i¼ n − 2; : : : ; 2; 4
When some of the xior yiare zero, we need to work with the full set of parameters since the invariants hi and kicannot be computed. In that case we have different formulas, with a higher computational cost, not described here because they are too complicated. However, new formulas can be obtained following the same reasoning and using similar techniques as those employed in this section.
all products ci;i−1ci−1;i can be computed according to the following scheme with 18n flops: 8 > > > > > > > > < > > > > > > > > : t 0n−1¼ ð1 þ hn−1mn−1d−1n ðkn−1d−1n−1− 1ÞÞ; t 0 0n−1¼ ð1 þ kn−1mn−1d−1n ðhn−1d−1n−1− 1ÞÞ;
t 0i¼ hiþ1miþ1diþ2ð1 þ t 0iþ1kiþ1diþ2Þ; i ¼ n − 2; : : : ; 2; t 0 0i ¼ kiþ1miþ1diþ2ð1 þ t 0 0iþ1hiþ1diþ2Þ; i ¼ n − 2; : : : ; 2; zn−1¼ d−2n ; zi¼ ð1 þ t 0iþ1ðkiþ1d−1iþ1− 1ÞÞð1 þ t 0 0iþ1ðhiþ1d−1iþ1− 1ÞÞ; i ¼ n − 2; : : : ; 1; ci;i−1ci−1;i¼ zi−1mi−1ðhi−1d−1i−1− 1Þðki−1d−1i−1− 1Þ; i ¼ n; : : : ; 2: The sumsϵj¼ Pn
i¼jþ2cijcji, j¼ n − 2; : : : ; 1, can be computed in this way:
8 < : wn−1¼ 0; wj¼ ðwjþ1þ zjþ1Þmjþ1hjþ1kjþ1d−2jþ1; j¼ n − 2; : : : ; 1; ϵj¼ wjmjðhjd−1j − 1Þðkjd−1j − 1Þ; j ¼ n − 2; : : : ; 1:
Finally, the sumPn−1 j¼1
Pn
i¼jþ1cijcji, which is required to complete the computation of
s2, can be expressed as Xn−1 j¼1 Xn i¼jþ1 cijcji¼ cn;n−1cn−1;nþ Xn−2 j¼1 ðϵjþ cjþ1;jcj;jþ1Þ ¼X n−1 j¼1 ðwjþ zjÞmjðhjd−1j − 1Þðkjd−1j − 1Þ;
and it costs 9n flops more.
In the case where we deal with a restricted class of matrices, for example, when dealing with tridiagonal or semiseparable matrices, we can simplify this procedure and compute the shift with a lower number of operations. In section 7, for example, we simplified the computation of the shift when our method is applied to tridiagonal matrices, obtaining the Laguerre shift with a lower number of flops.
5. Stability and computational cost. In sections 4.1 and 4.2 we described the implicit LR algorithm acting on the Neville representation of the matrix, assuming that the algorithm proceeds without incurring in situations requiring the algorithm to stop. However, it is well known [27] that the LR process can break down if, at step k, the matrix AðkÞ is no more LU -factorizable. In practical cases, to overcome this situation and resume the iterative process, one can change the value of the shiftσk, and hopefully
the problem is not present in the new matrix. When our method is applied, however, as observed in section 4.1, we can have that the process halts also because one of the quan-tities appearing in the denominator of the recurrences in sections 4.1 or 4.2 becomes zero. We will refer to this anomalous situation as a breakdown, too.
In this section we first show that the class of Neville-representable quasiseparable matrices is closed under shifted LR steps. Then we analyze stability and structure pre-servation of the method when applied to TN matrices. Moreover, we show that both breakdown situations do not occur when the algorithm is applied to TN matrices.
In Theorem 10 it is proven that the quasiseparable structure is preserved under LR steps. The next corollary proves that, if no anomalous situations happen, also the sub-classS is closed by LR steps.
COROLLARY12. Let A∈ S; if breakdown does not occur at each LR step, then each
AðkÞ in (4.1) is still inS.
The proof is based on the observation that if breakdowns do not occur at each step, then we can construct a matrix Aðkþ1Þsimilar to AðkÞ− σkþ1I , by means of updating the parameters involved in the Neville representation as described in section 4.1 or 4.2.
The natural class to which the proposed algorithm can be applied is the class of TN matrices.
THEOREM13. Let AðkÞbe a TN quasiseparable matrix represented as in Definition 4
with di> 0, then the qd-type methods described in sections 4.1 and 4.2 without shift or
with a shift which preserves the positivity of the eigenvalues have the following properties: 1. They are breakdown-free, and the updated parameters involved in the
represen-tation are all nonnegative.
2. The new matrix Aðkþ1Þproduced is still quasiseparable TN, with di> 0.
3. They do not contain subtractions (except a subtraction for the shift).
Proof. For a TN matrix AðkÞ, from Theorem 8 we know that xi, yi≥ 0, ai, bi≤ 0. If
we assume xi, yi≠ 0, we have equivalently mi> 0, hi, ki≤ 0. The shift σkþ1is such that
0 <σkþ1<μn, where μn is the smallest eigenvalue of AðkÞ.
1. Consider the recurrences (4.9); we see immediately, by induction on i, that e−1i ≥ αi> 0, whereαiare the auxiliary variables defined by (4.8). As a
con-sequence, considering the other recurrences in section 4.1, we have ¯xi, ¯yi≥ 0,
βi,γi≥ 1, fi, gi> 0, ¯¯xi, ¯¯yi≥ 0, ¯ai, ¯bi≤ 0. Similarly, if we assume xi, yi≠ 0 and
we refer to the formulation introduced in section 4.2 and used in Algorithm 1, we find that pi≥ 1 and ¯¯mi≥ 0.
If there is no shift, then ¯¯di≥ δi> 0, i¼ 1; : : : ; n − 1, again by induction on i,
and, as a consequence, ¯¯ai, ¯¯bi≤ 0.
In the case of a shift, we have by hypothesis that at each stepσkþ1is such that 0 <σkþ1<μn. We have to show also that in this case ¯¯di> 0. We know that
Aðkþ1Þ¼ LðkÞAðkÞLðkÞ−1− σkþ1I¼ ¯¯LsT¯¯Rs;
where T ¼ F ¯R1L¯1G− σkþ1¯¯L−1s ¯¯R −1
s is tridiagonal. Now, let Tjbe the jth
lead-ing principal minor of T , observe that for each j, detðTjÞ > 0, since Tjis similar
to AðkÞj − σkþ1Ij, where AðkÞj is the jth leading principal minor of AðkÞ. From the
interlacing property for TN matrices (Theorem 9), we have that 0 <μn− σkþ1 ≤ μiðjÞ− σkþ1, where μðjÞi is an eigenvalue of A
ðkÞ
j . This means
that detðTjÞ > 0, so T is strongly nonsingular, and in its LU factorization T ¼
¯¯L1¯¯D ¯¯R1 the entries ¯¯diare all positive. Moreover, ¯¯ai, ¯¯bi≤ 0, as shown by (4.15)
and (4.16).
No breakdown happens, because no division by zero can occur in computing the quantitiesαi, fi, gi, pi,δi.
2. Aðkþ1Þ is still TN, because it is Neville-representable with nonnegative
para-meters. In particular, all ¯¯di are positive.
3. It is easy to check that the updating formulas in section 4.1 and Algorithm 1 described in section 4.2 do not contain subtractions when applied to TN ma-trices, with the exception of a subtraction for the computation ofδiþ1. In fact, e−1i , βi, γi are sums of nonnegative quantities, and pi in the second loop of
Algorithm 1 is the product of sums of nonnegative quantities, since ki,
that, in case no shift is applied,δi> 0, and hence each¯¯diis obtained (see (4.14))
as the sum of two nonnegative quantities,δiand ¯ai¯bifigi, or kihimi∕ ðdie−1iþ1Þ in
Algorithm 1.
In the case of a shift, assume by contradiction that, for a given i,δi≤ 0. It is
easy to see that, if this is the case,δj≤ 0 for all j > i, since δiþ1is computed as
the sum of two negative quantities in (4.14) and in the third loop of Algorithm 1 as well. But this is a contradiction since ¯¯dn¼ δn > 0, as already proved. The
updating of the invariants does not involve subtractions since hi, ki≤ 0 and
σkþ1> 0. ▯
The approximation of distinct eigenvalues in increasing order is a well-known prop-erty of LR convergence in the real positive case if the shift strategy preserves the order-ing, as for Laguerre shift. In more detail, for nonsingular quasiseparable TN matrices the Laguerre shiftσkþ1 is such that 0 <σkþ1≤ μn. Furthermore, the shift computed in
fi-nite precision arithmetics is generally multiplied by a factor slightly less than one, also to prevent the effect of rounding errors which could destroy the TN structure.
As a consequence of the shift strategy the eigenvalues are computed in increasing order, so the deflation criterion is based only on the magnitude of the off-diagonal entries in the last row and column of AðkÞ.
The cost of Algorithm 1 is about 17n flops without shift and about 27n in the case a shift strategy is applied. The cost doubles if one works without invariants, and it de-creases if one deals, for example, with tridiagonal matrices, because the parameters xi
and yi are not needed.
6. Reduction to tridiagonal form. The Neville representation of quasiseparable matrices makes it easy to describe also an Oðn2Þ algorithm for the reduction into
tri-diagonal form of a matrix inS. A tridiagonalization procedure for TN matrices with the generalized quasiseparable structure has been described by Gemignani in [14] and is inspired by the algorithm of Koev designed for a generic TN matrix [15].
ALGORITHM2. TRIDIAGONALIZATION PROCEDURE.
^x←x; ^y←y, ^a←a; ^b←b; ^d←d; for j¼ 1 to n − 1 do
for i¼ n − 1 to j do
½^x; ^y; ^a; ^b; ^d←swap ð^x; ^y; ^a; ^b; ^d; iÞ; fAnnihilates row ig ½^x; ^y; ^a; ^b; ^d←swap ð^y; ^x; ^b; ^a; ^d; iÞ; fAnnihilates column ig end for
end for
However, it is possible to see that the algorithm can be extended also to matrices not TN but belonging to the classS. In the case where the tridiagonalization process is ap-plied to TN matrices, the stability of the process is guaranteed since it is subtraction-free, and breakdown cannot occur since there are no divisions by zero. Let us describe the process of tridiagonalization of a matrix A∈ S using the representation in terms of para-meters xi, yi, ai, bi, di. The algorithm can be described as follows.
To understand the tridiagonalization procedure, note that each time we apply the swap procedure with parameter i, we annihilate the entry xi or yi appearing in the
representation of the quasiseparable matrix. We need to annihilate each xiseveral times,
since the swap procedure creates a bulge that has to be removed with more Gauss trans-formations. In particular, we have to apply swap on row i for each column, and then we have a total of nðn − 1Þ calls to swap. The swap function, with parameter i, acts on
rows i, iþ 1 and annihilates xi, multiplying by a Gauss elementary matrix Gi
on the right and by its inverse on the left. We have G−1i AGi¼ G−1i LsL1DR1RsGi,
where Gi¼ Ii−1
L
ELIn−i−1 and E ¼ ½xðiÞ1 01. Reasoning similarly to what is done
for deriving the recurrences in section 4.1, the Gauss transformation Gi acting on
ALGORITHM3. ^x; ^y; ^a; ^b; ^d←swapx;y;a;b;d;i .
Require: i <¼ n − 1
α←xðiÞ {E¼ ½1α 01 is the transformation on rows i and i þ 1} ^x←x, ^y←y, ^a←a, ^b←b, ^d←d; {Parameter initialization} ^xðiÞ←0;
w←1 þ αyðiÞ; {Eð1Þ¼ ½w
α 1∕ w0 is the transformation acting on the left of Rs}
^yði − 1Þ←wyði − 1Þ, ^yðiÞ←yðiÞ∕ w; k←w − αbðiÞ {Eð2Þ¼ ½k
α 1∕ k0 is the transformation acting on the left of R1}
^bði − 1Þ←wbði − 1Þ; ^bðiÞ←kbðiÞ∕ w; if i≠ n − 1 then
^bði þ 1Þ←kbði þ 1Þ end if
^dðiÞ←kdðiÞ; ^dði þ 1Þ←dði þ 1Þ∕ k; ^aðiÞ←aðiÞ − ðαdði þ 1Þ∕ dðiÞÞ; if i≠ n − 1 then
δ←ðαdði þ 1Þ∕ dðiÞÞaði þ 1Þ∕ aðiÞ, {Eð3Þ¼ ½1
δ 01 is the transformation acting
on rows iþ 1, i þ 2 on the left of L1}
^aði þ 1Þ←aði þ 1Þ þ δ; end if
if i≠ n − 1 then ^xði þ 1Þ←δ − xði þ 1Þ end if
the right is moved inside as follows:
G−1i AGi¼ G−1i LsL1DR1ðRsGiÞ ¼ Lð1Þs L1DR1Gð1Þi R^s
¼ Lð1Þs L1DðR1Gð1Þi Þ ^Rs¼ Lð1Þs L1DGð2Þi R^1R^s
¼ Lð1Þs Gð3Þiþ1L^1D ^^R1R^s¼ ^LsL^1D ^^R1R^s:
In particular, with the same notation of the pseudocode in Algorithm 3, we have Gð1Þi ¼ Ii−1
L
Eð1ÞLIn−i−1 with Eð1Þ¼ ½xwðiÞ 1∕ w0 , G ð2Þ i ¼ Ii−1
L
Eð2ÞLIn−i−1 with Eð2Þ¼
½ k
xðiÞ 1∕ k0 , and finally G ð3Þ iþ1¼ Ii
L
Eð3ÞLIn−i−2with Eð3Þ¼ ½1δ 01. Since G ð1Þ
i Lshas only
the effect of annihilating the ith row, when we multiply on the right by Gð3Þiþ1, this will only update the entry iþ 1 of the vector describing Lð1Þs .
The swap procedure costs 19 flops; hence the cost of the tridiagonalization proce-dure is 19n2. Once the tridiagonal matrix is available, one can apply one of the well-known techniques for tridiagonal matrices. For example, since we already have the LU factorization, we can proceed by applying our method described in section 4.1 pruned of the unnecessary recurrences related to the updating of the parameters xi
and yi that now are zero. Similarly, one can apply the dqds algorithm [17]. Another
possible way is to symmetrize the tridiagonal matrix first, and then apply the QR or the LLH method. The cost of the dqds algorithm is about 6n flops plus the cost of the shift,
that is, 31n if the Laguerre shift is applied using a simplified version of the formulas proposed in section 4.3.
7. Numerical experiments. In this section we report some numerical results ob-tained using our methods for the computation of all eigenvalues of a possible unsym-metric quasiseparable matrix. The experiments were done using MATLAB 2006B on a Mac Powerbook, running OS X.5.
We denote byλ ¼ ½λ1;λ2; : : : ;λn the vector containing the exact eigenvalues and by
~
λ ¼ ½~λ1; ~λ2; : : : ; ~λn the vector of the computed ones, sorted in such a way that ~λi is an
approximation ofλi. For the purpose of estimating the relative error, we will consider the
results of MATLAB’s eig as the exact eigenvalues, that is, λ ¼ eigðAÞ. Accuracy is measured considering the absolute and relative error, that is,
EðabsÞ¼ kλ − ~λk∞¼ max i fjλi− ~λijg; E ðrelÞ¼ max i jλi− ~λij jλij :
By QS-qd (for quasiseparable-qd) we denote the implementation of Algorithm 1 endowed by Laguerre shift as described in section 4.3. TridLR denotes the implementa-tion of the tridiagonalizaimplementa-tion procedure described in Algorithm 2 followed by steps of the dqdsmethod, as described in [17].
In our experiments we compared the eigenvalues computed with QS-qd with MATLAB eig, using a cutting criterion of 10−16as deflation tolerance. It is well known that, for rank-structured matrices, it is often more convenient to compute the eigenva-lues, by applying directly an iterative method without the preliminary reduction to tri-diagonal or Hessenberg form [25]. In fact, the possibility of representing the matrices with a low number of parameters, and the closure under GR-type [26] steps, makes it convenient to apply directly an implicit method acting on the representation of the rank-structured matrix. The overhead of the computation of the tridiagonal struc-ture is, in fact, not rewarded by the efficiency of the tridiagonal eigensolver. The purpose of our experimentation is to show that good accuracy and efficiency can be obtained by applying QS-qd directly on the representation of a quasiseparable matrix. The experi-mentation has three main goals. The first goal is a comparison with the specialized tools for eigenvalues computation of symmetric semiseparable plus diagonal (SSPD) ma-trices, both TN and not. To this extent, the results obtained with our solver both in terms of accuracy and CPU time are compared with the results obtained by using the QR solver implemented by the routine EIGSSD5 which represents the state of
the art of the QR implementation for SSPD matrices.
In the case of non-TN matrices (Table 7.1), our algorithm performs a little worse from the point of view of accuracy, but it is faster, requiring almost half the time re-quired by the QR routine. To make a fair comparison, the time for the conversion from our representation to the Givens-vector representation used by the EIGSSD routine is not accounted for. In the case the matrix is TN, our algorithm performs better also in terms of accuracy, and we gain a digit over the QR implementation (see Table 7.2).
The second goal is to show the effectiveness of our method on (possibly) unsym-metric TN matrices. Table 7.3 reports the results obtained by our method on instances
5
EIGSSD is a function included in the MATLAB package SSPACK accompanying the book [25], and it is available online athttp://www.cs.kuleuven.be/~mase/.
of random generated TN matrices of different sizes. The time in seconds of our implementation is reported as well. We see that the absolute and relative errors are quite good, and the increase of time with respect to the size shows, as expected, a quadratic behavior.
The third goal consists of testing our QS-qd implementations on some“difficult” problems to see how accuracy is affected.6In Table 7.4 the results on a TN matrix with
a small eigenvalue equal toα are reported. We see that, when the eigenvalue α becomes of the order of the machine precision, the results are meaningless because EðrelÞis of order 10−1. Looking at the plot in logarithmic scale in Figure 7.1 of relative errors of each
TABLE7.1
Random SSPD matrix. Comparison with QS-qd and EIGSSD.
n EðabsÞ EðrelÞ QS-qd(sec) EðabsÞ EðrelÞ EIGSSD(sec)
10 2.7732e-15 1.0333e-15 0.08 1.0151e-14 3.7824e-15 0.14
50 4.6343e-13 7.5474e-14 0.39 7.4737e-14 1.2172e-14 0.94
100 2.7996e-13 3.1850e-14 1.36 2.7323e-13 3.1085e-14 3.29
200 3.0727e-12 2.3750e-13 5.25 1.0149e-12 7.8444e-14 12.59 300 2.4134e-12 1.4828e-13 14.80 8.9760e-12 5.5147e-13 32.64 500 6.9054e-12 3.5405e-13 35.29 2.6940e-12 1.3812e-13 78.63
TABLE7.2
Comparison for TN SSPD matrices between QS-qd and EIGSSD.
n EðabsÞ EðrelÞ QS-qd(sec) EðabsÞ EðrelÞ EIGSSD(sec)
10 1.8438e-14 1.8196e-15 0.10 2.4170e-14 2.3852e-15 0.17
50 7.5067e-14 4.2194e-15 1.98 1.4532e-13 1.2172e-14 4.39
100 6.4859e-14 3.0592e-15 6.40 2.0281e-12 9.5658e-14 16.66 200 3.5978e-13 9.3222e-15 10.05 1.5309e-12 3.9668e-14 31.09 300 4.4886e-13 8.2383e-15 10.71 1.2081e-12 2.2174e-14 22.60 400 4.6996e-13 8.9675e-15 21.38 1.6238e-12 3.0985e-14 48.55 500 6.4709e-13 1.0402e-14 39.42 6.0125e-10 9.6647e-12 76.97
TABLE7.3
Results for TN random matrices.
n niter EðabsÞ EðrelÞ QS-qd(sec)
10 37 3.3526e-15 4.8898e-16 0.38 50 239 5.6901e-14 3.5140e-15 0.56 100 488 1.3217e-13 6.0148e-15 1.65 200 993 2.2589e-13 7.3909e-15 4.62 300 1546 3.1303e-13 8.7152e-15 10.61 400 2080 3.0187e-13 7.6370e-15 19.29 500 2576 3.8896e-13 8.6375e-15 33.69 700 3812 6.1653e-13 1.1881e-14 68.83 1000 5689 9.5412e-13 1.4728e-14 135.19 6
eigenvalue approximated, we see, however, that the other eigenvalues are approximated very well. As we pointed out in section 5, the stability of QS-qd is not guaranteed for a generic symmetric matrix. However, the potentially dangerous subtraction of Algorithm 1 can only occur in the computation of the piat early steps of the process,
since at convergence migoes to zero. In Table 7.5 the results obtained on a particular
arrowhead matrix, with well-distributed eigenvalues, are reported. The algorithm in this case is fast and accurate despite the fact that the matrix is not TN.
Table 7.6 reports the behavior of the QS-qd method on a matrix with a couple of ill-conditioned eigenvalues. As test matrix we consider the inverse of the tridiagonal with
TABLE7.4
Relative errors for random TN matrices with the smallest eigenvalue equal toα. n α ¼ 10−3 α ¼ 10−4 α ¼ 10−5 α ¼ 10−6 α ¼ 10−8 α ¼ 10−16 100 3.0184e-13 2.1717e-12 2.4724e-11 8.8302e-11 8.1036e-09 8.9569e-02 200 4.1395e-13 8.3456e-13 5.5461e-11 1.6362e-10 1.2799e-08 2.3694e-01 300 6.8436e-13 7.4789e-12 3.8750e-11 2.7403e-10 7.9448e-08 4.9603e-01 400 1.7029e-13 2.1902e-12 2.3919e-11 1.4864e-09 1.7421e-08 2.7570e-01 500 4.5175e-13 6.0512e-12 1.0577e-11 3.3654e-10 2.6841e-08 7.9474e-01
0 50 100 150 200 250 300 350 400 450 500 10−16 10−14 10−12 10−10 10−8 10−6 10−4 10−2 100 102 Eigenvalues Relative Error
FIGURE7.1. Plot of the relative errors (in a logarithmic scale) of the computed eigenvalues of a randomly generated TN matrix of order 500 with an eigenvalue equal to 10−16.
TABLE7.5
An example of a matrix which is not TN. A¼ ðonesðnÞ þ diagð0∶n − 1ÞÞ−1. A is an arrowhead symmetric matrix.
n niter EðabsÞ EðrelÞ QS-qd(sec)
10 39 7.6328e-16 1.7383e-16 0.18 50 222 3.8659e-15 6.5444e-16 0.34 100 444 1.0880e-14 1.6580e-15 1.28 200 883 1.3769e-14 1.9065e-15 4.32 300 1314 1.1747e-14 1.5437e-15 9.56 500 2162 1.3649e-14 1.6849e-15 27.06
all entries equal to one, except for the entry (n, n− 1) equal to α. For this problem, the conditioning of the eigenvalues increases withα, but it does not depend on the size of the matrix. We see that accuracy slightly deteriorates asα increases.
Another interesting numerical experiment concerns the behavior of the method on a semiseparable matrix with clustered eigenvalues.7 We constructed a 100× 100
sym-metric semiseparable matrix whose eigenvalues are distributed according to Figure 7.2. Such a matrix has been constructed first generating a random orthogonal matrix Q and then constructing A¼ QDQT, where D is a diagonal matrix whose eigenvalues are
dis-tributed as follows: 20 eigenvalues geometrically disdis-tributed between 1 and 10−2, 20 eigenvalues between 5 · 10−3 and 5 · 10−5, and 60 eigenvalues between 2.5 · 10−5 and 2.5 · 10−7. We then reduced A to semiseparable form employing the algorithm proposed in [3] and available online athttp://www.cs.kuleuven.be/~mase/. We then computed, with MATLAB’s eig, the eigenvalues of the matrix obtained through this procedure, obtaining the values plotted in Figure 7.2, which differ slightly from the theoretical va-lues but are still clustered. Applying our method, we obtain a maximum relative error of
TABLE7.6
A¼ ðdiagðones½ðn − 2; 1Þ; α; −1Þ þ diagðones½ðn − 1; 1Þ; 1Þ þ eyeðnÞÞ−1. For different values of the para-meterα, the behavior of the relative error and of the maximum conditioning of the eigenvalues is reported.
n α ¼ 103 α ¼ 104 α ¼ 106 α ¼ 108 α ¼ 109 50 6.8360e-13 4.7427e-12 8.6504e-10 1.2536e-07 2.4598e-06 100 1.6239e-11 6.7904e-12 5.1840e-09 1.4151e-07 1.2406e-06 200 3.7919e-07 3.6445e-07 3.5502e-07 5.8907e-07 1.1434e-06 300 3.8272e-07 3.8317e-07 3.8699e-07 4.3830e-07 1.0376e-05 max(condeig) 15.8272 50.0050 5.0000e+02 5.0000e+03 1.5811e+04
0 10 20 30 40 50 60 70 80 90 100 10−7 10−6 10−5 10−4 10−3 10−2 10−1 100 101
FIGURE7.2. Logarithmic plot of the distribution of the eigenvalues of a semiseparable matrix of size 100.
7
2.9099e-10, while the mean error for all the eigenvalues was 6.5959e-12, suggesting a better behavior on the average.
On TN quasiseparable matrices, a comparison with the method (denoted by TridLR) described in section 6, which first reduces the matrix in tridiagonal form and then applies the method dqds [17] for tridiagonal matrices, is reported in Table 7.7. The comparison between the flops required by the tridiagonalization procedure followed by standard qd technique for tridiagonals (denoted, as mentioned before, as TridLR) and QS-qd seems to suggest that it is more convenient to first reduce the matrix into tridiagonal form. However, if one compares the time required by the two algorithms as reported in Table 7.7, we note that the times obtained are not those expected, while the accuracy is comparable. This suggests that the comparison of the times is more appro-priate than flop count since the interpreter or compiler—depending on the language the code is written in—can optimize the code to get faster execution times when the flop count would suggest a different behavior.8
8. Conclusions. In this paper two approaches to the computation of the eigenva-lues of a quasiseparable Neville-representable matrix have been proposed. The first one is a qd-type algorithm inspired by the qd methods for tridiagonal matrices. The second idea is to reduce the matrix to tridiagonal form and then apply a method for tridiagonal matrices, for instance, the same qd algorithm.
We have presented several theoretical results showing that the class of Neville-representable matrices is closed under LR steps. For TN matrices we proved also that the proposed algorithms are subtraction-free and breakdown-free, and, if a shift-preserving positivity is adopted, then each LR step produces a new matrix still TN.
Extensive numerical testing has been performed showing the effectiveness of this approach.
Acknowledgment. The authors are indebted to the two anonymous referees whose comments and suggestions helped improve the quality of the presentation.
TABLE7.7
For TN matrices, comparison between the two approaches proposed in this paper. The TridLR first applies the tridiagonalization procedure of section 6 and the steps of the dqds algorithm.
n EðabsÞ EðrelÞ TriLR(sec) EðabsÞ EðrelÞ QS-qd(sec) 10 3.3562e-15 7.2967e-16 0.17 6.2538e-15 1.3596e-15 0.10 50 3.7408e-14 3.1866e-15 0.78 3.6114e-14 3.0764e-15 0.38 100 9.8449e-14 4.4702e-15 2.26 1.1809e-13 5.3618e-15 1.35 200 2.1553e-13 7.0867e-15 8.74 2.5090e-13 8.2494e-15 4.69 400 2.4226e-13 6.3467e-15 39.96 3.1101e-13 8.1479e-15 21.79 600 3.3020e-13 6.5145e-15 80.22 4.8100e-13 9.4897e-15 49.92 800 3.9049e-13 7.1229e-15 149.61 7.0710e-13 1.2898e-14 91.31 1000 4.9826e-13 7.8901e-15 263.43 1.0501e-12 1.6629e-14 136.11
8
This has been verified executing the same code, using different MATLAB versions and different machines. In particular, with MATLAB Release 12, the algorithm TridLR is a bit faster than QS-qd, but for all the subsequent versions we tested, namely, MATLAB R2006B and MATLAB R2011B, the QS-qd outperformed TridLR.
