# A Method of Indefinite Krylov Subspace for Eigenvalue Problem

Authors: M. Aliyari; M. Ghasemi Kamalvand
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We describe an indefinite state of Arnoldi’s method for solving the eigenvalues problems. In the following, we scrutinize the indefinite state of Lanczos’ method for solving the eigenvalue problems and we show that this method for theJ-Hermitian matrices works much better than Arnoldi’s method.


---

## Body

## 1. Introduction

Around the early 1950s the idea of Krylov subspace iteration was established by Cornelius Lanczos and Walter Arnoldi. Lanczos’ method was based on two mutually orthogonal vector sequences and his motivation came from eigenvalue problems. In that context, the most prominent feature of the method is that it reduces the original matrix to tridiagonal form. Lanczos later applied his method to solve linear systems, in particular symmetric ones. Krylov subspace iterations or Krylov subspace methods are iterative methods which are used as linear system solvers and also iterative solvers of eigenvalue problems.On the other hand, the indefinite inner product defined byJ=diagj1,…,jn, jk∈-1,+1, arises frequently in applications. It is used, for example, in the theory of relativity and in the research of the polarized light. More on the applications of such products can be found in [1–6]. These applications in other fields of science inspired us to resume Lanczos, FOM, and Arnoldi’s methods in this mentioned indefinite inner space. Indefinite Arnoldi’s method is a process that constructs a J-orthonormal basis for the nondegenerated Krylov subspace; the basis that we proved have a particular common property, about the structure of the product of their vectors. In the following, iterative Arnoldi’s method for eigenvalue problem has been renovated in the mentioned indefinite inner product space and also a process is made which is useful for solving eigenvalue problem with J-Hermitian coefficient matrices. Indefinite iterative Lanczos’ method for eigenvalue problem is the same as Lanczos’ method that has been restored in the indefinite inner product space.This paper is organized as follows: In Section2, we recall the standard inner product and indefinite inner product in Cn. In the following part of this section we show some examples on indefinite inner product that will guide us to the objectives of this article. We express the indefinite Arnoldi algorithm for the computation of a J-orthonormal basis of the Krylov subspace and describe property of the basis in the form of several propositions to review and in the end of this section we exhibit the indefinite version of the Hermitian Lanczos algorithm.In Section3, we present a definition of the Ritz eigenpair of the a matrix and new algorithms from the indefinite Arnoldi and Lanczos’ algorithm that is named modified methods by the Ritz approximation in the indefinite Arnoldi and Lanczos’ process. This is our main goal and initiative in this article.Since the initial vectors are very important at the start of each iteration to the above algorithms, in this article, we consider the Ritz eigenvector instead of the common eigenvector in the start of the each repetition algorithm. In Section4 we present numerical examples and compare the modified method by the Ritz approximation in the Arnoldi and indefinite Lanczos algorithm. Algorithms are written with personal computer using MATLAB software and we illustrate examples by using these codes.


## 2. Indefinite Arnoldi and Lanczos Algorithms

LetCn be the n-dimensional space consisting of all column vectors x with complex coordinates xi, i=1,2,…,n. The standard inner product in Cn is denoted by ·,·. Thus (1)x,y=∑i=1nxiy¯i,where x=x1,…,xnT and y=y1,…,ynT and the bar denotes the complex conjugation. Remember that a function ·,· from Cn×Cn to C is called an indefinite inner product in Cn if the following axioms are satisfied: (i)
Linearity in the first argument:(2)αx1+βx2,y=αx1,y+βx2,y,for allx1,x2,y∈Cn and all complex numbers α, β.(ii)
Antisymmetry:(3)x,y=y,x¯.Example 1.
Letx=x1,…,xnT, y=y1,…,ynT∈Cn and define (4)x,y=∑i=1rxσiy¯σi-∑i=r+1nxσiy¯σi,where σ is a permutation for which σi=ji and ji∈1,…,n. It is easy to see that ·,· is an indefinite inner product. Indeed, i,ii properties are clearly confirmed. But for nondegeneracy property, if x,y=0 for all y∈Cn, then in special case, x,y=0 for y=y1,…,ynT, where (5)yσi=xσii=1,…,r;-xσii=r+1,…,k,by choosing an appropriate permutation σ.
Thus,(6)∑i=1rx¯σixσi--∑i=r+1nx¯σixσi=∑i=1rxσi2+∑i=r+1nxσi2=∑i=1nxσi2=0,and this yields that xi=0, for i=1,…,n. So, x=0.By [3], we know that, for every n×n invertible Hermitian matrix H, the formula (7)x,y=Hx,y,x,y∈Cndetermines an indefinite inner product on Cn and conversely for every indefinite inner product ·,· on Cn there exists an n×n invertible and Hermitian matrix H such that (7) holds and the established correspondence ·,·↔H is a bijection between the set of all indefinite inner products on Cn and the set of all n×n invertible Hermitian matrices.Example 2.
In Example (7), the corresponding nonsingular Hermitian matrix to that indefinite inner product is written in the form J=diag±1 wherein r is the number of +1 and n-r is the number of -1. This is because if (8)x,y=Jx,y,then (9)x,y=Jx,y=y∗Jx=y-1,…,y-nTJx1,…,xn=∑i=1rxσiy¯σi-∑i=r+1nxσiy¯σi,and conversely if (10)x,y=∑i=1rxσiy¯σi-∑i=r+1nxσiy¯σi,then it is clear that x,y=Jx,y, for all x,y∈Cn.Note. For x=x1,…,xnT, consider the relation x,x=x∗Jx.That the result becomes zero is a very special case and depends on how we choose the matrixJ.Recently, new algorithms have been presented in this regard and have been compared in terms of the number of replays and the time required to run algorithms.These methods could solve the linear systems of equations withJ-Hermitian coefficient matrices and also considered Arnoldi, FOM, and Lanczos’ methods for solving linear system of equations and resumed these methods in a space that is equipped with a special indefinite inner product and proposed new algorithms to run these methods. The indefinite Arnoldi algorithm for the computation of a J-orthonormal basis of the Krylov subspace(11)KmA,v0=spanv0,Av0,A2v0,…,Am-1v0,where A is n×n matrix and vi’s are n×1 vectors, is shown below: (1)
Choose a vectorx such that x,x≠0(2)
Definev1=x/x,x(3)
Forj=1,…,m Do:(4)
Fori=1,…,j Do:(5)
Computehij≔Avj,vi and tvi=vi,vi(6)
Computewj≔Avj-∑i=1jtvihijvi(7)
hj+1,j=wj,wj(8)
ifhj+1,j=0 then stop(9)
vj+1=wj/hj+1,j(10)
EndDo(11)
EndDoHereHm is an upper Hessenberg matrix.The following proposition expressed indefinite Arnoldi’s algorithm. (You can see [7, 8].)Proposition 3.
Assume that the indefinite Arnoldi algorithm does not stop before themth step. Then the vectors v1,…,vm form a J-orthonormal basis of the Krylov subspace KmA,v.Proof.
Consider the following expression:(12)hj+1,jvj+1=Avj-∑i=1jtvihijvi,j=1,…,m.Certainly that vectors v1,…,vm are J-orthonormal.Proposition 4.
Define(i)
Hm, the m×m Hessenberg matrix whose nonzero entries hij are defined by indefinite Arnoldi’s algorithm,(ii)
Vm, the n×m matrix with column vectors v1,…,vm,(iii)
J´=diagtv1,…,tvm.
Then the following relations are valid:(13)AVm=VmJ´Hm+hm+1,mvm+1emT,(14)Vm∗JAVm=Hm.In particular, if m=n then (15)Vn-1AVn=J´Hn.Proof.
By considering lines(4), (5), and 7 of indefinite Arnoldi’s algorithm, relation (13) is verified straightforwardly. Indeed, in general, (13) is the matrix representation of (12): (16)AVm=VmJ´Hm+wmemT=VmJ´Hm+hm+1,mvm+1emT=VmJ´∣vm+1Hm0,…,0,hm+1,m.Now, to see (14), left-multiply the relation (16) in Vm∗J. We earn (17)Vm∗JAVm=Vm∗JVmJ´Hm+hm+1,mVm∗Jvm+1emT.On the other hand, given that the vectors v1,…,vm build a J-orthonormal basis, then, we have the following. (1)
According to the definition ofvm+1, vm+1=0 or it is orthogonal to v1,…,vm, that is, vm+1,vi=vi∗Jvm+1=0, for i=1,…,m. Thus, (18)Vm∗Jvm+1=0.(2)
We have(19)Vm∗JVm=vi,vji,j=diagv1,v1,…,vm,vm=J´.In other words,J´Vm∗JVm=I.
Therefore, relation (17) can be summarized as follows: (20)Vm∗JAVm=Hm,and, by left-multiplying in J´, (21)J´Vm∗JAVm=J´Hm.Particularly, if m=n, relation (19) yields that J´Vn∗J=Vn-1 and thereby (22)Vn-1AVn=J´Hn.Remark 5.
It should be noted that a permutation matrixP is available such That (23)PJP=J´.We know that the indefinite Hermitian Lanczos algorithm is a simplified version of the indefinite Arnoldi algorithm that is applied to J-Hermitian matrices. The mth step of the algorithm transforms matrix A into a Hessenberg and J-Hermitian matrix, in other words, a tridiagonal matrix Tm; when m is equal to the dimension of A, Tm is similar to A. To see more, refer to [7–10]. As can be seen in the following, this method is expressed as a special case of the indefinite Arnoldi method in the complex space for the special case when matrix A is J-Hermitian.The indefinite version of the Hermitian Lanczos algorithm can be formulated as follows:(1)
Choose an initial vectorv1 such that v1,v1=±1(2)
Setβ1≡0,v0=0(3)
Forj=1,…,m Do:(4)
ωj≔Avj-tvj-1βjvj-1(5)
αj≔ωj,vj(6)
ωj≔ωj-tvjαjvj(7)
ifωj,ωj=0 then stop(8)
vj+1=wj/ωj,ωj(9)
βj+1≔tvj+1ωj,ωj(10)
EndDo


## 3. Indefinite Iterative Arnoldi’s Method for Eigenvalue Problem

Definition 6.
Suppose thatA,J′,Hm, and Vm are the same as those in Proposition (8), let λim,yim be an eigenpair of Hm,
λ i ( m ) is called Ritz value of A and provides an approximation for eigenvalue of A.
u i ( m ) = V m y i m is called Ritz vector of A and provides an approximation for eigenvector of A.Proposition 7.
Letyim be an eigenvector of J′Hm associated with the eigenvalue λim and uim the Ritz approximate eigenvector, so that uim=Vmyim. Then, (24)A-λimIuim=hm+1,memTyimvm+1.Proof.
Letui(m)=Vmyi(m) and Jm′Hmyi(m)=λi(m)yi(m). We have(25)AVmyim=VmJm′Hm+hm+1,mvm+1emTyimAVmyim=VmJm′Hmyim+hm+1,mvm+1emTyimAVm-λimVmyim=hm+1,memTyimvm+1A-λimIVmyim=hm+1,memTyimvm+1A-λimIuim=hm+1,memTyimvm+1.One of way to circumvent the difficulty is to restart the algorithm. After a run withm Arnoldi and Lanczos’ vectors, we compute the approximate eigenvector and use it as an initial vector for the next run with Arnoldi and Lanczos’ methods. This process, which is the simplest of this kind, is iterated to convergence. The iterative indefinite Arnoldi algorithm can be formulated as follows:(1)
Start: choose an initial vectorv1 and a dimension m.(2)
Iterate: performm steps of indefinite Arnoldi’s algorithm.(3)
Restart: compute the approximate eigenvectoru1m associated with the rightmost eigenvalue λ1m.If satisfied stop; else setv1≡u1(m) and go to (2).Of course, it should be noted that this algorithm is not beneficial for us, because in any case it is better to use the definite algorithm.In the following we have the same iterative indefinite Lanczos algorithm which can be formulated as follows:(1)
Start: choose an initial vectorv1 and a dimension m.(2)
Iterate: performm steps of indefinite Lanczos’ algorithm.(3)
Restart: compute the approximate eigenvectoru1(m) associated with the rightmost eigenvalue λ1m.If satisfied stop; else setv1≡u1m and go to (2).This algorithm is used forJ-symmetric matrices, since the number of flops in the performance of algorithm is certainly less than that of the Arnoldi algorithm. This is illustrated by the examples in the next section.


## 4. Numerical Example

In this section, we present numerical examples and compare the methods modified by the Ritz approximation in the Arnoldi and indefinite Lanczos process.Algorithms are written with personal computer using MATLAB software and the following examples are done using these codes.Example 1.
Consider the matricesJ=I00-I and A=A11A12A21A22, where A11,A22 are diagonal matrices with random elements in 0,1 and also A12, A21 are tridiagonal matrices with random elements in 0,1 such that A12=-A21T and v is n×1 vector with random entries in (0,1).
Letv1=v/|[v,v]|; in this case n=100, m=50. The results are in Table 1.Table 1 Method Iteration Time e Arnoldi 1 0.31 6 × 1 0 - 14 Indefinite Lanczos 1 0.28 1 × 1 0 - 13 Heree=A-λimIuim2.Example 2.
Consider the matrices(26)J=In/10,-In/10,In/10,-In/10,In/10,-In/10,In/10,-In/10,In/10,-In/10,where I is identity matrix and A∈Mn in the form (27)A=A11A12A13A14A15A16A17A18A19A1,10A21A22A23A24A25A26A27A28A29A2,10A31A32A33A34A35A36A37A38A39A3,10A41A42A43A44A45A46A47A48A49A4,10A51A52A53A54A55A56A57A58A59A5,10A61A62A63A64A65A66A67A68A69A6,10A71A72A73A74A75A76A77A78A79A7,10A81A82A83A84A85A86A87A88A89A8,10A91A92A93A94A95A96A97A98A99A9,10A10,1A10,2A10,3A10,4A10,5A10,6A10,7A10,8A10,9A10,10
such that(28)-Ai,i+1T=Ai+1,ifori=1:9,Ai,i+2T=Ai+2,ifori=1:8-Ai,i+3T=Ai+3,ifori=1:7,Ai,i+4T=Ai+1,ifori=1:6-Ai,i+5T=Ai+5,ifori=1:5,Ai,i+6T=Ai+6,ifori=1:4-Ai,i+7T=Ai+7,ifori=1:3,Ai,i+8T=Ai+8,ifori=1:2-Ai,i+9T=Ai+9,ifori=1,wherein Aij, i,j=1:10, are diagonal matrices with random elements (entries) in 0,1.
In this case,(i)
ifn=50,m=30, the results are in Table 2;(ii)
ifn=200,m=50; the results are in Table 3.Table 2 Method Iteration Time e Arnoldi 5 1.25 3.2 × 10 - 8 Indefinite Lanczos 3 0.64 4.3 × 10 - 6Table 3 Method Iteration Time e Arnoldi 1 0.27 4.6 × 10 - 10 Indefinite Lanczos 1 0.14 2.6 × 10 - 8 Heree=A-λimIuim2.It should be noted that obviously the number of external iterations depends on the number of internal iterations selected. The larger them value is taken, the more the external iterations will decrease.


## 5. Conclusion

We know that the matrices ofJ-Hermitian are important and functional matrices. We can find a way to find the eigenvalues of these types of matrices that are more efficient than Arnoldi’s method. To do this, we first constructed an indefinite Arnoldi method in order to be able to also make that indefinite Lanczos method. We tried to study and compare the Arnoldi and indefinite Lanczos methods. It was observed that Arnoldi’s method is not efficient in indefinite status, but the indefinite Lanczos method for J-symmetric (Hermitian) matrices is much better than Arnoldi’s method.



---

*Source: 2919873-2018-05-16.xml*