DOI: https://doi.org/10.26089/NumMet.v17r105

An orthogonal power method of solving the partial eigenproblem for a symmetric nonnegative definite matrix

Authors

  • I.V. Kireev

Keywords:

eigenvector
eigenvalue
conjugate direction method
Krylov subspaces

Abstract

An efficient version of the conjugate direction method to find a nontrivial solution of a homogeneous system of linear algebraic equations with a singular symmetric nonnegative definite square matrix is proposed and substantiated. A one-parameter family of one-step nonlinear iterative processes to determine the eigenvector corresponding to the largest eigenvalue of a symmetric nonnegative definite square matrix is also proposed. This family includes the power method as a special case. The convergence of corresponding vector sequences to the eigenvector associated with the largest eigenvalue of the matrix is proved. A two-step procedure is formulated to accelerate the convergence of iterations for these processes. This procedure is based on the orthogonalization in Krylov subspaces. A number of numerial results are discussed.

New computational technologies

Downloads

Published

2016-02-13

Issue

Vol. 17 (2016): Issue 1.

Section

Section 1. Numerical methods and applications

Author Biography

I.V. Kireev

Institute of Computational Modeling of SB RAS (ICM SB RAS)
• Associate Professor

References

  1. D. K. Faddeev and V. N. Faddeeva, Computational Methods of Linear Algebra (Lan’, St. Petersburg, 2002; Freeman, San Francisco, 1963).
  2. G. H. Golub and H. A. van der Vorst, “Eigenvalue Computation in the 20th Century,” J. Comput. Appl. Math. 123 (1-2), 35-65 (2000).
  3. D. S. Watkins, The Matrix Eigenvalue Problem: GR and Krylov Subspace Methods (SIAM, Philadelphia, 2007).
  4. V. V. Voevodin and Yu. A. Kuznetsov, Matrices and Computations (Nauka, Moscow, 1984) [in Russian].
  5. S. K. Godunov, Modern Aspects of Linear Algebra (Nauchnaya Kniga, Novosibirsk, 1997; Amer. Math. Soc., Providence, 1998).
  6. G. Meurant and Z. Strakoš, “The Lanczos and Conjugate Gradient Algorithms in Finite Precision Arithmetic,” Acta Numer. 15, 471-542 (2006).
  7. I. V. Kireev, “Inexpensive Stopping Criteria in the Conjugate Gradient Method,” Vychisl. Tekhnol. 20 (2), 44-55 (2015).
  8. V. V. Voevodin, Linear Algebra (Nauka, Moscow, 1980) [in Russian].
  9. V. V. Voevodin, Numerical Methods of Algebra: Theory and Algorithms (Nauka, Moscow, 1966) [in Russian].
  10. J. H. Wilkinson, The Algebraic Eigenvalue Problem (Clarendon, Oxford, 1965; Nauka, Moscow, 1970).
  11. B. N. Parlett, The Symmetric Eigenvalue Problem (Prentice-Hall, Englewood Cliffs, 1980; Nauka, Moscow, 1983).
  12. H. L. Leslie (Ed.), Discrete Mathematics and Its Applications. Handbook of Linear Algebra (CRC Press, Boca Raton, 2014).
  13. E. E. Ovtchinnikov, “Computing Several Eigenpairs of Hermitian Problems by Conjugate Gradient Iterations,” J. Comput. Phys. 227 (22), 9477-9497 (2008).
  14. V. I. Gorbachenko, Computational Linear Algebra with Examples in MATLAB (BKhV Press, St. Petersburg, 2011) [in Russian].