A Restarting Generalized Second-order Krylov Subspace Method

In the paper,we study how to solve the quadratic eigenvalue problem:(λ~2M+λD+K)x=0. ,M,D,K are square matrice of N-order,we assume M is nonsigular.This problem has many applications,including the solution of the corresponding quadratic matrix equation:MX~2+DX+K=0.We first introduce a second-order Krylov subspace G_n{A,B,u) based on a pair of square matrice A and B and a vector u.And the second-order Arnoldi method is just a effective method based on this kind of subspace.It is usually used for solving the quadratic eigenvalue problem.It can preserve the original structures of the QEP and achieve the global convergence behaviors.However,the second-order Arnoldi method is difficult to restart.In the paper,we modify the generation way of a second-order Krylov subspace and the modified subspace is called the generalized second-order Krylov subspace. Then we derive a restart method based on the new subspace.We apply Morgan's restart thinking for our problem,i.e.,we preserve the number of Ritz vectors that is most closest to what we wanted in each step of the algorithm,then the new subspace is composed of two parts,one part is the base vectors which is produced by the most closest Ritz vector as the initial vector for the expansion of the subspace.The other part is the remaining Ritz vecters of the last step.And the new subspace will contain more information of our most wanted Ritz pair.We will achieve our purpose if we continue in the same way.Numerical examples demonstrate that the method is effective. The paper includes six parts.In the first part,the related background and the course of development is introduced.The basic methods to solve the large scale QEP problem is also included.In the second part,a second-order Krylov subspace is introduced and the generalized subspace is denned.Then the relationship of the both is found.In the third part,we briefly describe the generation of basis for generalized subspace.And we discuss the phenomenon of deflation and the breakdown and give the corresponding methods to cope with.In the fourth part,we directly apply the new subspace to solve the QEP.In the fifth part,we derive a method for restarting.The method can save the compuing time greatly.In the last part,we test four examples and the results show that the modified algorithm has better performace than the original.