The PageRank model, which was first proposed by Google for its web search engine application, has since become a popular computational tool in a wide range of scientific fields, including chemistry, bioinformatics, neuroscience, bibliometrics, social networks, and others. PageRank calculations necessitate the use of fast computational techniques with low algorithmic and memory complexity. In recent years, much attention has been paid to Krylov subspace algorithms for solving difficult PageRank linear systems, such as those with large damping parameters close to one. In this article, we examine the full orthogonalization method (FOM). We present a convergence study of the method that extends and clarifies part of the conclusions reached in Zhang et al. (J Comput Appl Math. 2016; 296:397–409.). Furthermore, we demonstrate that FOM is breakdown free when solving singular PageRank linear systems with index one and we investigate the effect of using weighted inner-products instead of conventional inner-products in the orthonormalization procedure on FOM convergence. Finally, we develop a shifted polynomial preconditioner that takes advantage of the special structure of the PageRank linear system and has a good ability to cluster most of the eigenvalues, making it a good choice for an iterative method like FOM or GMRES. Numerical experiments are presented to support the theoretical findings and to evaluate the performance of the new weighted preconditioned FOM PageRank solver in comparison to other established solvers for this class of problem, including conventional stationary methods, hybrid combinations of stationary and Krylov subspace methods, and multi-step splitting strategies.

Preconditioned weighted full orothogonalization method for solving singular linear systems from PageRank problems

Serra Capizzano S.;
2023-01-01

Abstract

The PageRank model, which was first proposed by Google for its web search engine application, has since become a popular computational tool in a wide range of scientific fields, including chemistry, bioinformatics, neuroscience, bibliometrics, social networks, and others. PageRank calculations necessitate the use of fast computational techniques with low algorithmic and memory complexity. In recent years, much attention has been paid to Krylov subspace algorithms for solving difficult PageRank linear systems, such as those with large damping parameters close to one. In this article, we examine the full orthogonalization method (FOM). We present a convergence study of the method that extends and clarifies part of the conclusions reached in Zhang et al. (J Comput Appl Math. 2016; 296:397–409.). Furthermore, we demonstrate that FOM is breakdown free when solving singular PageRank linear systems with index one and we investigate the effect of using weighted inner-products instead of conventional inner-products in the orthonormalization procedure on FOM convergence. Finally, we develop a shifted polynomial preconditioner that takes advantage of the special structure of the PageRank linear system and has a good ability to cluster most of the eigenvalues, making it a good choice for an iterative method like FOM or GMRES. Numerical experiments are presented to support the theoretical findings and to evaluate the performance of the new weighted preconditioned FOM PageRank solver in comparison to other established solvers for this class of problem, including conventional stationary methods, hybrid combinations of stationary and Krylov subspace methods, and multi-step splitting strategies.
2023
2023
https://doi.org/10.1002/nla.2541
FOM; Krylov subspace methods; PageRank; polynomial preconditioner; singular linear system
Shen, Z. -L.; Carpentieri, B.; Wen, C.; Wang, J. -J.; Serra Capizzano, S.; Du, S. -P.
File in questo prodotto:
File Dimensione Formato  
Numerical Linear Algebra App - 2023 - Shen - Preconditioned weighted full orothogonalization method for solving singular.pdf

non disponibili

Tipologia: Versione Editoriale (PDF)
Licenza: Copyright dell'editore
Dimensione 2.34 MB
Formato Adobe PDF
2.34 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11383/2164414
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact