An Arnoldi-extrapolation algorithm for computing pagerank

DOI10.1016/J.CAM.2010.02.009MaRDI QIDQ989127zbMATH OpenOpenAlexFDO

Authors Gang Wu, Yimin Wei

Publication date 27 August 2010

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cam.2010.02.009

zbMATH Keywords

algorithmArnoldi methodconvergenceeigenvectorextrapolation methodGeneRankGoogle matrixKrylov subspace methodnumerical examplesPageRankRitz values

Mathematics Subject Classification ID

Iterative numerical methods for linear systems (65F10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Searching and sorting (68P10)

Review text

The authors aim at improving the PageRank algorithm which is commonly used to determine the global importance of Web pages. The algorithm essentially needs to compute the principal eigenvector of the Google matrix and is obviously required to be very efficient. To this end, the paper proposes a new Arnoldi-Extrapolation algorithm, based on the Arnoldi-type algorithm already presented in literature. An extrapolation method based on Ritz values is developed and then conveniently introduced into the Arnoldi-type algorithm. A detailed convergence analysis is provided. Some enlightening numerical examples show the very good properties of the proposed method.

Recommendations

• A new extrapolation method for PageRank computations
• A variant of the Power-Arnoldi algorithm for computing PageRank
• An Arnoldi-type algorithm for computing Page Rank
• An Arnoldi-Inout algorithm for computing PageRank problems
• A Power–Arnoldi algorithm for computing PageRank

Cites work

• A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity
• A Power–Arnoldi algorithm for computing PageRank
• A Reordering for the PageRank Problem
• A Survey of Eigenvector Methods for Web Information Retrieval
• A Survey on PageRank Computing
• Adaptive methods for the computation of PageRank
• Algorithms and Models for the Web-Graph
• An Arnoldi-type algorithm for computing Page Rank
• Comments on "Jordan Canonical Form of the Google Matrix"
• Convergence of Polynomial Restart Krylov Methods for Eigenvalue Computations
• Convergence of Restarted Krylov Subspaces to Invariant Subspaces
• Deeper Inside PageRank
• Eigenvalues and Jordan canonical form of a successively rank-one updated complex matrix with applications to Google's PageRank problem
• Eigenvalues of rank-one updated matrices with some applications
• Extrapolation methods for PageRank computations
• Fast PageRank Computation via a Sparse Linear System
• Further analysis of the Arnoldi process for eigenvalue problems
• Google pageranking problem: The model and the analysis
• Google's PageRank and beyond. The science of search engine rankings
• scientific article; zbMATH DE number 734901 (Why is no real title available?)
• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 961607 (Why is no real title available?)
• Jordan Canonical Form of the Google Matrix: A Potential Contribution to the PageRank Computation
• Krylov Subspace Methods for Solving Large Unsymmetric Linear Systems
• Matrix algorithms. Vol. 2: Eigensystems
• Monte Carlo Methods in PageRank Computation: When One Iteration is Sufficient
• Numerical range and functional calculus in Hilbert space
• On computing PageRank via lumping the Google matrix
• PageRank Computation, with Special Attention to Dangling Nodes
• Parallel iterative methods for sparse linear systems
• Rational extrapolation for the PageRank vector
• Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems
• Templates for the Solution of Algebraic Eigenvalue Problems
• The PageRank Vector: Properties, Computation, Approximation, and Acceleration
• Updating Markov Chains with an Eye on Google's PageRank

Cited in

(42)

• Off-diagonal low-rank preconditioner for difficult PageRank problems
• A GMRES-power algorithm for computing PageRank problems
• An Arnoldi-Inout method accelerated with a two-stage matrix splitting iteration for computing PageRank
• Multipreconditioned GMRES for simulating stochastic automata networks
• Extrapolation methods for PageRank computations
• The general inner-outer iteration method based on regular splittings for the PageRank problem
• A multi-power and multi-splitting inner-outer iteration for PageRank computation
• An extrapolation iteration and its lumped type iteration for computing PageRank
• The coupled iteration algorithms for computing PageRank
• A Hessenberg-type algorithm for computing PageRank problems
• Acceleration of the generalized FOM algorithm for computing PageRank
• Acceleration of an adaptive generalized Arnoldi method for computing PageRank
• A simpler GMRES algorithm accelerated by Chebyshev polynomials for computing PageRank
• Accelerating the Arnoldi method via Chebyshev polynomials for computing PageRank
• A variant of the Power-Arnoldi algorithm for computing PageRank
• An adaptive Power-GArnoldi algorithm for computing PageRank
• A general multi-splitting iteration method for computing PageRank
• A preconditioned and extrapolation-accelerated GMRES method for pagerank
• Triangular and skew-symmetric splitting method for numerical solutions of Markov chains
• The PageRank model of minimal irreducible adjustment and its lumping method
• On the multi-splitting iteration method for computing PageRank
• Shifted power-GMRES method accelerated by extrapolation for solving pagerank with multiple damping factors
• An adaptively preconditioned multi-step matrix splitting iteration for computing PageRank
• Extrapolation for solving a system of weakly singular nonlinear Volterra integral equations of the second kind
• An Arnoldi-Inout algorithm for computing PageRank problems
• A new extrapolation method for PageRank computations
• An adaptive reordered method for computing PageRank
• Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem
• The extrapolation-accelerated multilevel aggregation method in PageRank computation
• A two-step matrix splitting iteration for computing PageRank
• Extrapolating the Arnoldi algorithm to improve eigenvector convergence
• The modified matrix splitting iteration method for computing PageRank problem
• Extrapolation methods for fixed‐point multilinear PageRank computations
• Axiomatic characterization of PageRank
• Effective Computation of a Feedback Arc Set Using PageRank
• The MFPIO iteration and the FPMPE method for multilinear PageRank computations
• Extrapolation methods for multilinear PageRank
• A note on the pagerank algorithm
• An Arnoldi-type algorithm for computing Page Rank
• FOM accelerated by an extrapolation method for solving PageRank problems
• Eigenvalues and Jordan canonical form of a successively rank-one updated complex matrix with applications to Google's PageRank problem
• Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations

Describes a project that uses

Uses Software

• JDQZ
• JDQR
• GeneRank

This page was built for publication: An Arnoldi-extrapolation algorithm for computing pagerank

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