×

Extrapolation methods for fixed-point multilinear PageRank computations. (English) Zbl 1488.65106

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 \(\varepsilon\)-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.

MSC:

65F99 Numerical linear algebra
15A69 Multilinear algebra, tensor calculus
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65B05 Extrapolation to the limit, deferred corrections
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Software:

Netlib; EPSfun; Matlab
PDFBibTeX XMLCite
Full Text: DOI arXiv