A Fast Solver for a Class
of Linear Systems
Abstract
The solution of linear systems is a problem of fundamental
theoretical importance but also one with a myriad of applications in numerical mathematics, engineering, and science.
Linear systems that are generated by real-world applications
frequently fall into special classes. Recent research led to a
fast algorithm for solving symmetric diagonally dominant
(SDD) linear systems. We give an overview of this solver and
survey the underlying notions and tools from algebra, probability, and graph algorithms. We also discuss some of the
many and diverse applications of SDD solvers.
1. intRoDuCtion
One of the oldest and possibly most important computational problems is that of finding a solution to a system of
linear equations. There is evidence that humans have been
solving linear systems to facilitate economic activities
since at least the first century AD. With the advent of physical sciences and engineering, linear systems have been,
for centuries now, a central topic of applied mathematics.
And over the last two decades, the digital revolution has
expanded the use of linear system solvers to applications
of surprising variety.
Many of these new applications typically model entities and their relationships as networks, also known
as graphs, and use solvers to extract information from
them. The resulting linear systems frequently obey simple constraints which classifies them as symmetric diagonally dominant (SDD).
An example of an area where such systems arise is in
the analysis of social networks. Such networks can be represented as a set of links connecting people; an example is
shown in Figure 1. A natural question to ask is how “close”
are two persons in the network. Purely graph-based methods
measure either the length of the shortest path or the maximum number of disjoint paths between the two nodes, but
not both. To take both of these quantities into account we
can view the network as an electric circuit with each connection corresponding to an electrical wire. Hooking a battery at
the two nodes of interest and measuring the resistance of the
entire network gives a quantity known as the effective resistance, which can be used as a “proximity” measure. Since the
electrical network is not physically available, we cannot measure the effective resistance. We can, however, compute it by
solving an SDD linear system.
The above example is only one of many instances of infer-
ence on a graphical model. Similar methods are applicable
in a wide range of problems, such as measuring the impor-
tance of specific proteins in protein–protein interaction
networks14; the link prediction problem in social networks13;
or even problems where graphs arise less directly, such as
segmenting the image shown in Figure 2.
Figure 1. Representing a social network as a graph.
Figure 2. Segmentation of medical scans.
21
This paper is based on two previous works: “Approaching
Optimality for Solving SDD Linear Systems,” which
appeared in the Proceedings of FOCS ’ 10 and “A Nearly-m
log n Time Solver for SDD Linear Systems,” which
appeared in the Proceedings of FOCS ’ 11.