also called variables, b is a n × 1 column vector of real num-
bers, and A is an n × n matrix containing the coefficients of
the variables. For example, the above linear system can be
expressed in matrix form as:
( 2. 1)
Note that each off-diagonal entry is the negation of the
conductance of the resistor connecting its two vertices,
and each diagonal entry is the sum of the conductances
of all resistors incident to the corresponding vertex.
Since resistive networks can also be viewed as undirected
graphs, this type of matrix is known as a graph laplacian
and we will rely on this connection extensively in our
algorithm. SDD matrices are a further generalization of
graph Laplacians. However, an SDD system can be easily transformed into a Laplacian system (e.g. see Koutis
9) and so we will restrict our attention entirely to
Once we’re able to obtain the voltages at each vertex, we
can also compute the effective resistance between two vertices. Intuitively, this notion can be viewed as thinking of
the entire network as a single electrical component. Then
by Ohm’s law the voltage drop required to send 1 unit of
current corresponds to the resistance of the component.
In our example, the effective resistance between vertex 1
and 2 is x1 − x3 = 2/5. Formally, this value equals vs − vt from
the solution of the linear system Lv = j, where j is zero
everywhere except in the two entries corresponding to the
nodes s and t, for which we set js = 1 and jt = − 1. As we will
see later, this metric is not only used for network analytics,
but also plays a crucial role in our solver itself.
2. 1. Solvers and their speed
Despite its long history, the problem of constructing good
solvers is considered far from being solved, especially in
terms of speed. The speed of algorithms is commonly measured in terms of the input size. In the case of general linear systems on n variables, the matrix has size n2. However,
matrices are often sparse, that is, most of their entries are
equal to zero. Because of this we can easily “compress” them
to size proportional to the number of non-zeros, denoted by m.
The best case scenario, which remains entirely consistent
with our current understanding, is that linear systems can
be solved with O(m)a operations.
It’s fair to say that Gaussian elimination is the most
well-known method for solving linear systems. It runs in
O(n3) time and it is known as a direct method in that, if
the arithmetic operations are performed exactly then one
gets the exact solution to the system. Although this exponent of 3 has been decreased to as low as 2. 37,
methods in general require storing n2 entries, creating
a natural bottleneck that limits us to systems with a few
a We use f (n) = O( g (n) ) to denote f (n) ≤ c · g (n) when n ≥ n0 for some constants
c and n0.
One possible remedy to the space and time limitations of
direct methods are iterative methods. These compute progressively better approximate solutions by only performing
matrix–vector products and other simpler vector operations.
One of the most important iterative methods is Conjugate
Gradient, discovered by Lanczos, Hestenes, and Stiefel in
the early 1950s. This method works for arbitrary symmetric
positive definite systems, a class that includes SDD systems.
While it requires only O(m) space, it is understood that its
running time—in its original form—can be large.
Strong evidence that iterative methods can combine low
space requirements and very fast running time was provided by a family of iterative methods known as multigrid.
Multigrid solvers have an O(m) running time guarantee
albeit for restricted and well-structured systems that arise in
The solver we will review in this paper is also an iterative
method. It is the culmination of a line of work initiated by
23 which was brought to near-completion with the
breakthrough achievement of Spielman and Teng19: the first
solver that runs in time O(m log c n) for any graph Laplacian,
where c is a large constant. The work discussed here, summarized in the following claim from Koutis et al.,
a conceptually simpler, faster and more practical algorithm.
Theorem. SDD systems can be solved in Õ(m log n log(1/ε) )
time,b where ε is a standard measure of the approximation
3. thE ALGEBRAiC ComPonEnt
3. 1. iterative methods: Division-free inversion
Our way towards the faster solver starts with a basic and
perhaps seemingly unrelated question: is it possible to compute the inverse 1/a of a number a using a calculator with a
broken division key?
To answer the question we can invoke a basic identity
that tells us that when 0 < a < 2, 1/a equals the following infinite sum:
1/a = 1/( 1 − ( 1 − a))
= 1+( 1−a)+( 1−a)
2 +( 1−a)
( 3. 2)
Of course, computing an infinite sum is not possible. But
keeping a number of terms will give us an approximation of
1/a; the more terms we keep the better the approximation.
But how is this related to the problem of solving linear
systems? Matrices borrow several of the usual properties of scalar numbers. When A is symmetric, its inverse
A− 1 also satisfies the identity in 3. 2, substituting A for
a, A− 1 for 1/a and the identity matrix I for the number 1.
Furthermore, if we want an approximation to x = A−1bc we
can actually avoid entirely taking powers of the matrix; the
ith approximate vector
x(i) = (I + (I – A) + . . . (I – A)i)b
b The Õ() notation hides a log log n factor.
c If A− 1 does not exist, as in the case of Laplacians, we use A− 1 to denote the
pseudoinverse as well.