Publication

Off-diagonal low-rank preconditioner for difficult PageRank problems

Shen, Z-L., Huang, T-Z., Carpentieri, B., Wen, C., Gu, X-M. & Tan, X-Y., 15-Jan-2019, In : Journal of Computational and Applied Mathematics. 346, p. 456-470 15 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

  • Off-diagonal low-rank preconditioner for difficult PageRank problems

    Final publisher's version, 456 KB, PDF document

    Request copy

DOI

  • Zhao-Li Shen
  • Ting-Zhu Huang
  • Bruno Carpentieri
  • Chun Wen
  • Xian-Ming Gu
  • Xue-Yuan Tan

PageRank problem is the cornerstone of Google search engine and is usually stated as solving a huge linear system. Moreover, when the damping factor approaches 1, the spectrum properties of this system deteriorate rapidly and this system becomes difficult to solve. In this paper, we demonstrate that the coefficient matrix of this system can be transferred into a block form by partitioning its rows into special sets. In particular, the off-diagonal part of the block coefficient matrix can be compressed by a simple low-rank factorization, which can be beneficial for solving the PageRank problem. Hence, a matrix partition method is proposed to discover the special sets of rows for supporting the low rank factorization. Then a preconditioner based on the low-rank factorization is proposed for solving difficult PageRank problems. Numerical experiments are presented to support the discussions and to illustrate the effectiveness of the proposed methods. (C) 2018 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)456-470
Number of pages15
JournalJournal of Computational and Applied Mathematics
Volume346
Publication statusPublished - 15-Jan-2019

    Keywords

  • PageRank, Off-diagonal, Low-rank factorization, Matrix partition, Preconditioner, MATRIX SPLITTING ITERATION, COMPUTING PAGERANK, EXTRAPOLATION METHOD, LINEAR-SYSTEMS, ALGORITHM, GMRES, INVERSE, WEB

View graph of relations

ID: 103307686