Off-diagonal low-rank preconditioner for difficult PageRank problemsShen, 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 journal › Article › Academic › peer-review
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.
|Number of pages||15|
|Journal||Journal of Computational and Applied Mathematics|
|Publication status||Published - 15-Jan-2019|
- PageRank, Off-diagonal, Low-rank factorization, Matrix partition, Preconditioner, MATRIX SPLITTING ITERATION, COMPUTING PAGERANK, EXTRAPOLATION METHOD, LINEAR-SYSTEMS, ALGORITHM, GMRES, INVERSE, WEB