A note on Lanczos algorithm for computing pagerank

Kazuma Teramoto; Takashi Nodera

doi:10.5176/2251-1911_CMCGS14.15_3

A note on Lanczos algorithm for computing pagerank

Kazuma Teramoto, Takashi Nodera

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

We now study the Lanczos algorithm for computing the PageRank vector. This algorithm is based on biorthogonalization, which transforms a nonsymmetric matrix into a tridiagonal matrix to compute PageRank. This generates better approximation of the largest eigenvalue at early stage of iterations. We propose a practical scheme of the Lanczos biorthogonalization algorithm with SVD scheme for computing PageRank. Numerical results show that the proposed algorithm converges faster than the existing Arnoldi method in the computation time.

Original language	English
Title of host publication	Springer Proceedings in Mathematics and Statistics
Publisher	Springer New York LLC
Pages	25-33
Number of pages	9
Volume	124
ISBN (Print)	9783319161389
DOIs	https://doi.org/10.5176/2251-1911_CMCGS14.15_3
Publication status	Published - 2016
Event	3rd Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, CMCGS 2014 - Singapore, Singapore Duration: 2014 Feb 3 → 2014 Feb 4

Other

Other	3rd Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, CMCGS 2014
Country/Territory	Singapore
City	Singapore
Period	14/2/3 → 14/2/4

Keywords

Eigenvalue problem
Lanczos method
PageRank

ASJC Scopus subject areas

General Mathematics

Access to Document

10.5176/2251-1911_CMCGS14.15_3

Cite this

Teramoto, K & Nodera, T 2016, A note on Lanczos algorithm for computing pagerank. in Springer Proceedings in Mathematics and Statistics. vol. 124, Springer New York LLC, pp. 25-33, 3rd Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, CMCGS 2014, Singapore, Singapore, 14/2/3. https://doi.org/10.5176/2251-1911_CMCGS14.15_3

@inproceedings{868894d6d759423cb301d3bdb02f5f06,

title = "A note on Lanczos algorithm for computing pagerank",

abstract = "We now study the Lanczos algorithm for computing the PageRank vector. This algorithm is based on biorthogonalization, which transforms a nonsymmetric matrix into a tridiagonal matrix to compute PageRank. This generates better approximation of the largest eigenvalue at early stage of iterations. We propose a practical scheme of the Lanczos biorthogonalization algorithm with SVD scheme for computing PageRank. Numerical results show that the proposed algorithm converges faster than the existing Arnoldi method in the computation time.",

keywords = "Eigenvalue problem, Lanczos method, PageRank",

author = "Kazuma Teramoto and Takashi Nodera",

year = "2016",

doi = "10.5176/2251-1911_CMCGS14.15_3",

language = "English",

isbn = "9783319161389",

volume = "124",

pages = "25--33",

booktitle = "Springer Proceedings in Mathematics and Statistics",

publisher = "Springer New York LLC",

note = "3rd Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, CMCGS 2014 ; Conference date: 03-02-2014 Through 04-02-2014",

}

TY - GEN

T1 - A note on Lanczos algorithm for computing pagerank

AU - Teramoto, Kazuma

AU - Nodera, Takashi

PY - 2016

Y1 - 2016

N2 - We now study the Lanczos algorithm for computing the PageRank vector. This algorithm is based on biorthogonalization, which transforms a nonsymmetric matrix into a tridiagonal matrix to compute PageRank. This generates better approximation of the largest eigenvalue at early stage of iterations. We propose a practical scheme of the Lanczos biorthogonalization algorithm with SVD scheme for computing PageRank. Numerical results show that the proposed algorithm converges faster than the existing Arnoldi method in the computation time.

AB - We now study the Lanczos algorithm for computing the PageRank vector. This algorithm is based on biorthogonalization, which transforms a nonsymmetric matrix into a tridiagonal matrix to compute PageRank. This generates better approximation of the largest eigenvalue at early stage of iterations. We propose a practical scheme of the Lanczos biorthogonalization algorithm with SVD scheme for computing PageRank. Numerical results show that the proposed algorithm converges faster than the existing Arnoldi method in the computation time.

KW - Eigenvalue problem

KW - Lanczos method

KW - PageRank

UR - http://www.scopus.com/inward/record.url?scp=84955322856&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84955322856&partnerID=8YFLogxK

U2 - 10.5176/2251-1911_CMCGS14.15_3

DO - 10.5176/2251-1911_CMCGS14.15_3

M3 - Conference contribution

AN - SCOPUS:84955322856

SN - 9783319161389

VL - 124

SP - 25

EP - 33

BT - Springer Proceedings in Mathematics and Statistics

PB - Springer New York LLC

T2 - 3rd Annual International Conference on Computational Mathematics, Computational Geometry and Statistics, CMCGS 2014

Y2 - 3 February 2014 through 4 February 2014

ER -

A note on Lanczos algorithm for computing pagerank

Abstract

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this