Premium
Extrapolation methods for fixed‐point multilinear PageRank computations
Author(s) -
Cipolla Stefano,
RedivoZaglia Michela,
Tudisco Francesco
Publication year - 2020
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/nla.2280
Subject(s) - pagerank , extrapolation , multilinear map , power iteration , computation , eigenvalues and eigenvectors , mathematics , convergence (economics) , rate of convergence , fixed point , algorithm , matrix (chemical analysis) , computer science , mathematical optimization , theoretical computer science , iterative method , mathematical analysis , pure mathematics , key (lock) , physics , computer security , materials science , quantum mechanics , economics , composite material , economic growth
Summary Nonnegative tensors arise very naturally in many applications that involve large and complex data flows. Due to the relatively small requirement in terms of memory storage and number of operations per step, the (shifted) higher order power method is one of the most commonly used technique for the computation of positive Z ‐eigenvectors of this type of tensors. However, unlike the matrix case, the method may fail to converge even for irreducible tensors. Moreover, when it converges, its convergence rate can be very slow. These two drawbacks often make the computation of the eigenvectors demanding or unfeasible for large problems. In this work, we consider a particular class of nonnegative tensors associated with the multilinear PageRank modification of higher order Markov chains. Based on the simplified topological ε ‐algorithm in its restarted form, we introduce an extrapolation‐based acceleration of power method type algorithms, namely, the shifted fixed‐point method and the inner‐outer method. The accelerated methods show remarkably better performance, with faster convergence rates and reduced overall computational time. Extensive numerical experiments on synthetic and real‐world datasets demonstrate the advantages of the introduced extrapolation techniques.