A Preconditioned and Shifted GMRES Algorithm for the PageRank Problem with Multiple Damping Factors

DOI10.1137/110834585zbMath1263.65037OpenAlexW2080290181MaRDI QIDQ4903731

Gang Wu, Yanchun Wang, Xiao-qing Jin

Publication date: 24 January 2013

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/c575d36b6c98afb179334ff593bf18e5a1c47aa3

zbMATH Keywords

algorithmnumerical experimentslarge sparse linear systemcondition numberGMRESdirected graphpreconditionerPageRankWeb information retrievalill-conditionedshifted linear systemsGoogle

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Computational methods for sparse matrices (65F50) Searching and sorting (68P10) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical analysis or methods applied to Markov chains (65C40) Iterative numerical methods for linear systems (65F10) Directed graphs (digraphs), tournaments (05C20) Preconditioners for iterative methods (65F08)

Related Items

An efficient two-level preconditioner for multi-frequency wave propagation problems, On the convergence of the minimally irreducible Markov chain method with applications to PageRank, Off-diagonal low-rank preconditioner for difficult PageRank problems, Acceleration of an adaptive generalized Arnoldi method for computing PageRank, A GMRES-power algorithm for computing PageRank problems, Nested Krylov Methods for Shifted Linear Systems, Restarted Hessenberg method for solving shifted nonsymmetric linear systems, Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem, A new shifted block GMRES method with inexact breakdowns for solving multi-shifted and multiple right-hand sides linear systems, Truncated and sparse power methods with partially updating for large and sparse higher-order PageRank problems, A shifted block FOM algorithm with deflated restarting for matrix exponential computations, Block Krylov Subspace Methods for Functions of Matrices II: Modified Block FOM, A flexible and adaptive simpler GMRES with deflated restarting for shifted linear systems, Solving shifted linear systems with restarted GMRES augmented with error approximations, Krylov subspace recycling for sequences of shifted linear systems, An efficient elimination strategy for solving PageRank problems, PageRank computation with MAAOR and lumping methods, Block minimum perturbation algorithm based on block Arnoldi process for nonsymmetric linear systems with multiple right-hand sides, Flexible and deflated variants of the block shifted GMRES method, On restarted and deflated block FOM and GMRES methods for sequences of shifted linear systems, Efficient variants of the CMRH method for solving a sequence of multi-shifted non-Hermitian linear systems simultaneously, A preconditioned and extrapolation-accelerated GMRES method for pagerank, A Hessenberg-type algorithm for computing PageRank problems

Uses Software

• UF Sparse Matrix Collection