FOM accelerated by an extrapolation method for solving PageRank problems
| Autor: | Hong-Fan Zhang, Chun Wen, Zhao-Li Shen, Ting-Zhu Huang |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Speedup Applied Mathematics Extrapolation 010103 numerical & computational mathematics 01 natural sciences law.invention 010101 applied mathematics Computational Mathematics PageRank law Convergence (routing) Applied mathematics 0101 mathematics Orthogonalization Singular linear systems Mathematics |
| Zdroj: | Journal of Computational and Applied Mathematics. 296:397-409 |
| ISSN: | 0377-0427 |
| Popis: | This paper formulates the PageRank problem A x = x into a consistent singular linear system ( I - A ) x = 0 , and applies the full orthogonalization method (FOM) to solve it. This singular system is characterized by index one, namely i n d e x ( I - A ) = 1 . We analyze the breakdown performance of FOM on a general singular linear system, and conclude that FOM can determine a solution if it converges, without any unfortunate breakdowns for our target problem. Then we propose to use a vector extrapolation method to speed up the convergence performance of FOM. This extrapolation procedure is based on Ritz values, which directly stems from the Arnoldi-Extrapolation algorithm (Wu and Wei, 2010). Eventually numerical experiments are presented to illustrate the effectiveness of our approaches. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect