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.