| As a new stochastic model,the multilinear Page Rank model can be used for the data clustering and the hypergraph segmentation.Currently,the following main research directions are available: the uniqueness of solution,the disturbance analysis,the iteration methods and the practical applications.In this paper,we study several iterative methods to speed up the computations of the multilinear Page Rank problem.The research is mainly divided into two parts.One is the research of the fixed-point iterative class,and the other is the research of the Newton iterative class.In the study of the fixed-point iterative class,we first propose the FPIO algorithm.Based on the fact that the fixed-point iteration and the inner-outer method are too slow in solving the multilinear Page Rank problem,we use the two-step iterative framework to accelerate the computations.The specific implementation is as follows.The fixedpoint iteration is performed in the first half-step of the FPIO iteration,then the inner-outer method is run in the second half-step.Convergence analysis shows that the convergence speed of FPIO algorithm is faster than that of the fixed-point iteration and the inner-outer method.Furthermore,numerical experiments are used to illustrate the efficiency of the FPIO algorithm.Inspired by the FPIO algorithm,we replace the first half-step of the FPIO iteration with the multi-step fixed-point iterations,and then combine them with the inner-outer method periodically to obtain the MFPIO algorithm.This algorithm sacrifices the calculation cost of a single iteration in exchange for a faster convergence speed.Convergence analysis shows that the MFPIO algorithm converges faster than the FPIO algorithm and numerical experiments confirm that the MFPIO algorithm performs better than the FPIO algorithm.Finally,in order to speed up the multilinear Page Rank computations,the fixed-point iteration is improved by considering the minimal polynomial extrapolation(MPE)acceleration technique,such that a new algorithm named FPMPE is presented.In addition,convergence behaviour of the FPMPE algorithm is discussed in detail.Numerical results on several multilinear Page Rank problems are used to demonstrate the effectiveness of the FPMPE algorithm by comparing with several existing methods.In the study of the Newton iterative class,we propose the Chord-Newton-Krylov algorithm to compute the multilinear Page Rank problem.Instead of the LU decomposition,we directly adopt the Krylov subspace method to solve the linear system at each Newton iteration.Thereby,we obtain the Newton-Krylov method.Moreover,in order to minimize the computing consumption,the stopping criterion of the linear system is adaptive during the entire iteration.Inspired by the chord method,we fix the coefficient matrix of the linear system when the iteration of the Newton-Krylov method tends to be stable,so as to further reduce the calculation.That is the Chord-Newton-Krylov algorithm.Afterwards,the convergence analysis of the Chord-Newton-Krylov algorithm is discussed.Numerical experiments are used to show the efficiency of the proposed algorithm. |
