GRQM: A Robust And Fast Continuous Method For Extreme And Interior Eigenvalue Problems

Linear eigenvalue problems continue to be an important and relevant area of research in numerical linear algebra. The inherently nonlinear property leads to many computational problems. Except for particular cases, computation of the eigenvalues through the explicit construction of the characteristic equation is not an option since the coefficients of the equation can not be computed from determinant evaluations in a numerically stable way. Furthermore, even if the exact characteristic equation can be obtained, we could not compute the roots of the equation in the demanding precision. Perturbation theory indicates that small perturbation of the coefficients could lead to the big perturbation of the root. At the same time, numerically solving the eigenvectors is also a difficult task, especially for those with small angle between them. A clear conclusion is that all of the modern methods are of an iterative nature.Recently a continuous method has been proposed by G. H. Golub and L.-Z. Liao as an alternative way to solve both extreme and interior eigenvalue problems. However, this continuous method converges slowly, sometimes stagnates. Another problem is that it fails to work in some dense and ill-conditioned situations. In this paper, a new continuous method named gradient Rayleigh quotient method (GRQM) is proposed, which overcomes these deficiencies. GRQM is a combination of a rapidly convergent dynamical system (GRQ) and a linearly implicit Euler type ODE solver mixed with trust-region time step control (TRLIEM) . The main feature of GRQM is to use the Rayleigh quotient to update the Lagrange multiplier derived from a sequence of constrained optimization subproblems. Numerical experiments indicate also that the new method is usually faster and more robust.