Speaker
Description
In this talk, we consider the solution of the multilinear PageRank problem, which can be reformulated as a nonlinear system of equations in which the coefficient matrix is an M-matrix. In [1], Alfa et al., demonstrated that the inverse of a nonsingular M-matrix can be determined with a high relative entrywise accuracy by using a triplet representation of the M-matrix through a method known as the GTH algorithm. This variant of Gaussian elimination allows for the computation of a numerical inverse with comparable entrywise relative accuracy. Our approach combines the GTH algorithm with either the Newton method or block iterative schemes (such as block Jacobi, block Gauss-Seidel, and block Successive Over-Relaxation iterations). Specifically, in each iteration of the Newton method, we use the GTH algorithm to compute the inverse. All sub-matrices of the coefficient matrix are nonsingular M-matrices and can also be represented in a triplet format; So, at each step in the block iterative schemes, the GTH algorithm is used for inverse computation, which ensures high relative entrywise accuracy. We focus on the cases where the problem approaches a critical case, potentially causing the coefficient M-matrix become singular. In cases where the M-matrix becomes singular, we consider shifted versions of the algorithms. Our numerical results show the efficiency and reliability of our approach.
References:
-
Alfa, A., Xue, J., & Ye, Q. (2002). Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix. Mathematics of computation, 71(237), 217-236.
-
Alfa, A. S., Xue, J., & Ye, Q. (2002). Entrywise perturbation theory for diagonally dominant M-matrices with applications. Numerische Mathematik, 90, 401-414.
-
O'Cinneide, C. A. (1996). Relative-error bounds for the LU decomposition via the GTH algorithm. Numerische Mathematik, 73, 507-519.
