Fast Algorithms For HodgeRank Problems
Jiang, Zian
2019
- Least squares problems on graphs are a category of numerical linear algebra and optimization problems that are prevalent in ranking problems arising in real world networks. It has been an active research area to identify algorithms with good scalability. A notable work is from Colley et al, where they investigate the effectiveness of the unsmoothed aggregation algebraic multigrid (UA-AMG) and ... read moreshow that the algorithm is able to preserve the property that the convergence rate is not tied to the condition number of the matrix, and thus is more appropriate for graph-related problems. Also, they solve the least squares problems by solving their normal equations. In this work, we try to solve the least squares problem directly without forming the normal equation by using subspace correction method, multigrid method and sampling method to transform the original problem into a sequence of sub-problems in order to achieve better performance, providing numerical experiments comparing against other iterative methods on large random graphs and one set of real world networks to demonstrate the effectiveness of our algorithms for solving least squares problems on graphs.read less
- ID:
- ks65hr14z
- To Cite:
- TARC Citation Guide EndNote
