An Accelerated Newton‐GMRES Method for Multilinear PageRank

ABSTRACT Modeling complex multiway relationships in large‐scale networks is an increasingly important challenge in modern data science. The multilinear PageRank problem, which arises from higher order Markov chains, provides a natural framework for capturing such interactions, with applications in web ranking, recommendation systems, and higher order network analysis. It extends the classical Google PageRank model to a tensor‐based formulation, leading to a nonlinear system that describes multiway dependencies between states. Although classical Newton methods exhibit local quadratic convergence under standard assumptions, their practical applicability is often limited by the high computational cost of assembling and solving large Jacobian systems, especially for large‐scale problems. To overcome this limitation, we propose an accelerated Newton‐GMRES framework in which the GMRES method is used to approximately solve the linear systems arising at each Newton iteration, in a matrix‐free manner, thus avoiding the explicit construction of the Jacobian. We further employ vector extrapolation methods, including Minimal Polynomial Extrapolation (MPE), Reduced Rank Extrapolation (RRE), and Anderson Acceleration (AA), to further improve convergence and robustness. In addition, we compare the proposed approach with commonly used methods for nonlinear problems, such as preconditioned GMRES variants and quasi‐Newton schemes, in order to place our results within the broader numerical literature. Extensive numerical experiments on benchmark tensors, synthetic data, and real‐world networks demonstrate that the proposed accelerated Newton‐GMRES method is more efficient and scalable than standard Newton‐type solvers, particularly for large problem sizes and for damping parameters close to 1.