# A New Algorithm for Solving Large-Scale Generalized Eigenvalue Problem Based on Projection Methods

Authors: F. Abbasi Nedamani; A. H. Refahi Sheikhani; H. Saberi Najafi
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we consider four methods for determining certain eigenvalues and corresponding eigenvectors of large-scale generalized eigenvalue problems which are located in a certain region. In these methods, a small pencil that contains only the desired eigenvalue is derived using moments that have obtained via numerical integration. Our purpose is to improve the numerical stability of the moment-based method and compare its stability with three other methods. Numerical examples show that the block version of the moment-based (SS) method with the Rayleigh–Ritz procedure has higher numerical stability than respect to other methods.


---

## Body

## 1. Introduction

Many problems arising in different fields of science and engineering can be reduced to the generalized eigenvalue problem [1–3]:(1)Ax=λBx,where A,B are n×n real or complex, large, sparse, and only a few of the eigenvalues are desired. Also, when is B=I (identity matrix), we have a standard eigenvalue problem. Computing eigenpairs λ,x of the generalized and standard eigenvalue problems is one of the important problems in many scientific applications [4–7]. There are several methods for solving such eigenvalue problems [8]. Among these methods, the iterative methods are used to generate a subspace that contains the desired eigenvectors. Techniques based on the Krylov subspaces are powerful tools for building desired subspaces for large-scale eigenvalue problems [9–11]. Expressed methods in this article find all of the zeros that lie in a circle using numerical integration. In this paper, we briefly describe moment-based method in Section 2, Rayleigh–Ritz with contour integral method in Section 3, block version of the Sakurai–Sugiura method in Section 4, and block version of the SS method with Rayleigh–Ritz procedure in Section 5 for solving generalized eigenvalue problem (1). In Section 6, we provide four numerical tests for comparing four methods, and in Section 6, we apply the BSSRR method with selected matrices from different application areas, and finally, we draw some conclusions in Section 7.


## 2. Moment-Based Method (SS Method)

For solving (1), we consider computing entire poles of a rational function:(2)fz=uHzB−A−1,v,u,v∈ℂn/0.Those are eigenvaluesλ of equation (1) and lie in a circle using numerical integration. Let Γ be positively oriented closed Jordan curve [12] in the complex plane and λ1,…,λn be distinct eigenvalues that lie in the Γ. Let(3)μk=12πi∫Γ−z−γkfzdz,k=0,1,…,where γ is located inside Γ and the m × m Hankel matrices Hm, Hm< be Hm=μi+j−2i,j=1m and Hm<=μi+j−1i,j=1m. Also, let(4)sk=12πi∫Γ−z−γkzB−A−1vdz,k=0,1,….Then, we have the following theorem.Theorem 1.
Ifvj=0 for 1≤j≤m, then the eigenvalues of the pencil Hm<−λHm are given byλ1−γ,…,λm−γ.Proof.
In [13], by approximating the integral of equation (3) via the N-point trapezoidal rule, we obtain(5)μk≈μ^k=1N∑j=0N−1ωj−γk+1fωj,k=0,1,….
Letξ1,…,ξm be the eigenvalues of pencil Hm<−λHm. We regard λ^j=γ+ξj,1≤j≤m as the approximations for λ^1,…,λ^m and(6)ωjB−Ayj=v,j=0,1,…,N−1,s^k=1N∑j=0N−1ωj−γk+1yj,k=0,1,….
Also, letV^m be the Vandermonde matrix for ξ1,…,ξm. Then, the approximations for the eigenvectors are obtained by(7)q^1,…,q^m=s^0,…,s^m−1V^m−T.


## 3. Rayleigh–Ritz with Contour Integral Method (CIRR Method)

We consider (1), let A,B∈ℝn×n be symmetric and let B be positive definite and λj,xj,1≤j≤n be eigenpairs of the matrix pencil A,B. We apply a Rayleigh–Ritz procedure with an orthonormal basis Q∈ℝn×m. The projected matrices are given by A˜=QTAQ and B˜=QTBQ. Q∈ℝn×m is used to generate a sequence of subspace containing approximations to the desired eigenvector. The Ritz values of the projected pencil A˜,B˜ are taken as approximate eigenvalues for original pencil A,B with corresponding Ritz vectors. In this method, by applying the Rayleigh–Ritz procedure moments are not explicitly used [17]. The algorithm is as follows.Rayleigh–Ritz procedure(1)
Construct an orthonormal basisQ(2)
FormA˜=QTAQ and B˜=QTBQ(3)
Compute the eigenpairsθj,ωj1≤j≤mof A˜,B˜(4)
Setpj=Qωj,j=1,…,MTheorem 2.
Letsk be defined by (4). Suppose that νis expanded by the eigenvectors x1,…,xn as(8)v=∑j=1nαjxj.
Then,(9)sk=∑j=1mαjλj−γkxj,j=0,1,…,m−1.Proof.
It follows from (4) and (8) that(10)sk=12πi∫Γ−∑j=1nαjz−γkzB−A−1Bxjdz.
Sinceλj,xj is an eigenpair of the matrix pencil A,B, we have zB−Axj=z−λjBxj and thus zB−A−1Bxj=z−λi−1xj, and thus(11)sk=∑j=1n12πi∫Γ−αjz−γkz−λjxjdz,k=0,1,…,m−1.
By the residue theorem, we obtain the result.
We define them×m Vandermonde matrix with λ1−γ,…,λm−γ by(12)V=1λ1−γ…λ1−γm−11λ2−γ…λ2−γm−1⋮⋮⋮⋮1λm−γ…λm−γm−1.
From the equation (9), we have(13)S=XDV,where S=s0,…,sm−1,X=x1,…,xm, and D=diagα1,…,αm.Theorem 3.
Ifλ1,…,λm are distinct and αj≠0 for 1≤j≤m, then(14)spanq1,…,qm=spanx1,…,xm.Proof.
Sinceλ1,…,λm are mutually distinct and αj≠0 for 1≤j≤m. V and D are nonsingular. Therefore, it follows from (13) that(15)spans0,…,sm−1=spanx1,…,xm.
Since the vectorsq1,…,qm are orthonormal basis of spans0,…,sm−1, equation (14) holds.For nonzero vectorv∈ℝn, we define the moments:(16)μk=12πi∫Γ−z−γkBvTzB−A−1Bvdz,k=0,1,…,where γ is located inside Γ. Also, we obtain the following approximations via the N-point trapezoidal rule:(17)μk≃μ^k=1N∑j=0N−1ωj−γk+1BvTωjB−A−1Bv,k=0,1,…,s^k=1N∑j=0N−1ωj−γk+1ωjB−A−1Bv,k=0,1,….


## 4. Block Sakurai–Sugiura Method (BSS Method)

In this method, for solving (1), we reformulate the SS method in the context of the resolvent theory. This method has the potential to resolve degenerated eigenvalues.Theorem 4.
LetzB−A be a regular pencil of order N. Then, there exist nonsingular matrices P˜,Q∈ℂN×N such that(18)P˜zB−AQ=zIk1−J1−−−−−−⋱−−−−−−zIkd−Jd−−−−−−zNd+1−Ikd+1−−−−−−⋱−−−−−−−zNr−Ikr,where Ji,Ni∈ℂki×ki are Jordan blocks, Ni is nilpotent, and Ik denotes the identity matrix of order k.
Proof. In [12].
Here, becauseP˜,Q are the regular matrices, we can define P=P˜−1 and Q˜=Q−1. According to the (18), we will partition row vectors in P˜ and Q˜ into P˜i,Q˜i∈ℂki×N, and column vectors in P and Q into Pi,Qi∈ℂN×ki, respectively, for i=1,…,r.Theorem 5.
Resolvent of the regular pencilzB−A−1 is decomposed into(19)zB−A−1=∑i=1dQi∑m=0ki−1Ji−αiIkimz−αim+1P˜i−∑i=d+1rQi∑m=0ki−1zmNimP˜i,where αi is an eigenvalue of Jordan block Ji.Proof.
LetW=P˜zB−AQ. According to Theorem 4, we have(20)zB−A−1=QW−1P˜=∑i=1dQizIki−Ji−1P˜i+∑i=d+1rQizNi−Iki−1P˜i.
Using the resolvent of the Jordan block,(21)Rz,Ji=zIki−Ji−1=∑m=0ki−1Ji−αiIkimz−αim+1
AndzNi−Iki−1=−z−1Rz−1,Ni, we get the result.Theorem 6.
The localized moment matrix is written as(22)Mn=∑i;αi∈GQiJinQ˜i.Proof.
In [18].Definition 1.
Let C and D be arbitraryN×m matrices, where N>m≥kΓ. A size-reduced moment matrix is defined as(23)Mn=CHMnD∈ℂm×m.Theorem 7.
If ranks of bothCHQΓ and Q˜ΓD are kΓ, nonsingular part of a matrix pencil zM0−M1is equivalent to zIkΓ−JΓ.Proof.
In [18].Theorem 8.
The right eigenvectors of the original matrix pencilzB−A are given by QΓ=M0DQΓ, and its adjoint is given by Q˜Γ=P˜ΓCHM0.Proof.
In [18].Theorem 9.
If all elements ofQ˜Γv and vHQΓ are nonzero, and there is no degeneracy in JΓ, then nonsingular part of a matrix pencil zHm−Hm< is equivalent to zIkΓ−JΓ.Proof.
By choosing row vectors ofCH and vectors of D to be(24)CHi,∗=vHQΓJΓi−1Q˜Γ.
AndDi,∗=QΓJΓi−1Q˜Γv for i=1,2,…,m , respectively, we have H=M0 and Hm<=M1. As for the rank of Q˜ΓD, we consider that column vectors of Q˜ΓD from the Krylov series of JΓ starting from Q˜Γv. Because JΓ has not degenerated, and elements of Q˜Γv are nonzero, these column vectors are linearly independent, and thus the rank of Q˜ΓD is fkΓ.


## 5. Block Version of the SS Method with the Rayleigh–Ritz Procedure (BSSRR Method)

We suggest a new algorithm for computing all poles of analytic function (2) with the use of the algorithm in [19]. As the eigenpairs λi,xi of equation (1) can be obtained from HM1ui=θiHM2ui, where HM1 and HM2 are small M×M Hankel matrices. Let V∈ℂn×l\0, a random matrix, and S=S0,S1,…,SM−1∈ℂn×LM, where(25)Sk=sk1,…,skL=12πi∮Γ1z−γkzB−A−1BVdz,k=0,1,…,M−1.Then, the block version of the SS method with Rayliegh–Ritz procedure [20] constructs the LM-dimensional subspace:(26)δM=spanS=spans01,…,s0L,s11,…,s1L,…,sM−11,…,sM−1L.For the Rayleigh–Ritz procedure, the subspaceδM contains all eigenvectors of (1) δM=spanx1,x2,…,xm for m≤LM. With using N-point trapezoidal rule for equation (25), we have(27)Sk≈S˜k=∑j=1Nωjzj−γkzjB−A−1BV.where zj is the quadrature point and ωj is the corresponding weight [21].Based on Theorem4, we analyse the relationship between the contour integral spectral projection and the Krylov subspace.


### 5.1. An Arnoldi-Based Interpretation of the Contour Integral Spectral Projection

Since the matricesP˜,Q are nonsingular, we define P=P˜−1,Q˜=Q−1. According to the Jordan block structure of (18), we partition row vectors in P˜,Q˜ into P˜i,Q˜i∈ℂni×n and column vectors in P,Q into Pi,Qi∈ℂn×ni, respectively, for i=1,2,…,r. Then, we can derive the following lemma and theorem.Lemma 1.
Letψkz be a k-degree polynomial. Then, we have(28)12πi∮Γ1ψkz−γzB−A−1Bdz=ψkSΓPΓ,where(29)SΓ=∑i:λi∈ΩQiJi−γIQ˜i,PΓ=∑i:λi∈ΩQiQ˜i.Proof.
From Theorem6 and the binomial theorem z−γℓ=∑j=0ℓℓjzℓ−jγj, we have the following relation:(30)12πi∮Γ1z−γℓzB−A−1Bdz=∑i:λi∈ΩQiJi−γIℓQ˜i,ℓ=0,1,….
Here, sinceQ˜iQi=I and Q˜iQj=0 for i≠j,(31)∑i:λi∈ΩQiJi−γIℓQ˜i=∑i:λi∈ΩQiJi−γIQ˜iℓ∑i:λi∈ΩQiQ˜i=SΓℓPΓ,ℓ=0,1,….
Therefore, Lemma1 is proved.Definition 2.
LetA∈ℂn×n, V=v1,v2,…,vL∈ℂn×L, and let κmA,v1 the Krylov subspace defined by(32)κmA,v1=spanv1,Av1,…,Am−1v1.
Then, the subspaceκm∗A,V is defined by the sum of the Krylov subspaces, i.e.,(33)κm∗A,V=κmA,v1+κmA,v2+⋯+κmA,vL=spanV,AV,…,Am−1V.Theorem 10.
Letδm be the subspace of the block version of the SS method with the Rayleigh–Ritz procedure defined by (26). Then, we have(34)δm=κm∗SΓ,PΓV.Proof.
From the definition ofSk (25) and Lemma 1, we have Sk=SΓkPΓV. Therefore,(35)δM=spanS0,S1,…,Sk=spanPΓV,SΓPΓV,…,SΓM−1PΓV=κM∗SΓ,PΓV.
Therefore, Theorem10 is proved.Remark 1.
Theorem10 shows that the block version of the SS method with the Rayleigh–Ritz procedure can be regarded as the Rayleigh–Ritz procedure based on the block Krylov subspace κM∗SΓ,PΓV. Here, we note that, in the block version of the SS method with the Rayleigh–Ritz procedure, the basis vectors of κM∗SΓ,PΓV are explicitly computed by (25) and the QR decomposition of S (Algorithm 1).
Andλi,xi=θi,Wui for i=1,2,…,LM.Algorithm 1:BSSRR method.
Input:L,M,N∈ℕ,V∈ℂn×L,γ,zj,ωj for j=1,2,…,NOutput: eigenpairsλi,xi for i=1,2,…,LM(1)
SolvezjB−AYj=BV for j=1,2,…,N,[14–16](2)
ComputeSk=∑j=1Nωjzj−γkYj for k=0,1,…,M−1(3)
Compute QR decomposition ofS=S0,S1,…,SM−1:S=WR(4)
Compute eigenpairsθi,ui of the matrix pencil WHAW,WHBW


## 5.1. An Arnoldi-Based Interpretation of the Contour Integral Spectral Projection

Since the matricesP˜,Q are nonsingular, we define P=P˜−1,Q˜=Q−1. According to the Jordan block structure of (18), we partition row vectors in P˜,Q˜ into P˜i,Q˜i∈ℂni×n and column vectors in P,Q into Pi,Qi∈ℂn×ni, respectively, for i=1,2,…,r. Then, we can derive the following lemma and theorem.Lemma 1.
Letψkz be a k-degree polynomial. Then, we have(28)12πi∮Γ1ψkz−γzB−A−1Bdz=ψkSΓPΓ,where(29)SΓ=∑i:λi∈ΩQiJi−γIQ˜i,PΓ=∑i:λi∈ΩQiQ˜i.Proof.
From Theorem6 and the binomial theorem z−γℓ=∑j=0ℓℓjzℓ−jγj, we have the following relation:(30)12πi∮Γ1z−γℓzB−A−1Bdz=∑i:λi∈ΩQiJi−γIℓQ˜i,ℓ=0,1,….
Here, sinceQ˜iQi=I and Q˜iQj=0 for i≠j,(31)∑i:λi∈ΩQiJi−γIℓQ˜i=∑i:λi∈ΩQiJi−γIQ˜iℓ∑i:λi∈ΩQiQ˜i=SΓℓPΓ,ℓ=0,1,….
Therefore, Lemma1 is proved.Definition 2.
LetA∈ℂn×n, V=v1,v2,…,vL∈ℂn×L, and let κmA,v1 the Krylov subspace defined by(32)κmA,v1=spanv1,Av1,…,Am−1v1.
Then, the subspaceκm∗A,V is defined by the sum of the Krylov subspaces, i.e.,(33)κm∗A,V=κmA,v1+κmA,v2+⋯+κmA,vL=spanV,AV,…,Am−1V.Theorem 10.
Letδm be the subspace of the block version of the SS method with the Rayleigh–Ritz procedure defined by (26). Then, we have(34)δm=κm∗SΓ,PΓV.Proof.
From the definition ofSk (25) and Lemma 1, we have Sk=SΓkPΓV. Therefore,(35)δM=spanS0,S1,…,Sk=spanPΓV,SΓPΓV,…,SΓM−1PΓV=κM∗SΓ,PΓV.
Therefore, Theorem10 is proved.Remark 1.
Theorem10 shows that the block version of the SS method with the Rayleigh–Ritz procedure can be regarded as the Rayleigh–Ritz procedure based on the block Krylov subspace κM∗SΓ,PΓV. Here, we note that, in the block version of the SS method with the Rayleigh–Ritz procedure, the basis vectors of κM∗SΓ,PΓV are explicitly computed by (25) and the QR decomposition of S (Algorithm 1).
Andλi,xi=θi,Wui for i=1,2,…,LM.Algorithm 1:BSSRR method.
Input:L,M,N∈ℕ,V∈ℂn×L,γ,zj,ωj for j=1,2,…,NOutput: eigenpairsλi,xi for i=1,2,…,LM(1)
SolvezjB−AYj=BV for j=1,2,…,N,[14–16](2)
ComputeSk=∑j=1Nωjzj−γkYj for k=0,1,…,M−1(3)
Compute QR decomposition ofS=S0,S1,…,SM−1:S=WR(4)
Compute eigenpairsθi,ui of the matrix pencil WHAW,WHBW


## 6. Numerical Experiments

In this section, we have provided five numerical examples. In Examples1–4, we have discussed stability Algorithm 2 (SS method), Algorithm 3 (CIRR method), Algorithm 4 (BSS method), and Algorithm 1 (BSSRR method), and in Example 5, we have applied the BSSRR method with selected matrices in the fields of engineering sciences. Also, we have used Axi+λiBxi2/Axi2+λiBxi2 to compute relative residual for all of the methods. In computational results tables, the number of eigenpairs has been named NE.Algorithm 2:SS method.
Input:u,v∈ℂn,N,m,γ,ρOutput:λ^1,…,λ^m,q^1,…,q^m(1)
Setωj⟵γ+ρ2πij/N,j=0,1,…,N−1(2)
SolveωjB−Ayj=v,j=0,1,…,N−1, [14–16](3)
Setfj⟵uHyj,j=0,1,…,N−1(4)
Computeμ^k,k=0,…,2m−1 by (5)(5)
Compute the eigenvaluesξ1,…,ξm of the pencil H^m<−λH^m(6)
Computeq^1,…,q^m by (7)(7)
Setλ^j⟵γ+ξj,j=1,…,mAlgorithm 3:CIRR method.
Input:v∈ℝn,N,M,γ,ρOutput:λ^1,…,λ^m,x^1,…,x^m(1)
Setωj=γ+ρexp2πij+1/2/N,j=0,1,…,N−1(2)
SolveωjB−Ayj=Bv for yj, j=0,1,…,N−1, [14–16](3)
Computes^k, k=0,1,…,M−1 by (17)(4)
Construct an orthonormal basisQ from s^0,…,s^M−1(5)
FormA˜=QTAQ and B˜=QTBQ(6)
Compute the eigenpairsθj,ωj1≤j≤Mof A˜,B˜(7)
Setpj=Qωj,j=1,…,M(8)
Select the approximate eigenpairsλ^1,x^1,…,λ^m,x^m from θj,pj1≤j≤MAlgorithm 4:BSS method.
Input:V∈ℂN×l,zj,ωj for j=1,2,…,MOutput:αk for k=1,2,…,K(1)
SolvezjB−AV˜j=BV [14–16] and calculate Vj=VHV˜j∈ℂl×l(2)
Computeμ¯n=∑j=1MωjzjnVj(3)
Construct Hankel matricesHm and Hm<∈ℂml×ml(4)
Perform singular value decomposition,Hm=WsU(5)
ConstructH=s−1/2WHHm<UHs−1/2∈ℂK×K(6)
Compute eigenvalues ofH to have αk(7)
ComputeS¯n=∑j=1MωjzjnV˜j(8)
ComputeQ1,…,QK=S¯0,…,S¯m−1UHs−1/2q1,…,qKExample 1.
A real symmetric matrixA∈ℝn×n was prepared, which has five primary eigenvalues −12.03, −12.02, −12.01, −12.00, −11.99. In the range of [−12.5, −11.5], other eigenvalues were taken randomly in the range of [−40, 40], and a random unitary matrix was prepared to construct A. An identity matrix was used for B. After applying Algorithms 1–4, we obtained numerical results that have been shown in Table 1.Table 1
The minimum relative residual of Algorithms1–4 in Example 1.
γ=−0.2+0.6i,ρ=0.5N.Am = 16,N = 32M = 18, N = 32 m = 16M = 32, m = 4, l = 4M = 4, L = 4, N = 32Threshold =1.1×10−18SSNECIRRNEBSSNEBSSRRNEn = 2000.82114168.8577E − 008161.9902E − 008167.9051E − 01616n = 4000.7919163.2359E − 06165.1353E − 09169.8608E − 1616n = 6000.8393163.2571E − 05161.1753E − 07161.3489E − 1516n = 8000.8665168.8640E − 05162.6448E − 05161.6268E − 1516n = 10000.8508167.7542EE − -05162.7825E − 05162.2567E − 1516n = 15000.8671165.6523E − 05168.7373E − 005161.9151E − 1516Example 2.
We let that A, B were complex, random matrices, and B was positive definite. After applying Algorithms1–4, we obtained numerical results that have been shown in Table 2. Also, the relative residual for described methods has been drawn in Figure 1 for n = 1000.Table 2
The minimum relative residual of Algorithms1–4 in Example 2.
γ=−0.1+0.5i,ρ=0.4N.A, N.Bm = 16, N = 32M = 18, N = 32 m = 16M = 32, m = 4, l = 4M = 4, L = 4, N = 32Threshold =1.1×10−14SSNECIRRBSSNEBSSRRNEn = 2000.930716—9.919E − 05166.1079E − 1616n = 4000.8955516—1.3066E − 04168.3165E − 1616n = 6000.892616—6.6731E − 004169.03555E − 1616n = 8000.880216—1.600E − 004168.6891E − 1616n = 10000.874916—3.2000–004161.2295E − 1516n = 15000.843216—1.6400E − 004161.9151E − 1516Figure 1
Results of comparing the relative residual of Algorithms1–4 in Example 2 with n = 1000.Example 3.
In this example, A, B were taken sparse, symmetric, and random, and A was positive definite. After applying Algorithms1–4, we obtained numerical results that have been shown in Table 3. Also, the relative residual for described methods has been drawn in Figure 2 for n = 1000.Table 3
The minimum relative residual of Algorithm1–4 and in Example 3.
γ=0,ρ=0.14N.A, N.Bm = 16, N = 64M = 18, N = 64 m = 16\M = 64, m = 4, l = 4M = 4, L = 4, N = 64Threshold =1.1×10−18SSNECIRRNEBSSNEBSSRRNEn = 2000.6600165.7595E − 13163.4279E − 1186.3585E − 1516n = 4000.6028167.2639E − 11166.1907E − 11103.1440E − 1516n = 6000.6509163.4114E − 11163.0774E − 09113.3606E − 1516n = 8000.5966166.2826E − 11163.0774E − 08128.2243E − 1516n = 10000.6065166.8571E − 10169.7887E − 08123.3916E − 1516n = 15000.6737163.6078E − 12167.9782E − 08112.3400E − 1516Figure 2
Results of comparing the relative residual of Algorithms1–4 in Example 3 with n = 1000.Example 4.
We consider matrices:(36)A=In,B=−7−3−1−1−1−1−3−8−3−1−1−1−1−3−8−3−1−1−1⋱⋱⋱⋱⋱−1−1−3−8−3−1−1−1−1−3−8−3−1−1−1−1−3−7,
After applying Algorithms1–4, we obtained numerical results that have been shown in Table 4. Also, the relative residual for described methods has been drawn in Figure 3 for n = 1000.Table 4
The minimum relative residual of Algorithms1–4 in Example 4.
γ=0,ρ=0.15N.A, N.Bm = 16, N = 32M = 18, N = 32 m = 16M = 32, m = 4, l = 4M = 4, L = 4, N = 32Threshold =1.1×10−14SSNECIRRNEBSSNEBSSRRNEn = 2000.7389160.0035160.0315162.4592E − 01516n = 4000.7350160.0057160.0337164.2091E − 1516n = 6000.7370160.0049160.0349165.2251E − 1516n = 8000.7389160.0068160.0323166.0494E − 1516n = 10000.7240160.0069160.0329166.4196E − 1516n = 15000.7393160.0065160.0384167.9371E − 1516Figure 3
Results of comparing the relative residual of Algorithms1–4 in Example 4 with n = 1000.Example 5.
In this example, we selected seventeen matrices from the UF sparse matrix collection. Two major requirements were used in the selection procedure: matrices with different parameters and matrices arising in different application areas were chosen. We consider the following symptoms parameters.
The order N, the number of nonzero elements NZ, and the condition number CON. The application areas of the selected matrices are listed in Table5. Matrices from the different areas were selected and thus obtained results by running the matrices will be typical in several scientific fields. We applied the BSSRR method for the calculation of relative residual generalized eigenvalue problem (1) when A is one of the selected matrices in Table 5 and B is identity matrix. As the dimension A, B is equal. We computed relative residual respect to −2 In Table 6 and computed respect to other norms in Table 7, too, the number of eigenpairs for each matrix was sixteen in Table 7.Table 5
Application areas, names, and properties 17 matrices selected.
ApplicationNameNNZCONGeneralized eigenvalue problemlund_a14724495.4430E + 006Generalized eigenvalue problemlund_b14724496.0317E + 004Chemical kineticsfs_183_11839981.5122E + 013Square dielectric wave guidedw256B51225004.5047Chemical kineticsfs_760_176057391.1234E + 016Large helicopter modelrotor2791106851.2651E + 013Dynamic analysis in structural engineeringbcsstk1981768532.8130E + 011Unsymmetric basis from LP problembp_160082248418.6511E + 006Power systems simulationqh882882479069.9827E + 024Oil reservoir simulationSherman1100037502.2575E + 004Aeroelasticitytols1090109035462.1164E + 006Alfven spectra in magneto hydrodynamicmdh12801280479069.9827E + 024Nuclear reactor modelsnnc261137485884.1082E + 015Dynamic analysis in structural engineeringbcsstk121473342415.2502E + 008Plasma physicsutm17001700215001.6380E + 007Splatzman symmetric finite difference three ocean modelPlat19191919323995.1323E + 018Dynamic analysis in structural engineeringbcsstk132003838834.5698E + 010Table 6
Calculation relative residual 2-norm of the BSSRR method.
γ=0,ρ=0.12,M=4,L=4,N=32BSSRRName matrixNEMinimum residualMaximum residualTimelund_a161.2115E − 0153.2651E − 0150.4351lund_b167.7260E − 0154.9013E − 0150.4034fs_183_1169.4890E − 0167.6258E − 0100.6897dw256 B163.0480E − 0151.13825E − 01337.9230fs_760_1161.9950E − 0151.1748E − 014114.1690rotor2162.9661E − 0157.6861E − 01173.6634bcsstk19161.7704E − 0154.3297E − 01580.9064bp_1600164.1415E − 0158.8643E − 015118.4747qh882168.3663E − 0118.1529E − 01091.1155Sherman1162.0279E − 0156.7531E − 015145.8976tols1090166.3521E − 151.0472E − 12174.7583mdh1280169.1528E − 0151.1804E − 012362.0046nnc261162.4955E − 0151.387E − 014362.3879bcsstk12161.7482E − 0154. 9099E − 015546.7578utm1700165.0652E − 0152.6436E − 014960.8218Plat1919163.1237E − 0151.2013E − 0131191.3179bcsstk13162.8611E − 0155.3720E − 0141363.4479Table 7
Calculation minimum relative residual of the BSSRR method with other norms.
γ=0,ρ=0.12,M=4,L=4,N=32BSSRRName matrix‖−‖1Time‖−‖∞Time‖−‖froTimelund_a1.6280E − 150.46411.464E − 0150.47511.0893E − 0150.4429lund_b1.2158E − 0150.43291.1523E − 0150.42899.5626E − 0160.4587fs_183_11.3389E − 0150.91601.9050E − 0150.99265.7331E − 0150.7920dw256B1.0643E − 01438.32474.8503E − 01538.51824.8285E − 01539.0655fs_760_11.4451E − 014115.76345.8661E − 015116.88769.4203E − 015116.0084rotor28.5274E − 01574.37943.6814E − 01579.67051.5234E − 01575.7969bcsstk194.6544E − 01583.63741.1299E − 01584.17061.6893E − 01583.6942bp_16005.6919E − 15119.67762.1991E − 015119.99963.3914E − 015123.9625qh8822.7482E − 01098.53871.8575E − 01093.94661.0929E − 01094.3459Sherman12.2421E − 014148.69589.1555E − 015147.35712.1974E − 015160.7665tols10906.4706E − 14203.01377.8958E − 14186.59228.0820E − -14175.2136mdh12801.1013E − 014357.01953.8742E − 015363.00946.2742E − 015357.0245nnc2612.8400E − 015391.51212.9017E − 015369.48313.2134E − 015363.7672bcsstk121.0533E − 014615.08518.1737E − 015624.60211.8975E − 015582.1993utm17001.1256E − 14985.16956.1700E − 0151031.46405.5940E − 015968.1327Plat19196.6578E − 0151173.13104.1980E − 0151294.08505.8991E − 0151296.4698bcsstk137.4671E − 0151366.75343.5188E − 0151408.81373.2373E − -0151385.8719


## 7. General Conclusions and Plans for Future Work

Several specific conclusions were drawn in connection with the numerical results presented in the previous section. Some general conclusions are given as follows:(1)
All numerical experiments indicate that CIRR, BSS, and BSSRR methods have higher stability than respect to the SS method(2)
BSSRR method has less relative residual respect to SS, CIRR, and BSS methods(3)
If−2 is used for calculation of relative residual in the BSSRR method, then we have higher accuracy and less consuming timeDesigning quadrature points with higher performance and a more precise error analysis of the BSSRR method is a part of our future work.



---

*Source: 8895856-2020-12-14.xml*