Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA continuation method for computing the multilinear Pagerank
142
0
0.0
(
0
)
Added by
Federico G. Poloni
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The multilinear Pagerank model [Gleich, Lim and Yu, 2015] is a tensor-based generalization of the Pagerank model. Its computation requires solving a system of polynomial equations that contains a parameter $alpha in [0,1)$. For $alpha approx 1$, this computation remains a challenging problem, especially since the solution may be non-unique. Extrapolation strategies that start from smaller values of $alpha$ and `follow the solution by slowly increasing this parameter have been suggested; however, there are known cases where these strategies fail, because a globally continuous solution curve cannot be defined as a function of $alpha$. In this paper, we improve on this idea, by employing a predictor-corrector continuation algorithm based on a more general representation of the solutions as a curve in $mathbb{R}^{n+1}$. We prove several global properties of this curve that ensure the good behavior of the algorithm, and we show in our numerical experiments that this method is significantly more reliable than the existing alternatives.
rate research
Read More
We consider the multilinear pagerank problem studied in [Gleich, Lim and Yu, Multilinear Pagerank, 2015], which is a system of quadratic equations with stochasticity and nonnegativity constraints. We use the theory of quadratic vector equations to prove several properties of its solutions and suggest new numerical algorithms. In particular, we prove the existence of a certain minimal solution, which does not always coincide with the stochastic one that is required by the problem. We use an interpretation of the solution as a Perron eigenvector to devise new fixed-point algorithms for its computation, and pair them with a homotopy continuation strategy. The resulting numerical method is more reliable than the existing alternatives, being able to solve a larger number of problems.
In this paper, we propose a numerical method to solve the classic $L^2$-optimal transport problem. Our algorithm is based on use of multiple shooting, in combination with a continuation procedure, to solve the boundary value problem associated to the transport problem. We exploit the viewpoint of Wasserstein Hamiltonian flow with initial and target densities, and our method is designed to retain the underlying Hamiltonian structure. Several numerical examples are presented to illustrate the performance of the method.
We present a parallel computing strategy for a hybridizable discontinuous Galerkin (HDG) nested geometric multigrid (GMG) solver. Parallel GMG solvers require a combination of coarse-grain and fine-grain parallelism to improve time to solution performance. In this work we focus on fine-grain parallelism. We use Intels second generation Xeon Phi (Knights Landing) many-core processor. The GMG method achieves ideal convergence rates of $0.2$ or less, for high polynomial orders. A matrix free (assembly free) technique is exploited to save considerable memory usage and increase arithmetic intensity. HDG enables static condensation, and due to the discontinuous nature of the discretization, we developed a matrix vector multiply routine that does not require any costly synchronizations or barriers. Our algorithm is able to attain 80% of peak bandwidth performance for higher order polynomials. This is possible due to the data locality inherent in the HDG method. Very high performance is realized for high order schemes, due to good arithmetic intensity, which declines as the order is reduced.
This article deals with the efficient and accurate computation of the electrostatic forces between charged, spherical dielectric particles undergoing mutual polarisation. We use the spectral Galerkin boundary integral equation framework developed by Lindgren et al. (J. Comput. Phys. 371 (2018): 712-731) and subsequently analysed in two earlier contributions of the authors to propose a linear scaling in cost algorithm for the computation of the approximate forces. We establish exponential convergence of the method and derive error estimates for the approximate forces that do not explicitly depend on the number of dielectric particles $N$. Consequently, the proposed method requires only $mathcal{O}(N)$ operations to compute the electrostatic forces acting on $N$ dielectric particles up to any given and fixed relative error.
The paper is concerned with methods for computing the best low multilinear rank approximation of large and sparse tensors. Krylov-type methods have been used for this problem; here blo
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
