Algebraic Multigrid for Least Squares Problems on Graphs with Applications to HodgeRank.
Colley, Charles.
Lin, Junyuan.
Hu, Xiaozhe.
Aeron, Shuchin.
2017
-
Least squares problems on graphs are a large subclass of numerical linear algebra problems that may arise from many different applications, e.g., ranking problems, distributed clock synchronization, ranking, and arbitrage detection. Solutions to these problems are very practical and as scalability becomes a prevalent issue, researchers are working to identify algorithms most appropriate to solve ... read morethese least squares problem. A notable endeavor is the work of Hirani et al. [1] where they provide an analysis of a variety of solvers on problems generated by random graphs. One result the group found was that smoothed aggregation algebraic multigrid (SA-AMG) method was unfit for solving these problems. In this work we investigate the effectiveness of the unsmoothed aggregation AMG (UA-AMG) method and show it is more appropriate for graph-related problems due to its ability to maintain the structure of graphs in the multilevel hierarchy. We present an analysis of the two-level algorithms for solving graph Laplacians least squares problems showing that the convergence rate is not tied to the condition number of the matrix. We then apply UA-AMG as a preconditioner for conjugate gradient (CG) method to achieve better performance, providing experiments comparing against other iterative methods on a collection of larger random graphs and a collection of real world network topologies to demonstrate the effectiveness of UA-AMG methods for solving least squares problems on graphs.
© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.read less - Colley, Charles, Junyuan Lin, Xiaozhe Hu, and Shuchin Aeron. "Algebraic Multigrid for Least Squares Problems on Graphs with Applications to HodgeRank." In 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 627-36. Orlando / Buena Vista, FL, USA: IEEE, 2017. https://doi.org/10.1109/IPDPSW.2017.163.
- ID:
- tb09jj722
- To Cite:
- TARC Citation Guide EndNote
- Usage:
- Detailed Rights
