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 ( ioannis.koutis@upr.edu),
Computer science department, university
of Puerto rico-rio Piedras.
Gary L. Miller ( glmiller@cs.cmu.edu),
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 ( yangp@cs.cmu.edu),
Computer science department, Carnegie
Mellon university.