Asset Details
Do you wish to reserve the book?
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
Do you wish to request the book?
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Paper
Ultrasparse Ultrasparsifiers and Faster Laplacian System Solvers
2023
Overview
In this paper we provide an \\(O(m (\\log \\log n)^{O(1)} \\log(1/\\epsilon))\\)-expected time algorithm for solving Laplacian systems on \\(n\\)-node \\(m\\)-edge graphs, improving improving upon the previous best expected runtime of \\(O(m \\sqrt{\\log n} (\\log \\log n)^{O(1)} \\log(1/\\epsilon))\\) achieved by (Cohen, Kyng, Miller, Pachocki, Peng, Rao, Xu 2014). To obtain this result we provide efficient constructions of \\(\\ell_p\\)-stretch graph approximations with improved stretch and sparsity bounds. Additionally, as motivation for this work, we show that for every set of vectors in \\(\\mathbb{R}^d\\) (not just those induced by graphs) and all \\(k > 1\\) there exist ultrasparsifiers with \\(d-1 + O(d/\\sqrt{k})\\) re-weighted vectors of relative condition number at most \\(k\\). For small \\(k\\), this improves upon the previous best known relative condition number of \\(\\tilde{O}(\\sqrt{k \\log d})\\), which is only known for the graph case.
Publisher
Cornell University Library, arXiv.org
Subject
