Off-diagonal low-rank preconditioner for difficult PageRank problems
| Autor: | Xian-Ming Gu, Bruno Carpentieri, Ting-Zhu Huang, Zhao-Li Shen, Chun Wen, Xue-Yuan Tan |
|---|---|
| Přispěvatelé: | Computational and Numerical Mathematics |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
PageRank
Rank (linear algebra) Diagonal COMPUTING PAGERANK INVERSE 010103 numerical & computational mathematics LINEAR-SYSTEMS GMRES 01 natural sciences law.invention Matrix (mathematics) Low-rank factorization Factorization law ALGORITHM 0101 mathematics Coefficient matrix Matrix partition Mathematics Preconditioner EXTRAPOLATION METHOD Applied Mathematics Linear system Off-diagonal WEB 010101 applied mathematics Computational Mathematics Algorithm MATRIX SPLITTING ITERATION |
| Zdroj: | Journal of Computational and Applied Mathematics, 346, 456-470. ELSEVIER SCIENCE BV |
| ISSN: | 0377-0427 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect