  A new method for solving Laplacian linear systems proposed by Kelner et al.
involves the random sampling and update of fundamental cycles in a graph.
Kelner et al. proved asymptotic bounds on the complexity of this method but did
not report experimental results. We seek to both evaluate the performance of
this approach and to explore improvements to it in practice. We compare the
performance of this method to other Laplacian solvers on a variety of real
world graphs. We consider different ways to improve the performance of this
method by exploring different ways of choosing the set of cycles and the
sequence of updates, with the goal of providing more flexibility and potential
parallelism. We propose a parallel model of the Kelner et al. method, for
evaluating potential parallelism in terms of the span of edges updated at each
iteration. We provide experimental results comparing the potential parallelism
of the fundamental cycle basis and our extended cycle set. Our preliminary
experiments show that choosing a non-fundamental set of cycles can save
significant work compared to a fundamental cycle basis.
