A Hessenberg-type algorithm for computing PageRank problems

DOI10.1007/S11075-021-01175-WzbMATH Open1485.65037arXiv1908.00235OpenAlexW3187239659MaRDI QIDQ2118965FDOQ2118965

Yanyan Li

Publication date: 23 March 2022

Published in: Numerical Algorithms (Search for Journal in Brave)

Abstract: PageRank is a widespread model for analysing the relative relevance of nodes within large graphs arising in several applications. In the current paper, we present a cost-effective Hessenberg-type method built upon the Hessenberg process for the solution of difficult PageRank problems. The new method is very competitive with other popular algorithms in this field, such as Arnoldi-type methods, especially when the damping factor is close to $1$ and the dimension of the search subspace is large. The convergence and the complexity of the proposed algorithm are investigated. Numerical experiments are reported to show the efficiency of the new solver for practical PageRank computations.

Full work available at URL: https://arxiv.org/abs/1908.00235

zbMATH Keywords

Krylov subspace methodRitz valuesArnoldi processHessenberg processPageRank vector

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Iterative numerical methods for linear systems (65F10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• CMRH: A new method for solving nonsymmetric linear systems based on the Hessenberg reduction algorithm
• Numerical Methods for Large Eigenvalue Problems
• Deeper Inside PageRank
• Adaptive methods for the computation of PageRank
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• On a variable smoothing procedure for Krylov subspace methods
• A new look at CMRH and its relation to GMRES
• A Survey on PageRank Computing
• Flexible global generalized Hessenberg methods for linear systems with multiple right-hand sides
• Matrix Krylov subspace methods for linear systems with multiple right-hand sides
• The global Hessenberg and CMRH methods for linear systems with multiple right-hand sides
• Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems
• On computing PageRank via lumping the Google matrix
• Polynomial characterizations of the approximate eigenvectors by the refined Arnoldi method and an implicitly restarted refined Arnoldi algorithm
• An Inner-Outer Iteration for Computing PageRank
• An Arnoldi-Inout algorithm for computing PageRank problems
• A Power–Arnoldi algorithm for computing PageRank
• Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem
• An Arnoldi-type algorithm for computing Page Rank
• An Arnoldi-extrapolation algorithm for computing pagerank
• PageRank beyond the web
• A new extrapolation method for PageRank computations
• A Survey of Eigenvector Methods for Web Information Retrieval
• On adaptively accelerated Arnoldi method for computing PageRank
• A Reordering for the PageRank Problem
• Eigenvalue computations based on IDR
• A Preconditioned and Shifted GMRES Algorithm for the PageRank Problem with Multiple Damping Factors
• Google pageranking problem: The model and the analysis
• The $25,000,000,000 Eigenvector: The Linear Algebra behind Google
• Reducing a Matrix to Hessenberg Form
• A new implementation of the CMRH method for solving dense linear systems
• A refined subspace iteration algorithm for large sparse eigenproblems
• On the use of two QMR algorithms for solving singular systems and applications in Markov chain modeling
• Restarted Hessenberg method for solving shifted nonsymmetric linear systems
• The block Hessenberg process for matrix equations
• The block CMRH method for solving nonsymmetric linear systems with multiple right-hand sides
• Efficient variants of the CMRH method for solving a sequence of multi-shifted non-Hermitian linear systems simultaneously
• On certain methods for expanding the characteristic polynomial
• A restarted induced dimension reduction method to approximate eigenpairs of large unsymmetric matrices
• Newton generalized Hessenberg method for solving nonlinear systems of equations
• Weighted and flexible versions of block CMRH method for solving nonsymmetric linear systems with multiple right-hand sides
• Extended and rational Hessenberg methods for the evaluation of matrix functions
• On global Hessenberg based methods for solving Sylvester matrix equations

Cited In (8)

• The coupled iteration algorithms for computing PageRank
• Title not available (Why is that?)
• On efficient randomized algorithms for finding the PageRank vector
• An adaptively preconditioned multi-step matrix splitting iteration for computing PageRank
• Saddle point mirror descent algorithm for the robust PageRank problem
• An Arnoldi-type algorithm for computing Page Rank
• Distributed PageRank computation with improved round complexities
• Computing heat kernel PageRank and a local clustering algorithm

Uses Software

• CMRH

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• An Arnoldi-Inout algorithm for computing PageRank problems 👍 👎
• An Arnoldi-type algorithm for computing Page Rank 👍 👎
• An improved approach to the PageRank problems 👍 👎
• The coupled iteration algorithms for computing PageRank 👍 👎
• On efficient randomized algorithms for finding the PageRank vector 👍 👎
• A Sublinear Time Algorithm for PageRank Computations 👍 👎

This page was built for publication: A Hessenberg-type algorithm for computing PageRank problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118965)