in Spielman and Teng20 that O(log n) iterations of solves produce a good approximation to a basic eigenvector of a graph. More closely related to preconditioned iterative methods is a solver for elliptic finite element linear systems. 4 This work showed that such systems can be preconditioned with graph Laplacians and so they can be solved in nearly linear time.

A more general framework stems from one of the most powerful discoveries in combinatorial optimization: interior point algorithms. It was shown by Daitch and Spielman17 that interior point algorithms allow us to reduce a broad class of graph problems to solving a small number of SDD linear systems. This led to the best known running times for problems such as minimum cost flow and loss generalized flow. These problems are extensions of the maximum flow problem, which in its simplest version asks for the maximum number of edge disjoint routes (or “flow”) between two nodes s and t. Further work in this direction led to the first improvement in 20 years on the approximate maximum flow problem. 5 The max-flow result is in turn directly applicable to graph partitioning, that is the separation of a graph to two well connected pieces; the fastest known algorithm for this problem repeatedly applies the fast max-flow algorithm. 16

It is also worth noting that the solver presented in Blelloch et al. 3 readily gives—for all the above problems— parallel algorithms that are essentially able to split evenly the computational work and yield speedups even when only a small number of processors is available. This is a rare feature among previous algorithms for these problems.

Solver-based algorithms have already entered practice, particularly in the area of computer vision, where graphs are used to encode the neighboring relation between pixels. Several tasks in image processing, such as image denoising, gradient inpaint-ing, or colorization of grayscale images, are posed as optimization problems for which the best known algorithms solve SDD systems. 11, 12 Linear systems in vision are often “planar”, a class of SDD systems for which an O(m) time algorithm is known. 7

Given the prevalence of massive graphs in modern problems, it is expected that the list of applications, both theoretical and practical, will continue expanding in the future. We believe that our solver will accelerate research in this area and will move many of these algorithms into the practical realm.

Acknowledgments

This work is partially supported by NSF grant number CCF- 1018463. I. Koutis is supported by NSF CAREER award CCF- 1149048. Part of this work was done while I. Koutis was at CMU. R. Peng is supported by a Microsoft Research Fellowship.

 

1. abraham, I., neiman, o. using petal decompositions to build a low stretch spanning tree. In Proceedings of the 44th Symposium on Theory of Computing (stoC ’ 12, 2012), aCM, new york, ny, 395–406.

2. alon, n., karp, r., Peleg, d., West, d. a graph-theoretic game and its application to the k-server problem. SIAM J. Comput. 24( 1) (1995), 78–100.

3. blelloch, g.e., gupta, a., koutis, I., Miller, g.l., Peng, r., tangwongsan, k. near linear-work parallel sdd solvers, low-diameter decomposition, and low-

References

stretch subgraphs. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (sPaa ’ 11, 2011), aCM, new york, ny, 13–22.

4. boman, e.g., hendrickson, b., Vavasis, s.a. solving elliptic finite element systems in near-linear time with support preconditioners. SIAM J. Numer. Anal. 46( 6) (2008), 3264–3284.

5. Christiano, P., kelner, J.a., Ma¸dry, a.,
spielman, d., teng, s.-h. electrical
flows, laplacian systems, and faster
approximation of maximum flow in
undirected graphs. In Proceedings of
the 43rd ACM Symposium on Theory of
Computing (STOC), 2011.

 

Ioannis Koutis ( [e-mail]), Computer science department, university of Puerto rico-rio Piedras.

Gary L. Miller ( [e-mail]), Computer science department, Carnegie Mellon university.

16. sherman, J. breaking the multicommodity flow barrier for

O( n)-approximations to sparsest cut. In Proceedings of the 2009

50th Annual IEEE Symposium on Foundations of Computer Science (FoCs ’09, 2009), Ieee Computer society, Washington, dC, usa, 363–372.

17. spielman, d.a., daitch, s.I. Faster approximate lossy generalized flow via interior point algorithms. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), May 2008.

18. spielman, d.a., srivastava, n. graph sparsification by effective resistances. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 2008, 563–568.

19. spielman, d.a., teng, s.-h. nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), June 2004, 81–90.

20. spielman, d.a., teng, s.-h. nearly-linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. CoRR, abs/cs/ 0607105, 2006.

21. tolliver, d.a., koutis, I., Ishikawa, h., schuman, J.s., Miller, g.l. automatic multiple retinal layer segmentation in spectral domain oct scans via spectral rounding. In ARVO Annual Meeting, May 2008.

22. trottenberg, u., schuller, a., oosterlee, C. Multigrid, 1st edn, academic Press, london, 2000.

23. Vaidya, P.M. solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. A Talk Based on this Manuscript was Presented at the IMA Workshop on Graph Theory and Sparse Matrix Computation, october 1991.

24. Vassilevska Williams, V. breaking the Coppersmith-Winograd barrier. In Proceedings of the 44th Symposium on Theory of Computing, stoC ’ 12, 2012.

 

Richard Peng ( [e-mail]), Computer science department, Carnegie Mellon university.