logo SBA

ETD

Archivio digitale delle tesi discusse presso l’Università di Pisa

Tesi etd-11262019-064341


Tipo di tesi
Tesi di laurea magistrale
Autore
BUCCI, ALBERTO
URN
etd-11262019-064341
Titolo
Newton-type methods for the Multilinear Pagerank
Dipartimento
MATEMATICA
Corso di studi
MATEMATICA
Relatori
relatore Prof. Poloni, Federico
controrelatore Prof.ssa Meini, Beatrice
Parole chiave
  • algorithm
  • Multilinear PageRank
Data inizio appello
13/12/2019
Consultabilità
Completa
Riassunto
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.
File