Efficient numerical methods to solve sparse linear equations with application to PageRank

A. Anikin, A. Gasnikov, A. Gornov, D. Kamzolov, Y. Maximov and Yurii Nesterov ()
Additional contact information
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3232, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: Over the last two decades, the PageRank problem has received increased interest from the academic community as an efficient tool to estimate web-page importance in information retrieval. Despite numerous developments, the design of efficient optimization algorithms for the PageRank problem is still a challenge. This paper proposes three new algorithms with a linear time complexity for solving the problem over a bounded-degree graph. The idea behind them is to set up the PageRank as a convex minimization problem over a unit simplex, and then solve it using iterative methods with small iteration complexity. Our theoretical results are supported by an extensive empirical justification using real-world and simulated data.

Keywords: Applied Mathematics; Control and Optimization; Software (search for similar items in EconPapers)
Pages: 29
Date: 2023-01-01
Note: In: Optimization Methods and Software, 2022, vol. 37(3), p. 907-935
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3232

DOI: 10.1080/10556788.2020.1858297

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().