An Empirical Study of Cycle Toggling Based Laplacian Solvers
Skip to main content
eScholarship
Open Access Publications from the University of California

An Empirical Study of Cycle Toggling Based Laplacian Solvers

  • Author(s): Deweese, K
  • Gilbert, JR
  • Miller, G
  • Peng, R
  • Xu, HR
  • Xu, SC
  • et al.
Abstract

We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solution to this linear system through a sequence of flow adjustments along cycles. We study both data structure oriented and recursive methods for handling these adjustments. The primary difficulty faced by this approach, updating and querying long cycles, motivated us to study an important special case: instances where all cycles are formed by fundamental cycles on a length $n$ path. Our methods demonstrate significant speedups over previous implementations, and are competitive with standard numerical routines.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View