Open AccessAcceleration of the generalized FOM algorithm for computing PageRank
Author(s) -
Yu Jin,
Chun Wen,
ZhaoLi Shen
Publication year - 2022
Publication title -
electronic research archive
Language(s) - English
Resource type - Journals
ISSN - 2688-1594
DOI - 10.3934/era.2022039
Subject(s) - extrapolation , orthogonalization , pagerank , convergence (economics) , acceleration , intersection (aeronautics) , algorithm , computer science , power iteration , benchmark (surveying) , implementation , power (physics) , mathematics , theoretical computer science , iterative method , engineering , physics , mathematical analysis , classical mechanics , aerospace engineering , quantum mechanics , economics , economic growth , geodesy , geography , programming language
In this paper, a generalized full orthogonalization method (GFOM) based on weighted inner products is discussed for computing PageRank. In order to improve convergence performance, the GFOM algorithm is accelerated by two cheap methods respectively, one is the power method and the other is the extrapolation method based on Ritz values. Such that two new algorithms called GFOM-Power and GFOM-Extrapolation are proposed for computing PageRank. Their implementations and convergence analyses are studied in detail. Numerical experiments are used to show the efficiency of our proposed algorithms.