Communications of the ACM
Home/Magazine Archive/October 2012 (Vol. 55, No. 10)/Technical Perspective: Graph Embeddings and Linear.../Full Text
Research highlights
Technical Perspective: Graph Embeddings and Linear Equations
Algorithmic advances can come from the most unexpected places. The following paper by Koutis, Miller, and Peng is an elegant case in point. It describes an emerging approach to solving linear systems of equations that relies heavily on techniques from graph theory.
OK, I admit it. Solving systems of equations is one of those "supposed to be good for you" topics that we all had to suffer through but most of us quickly forgot. But it also happens to be hugely important. For decades, scientists and engineers have simulated the world by solving linear systems. Systems with billions of variables are commonly solved, and this computation almost certainly consumes the majority of supercomputing cycles in the world. In recent years, linear systems have played a key role in page ranking, data analysis, recommendation systems and numerous other aspects of our data-centric world.
Back in high school we were all taught how to solve such systems by repeatedly subtracting one equation from another to eliminate a variable. Unfortunately, this simple approach takes O(n3) time for n equations with n variables. These days, large systems are usually solved using a different type of approach in which better and better approximations to the answer are computed until an acceptable tolerance is achieved. The traditional theory behind these iterative methods relies on numerical analysis, not a favorite class for most computer science students.
In recent years, a small cadre of researchers has been building a novel theoretical framework for analyzing a very important class of linear systems. With this new approach, the performance of an algorithm can be evaluated using techniques from graph theory—a discipline quite different from numerical analysis. The authors describe the quirky history of this line of research, starting with the conceptual breakthrough by Vaidya and continuing with the theoretical heavy lifting provided by Spielman, Teng, and collaborators.
The connection between graph embeddings and linear solvers described in the following paper is a perfect example of cross-disciplinary mixing.
Beyond its novelty value, this research affords insights that traditional approaches cannot. Numerical analysis techniques (and the algorithms that come from them) often have to assume that the system of equations comes from a grid with very simple connectivity. These assumptions are clearly not true for data-centric applications like those mentioned above. By contrast, the new techniques are quite general and impose no constraints on the structure of the system of equations. They lead to algorithmic approaches and analysis tools that are unlike anything that has come before. In addition, theoretical computer scientists think about computational complexity in a different way than numerical analysts do, and so provide a new framework for algorithmic analysis.
This is a challenging area of research because it cuts across disciplines and requires a depth of expertise in multiple areas. This paper provides an accessible introduction to this rapidly evolving set of ideas. Its key contribution is a significantly simpler algorithm that retains desirable theoretical properties. Unfortunately, "simpler" is still probably too complex for the numerical computing community to adopt. But this work brings these ideas much closer to practical realization.
When unanticipated connections between fields are uncovered, we get to see the familiar in strange and fresh ways. Our understanding is deepened and new insights emerge from the fusion of alternative perspectives. The connection between graph embeddings and linear solvers described in this paper is a perfect example of this cross-disciplinary mixing. The line of work it describes has already resulted in improved algorithms for long-standing graph problems, and spun off numerous juicy theoretical questions. Almost lost in this excitement is the implication for scientific computing of provably near-optimal solvers for a hugely important class of linear systems. This is important work whose full ramifications are still emerging.
©2012 ACM 0001-0782/12/10 $15.00
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found