• algorithm
• Multilinear PageRank

The aim of this thesis is to present new methods for solving the Multilinear PageRank problem. For that, we analyse different known iterative algorithms, such as the ones studied in a paper by Gleich, Lim and Yu.

In this brief investigation, we confirmed the superiority of the Newton's iteration over the other iterative algorithms. Providing also an ad hoc modification of Newton's method, the so called "\textit{Inexact inverse Newton's iteration}". This modification, scaling to large problems, could help to reduce the computational effort required by the Newton's iteration.

Though Newton's iteration turned out to be the best alternative, it still has some drawbacks. In particular, there are tensors for which convergence is too slow or even not achieved. So, for reasons of reliability, we far investigated the problem.

Inspired by ideas of homotopy continuation we designed two new algorithms. To introduce them, we give notions of numerical continuation theory, that is a strategy used to approximate solutions of a system of parametrized nonlinear equations. In particular we focus our attention on predictor-corrector methods.
These methods apply really well on our case, indeed the equations involved in the Multilinear PageRank problem can be seen as homotopy maps, that are effectively parametrized equations.

In the conclusion of the thesis we report some numerical experiments conducted on a large amount of tensors of several dimensions. The experimentation shows that one of the predictor-corrector algorithms still has some troubles with input coefficients that we should make adaptive, while with the other we have already achieved extraordinary results.