can be produced with i applications of the following simple recurrence:
x(0) = 0
x(i+ 1) = b + (I – A)x (i) for i > 0.
It can be seen that each step involves a matrix–vector
multiplication by A. This is the simplest among iterative
methods that in general attempt to approximate the solution of a linear system using only a sum of results from a
series of matrix–vector multiplications.
3. 2. Preconditioning
So far, our replacement for the division button is of rather
restricted value, since it only works when 0 < a < 2, and
can converge very slowly when a is close to 0 or 2. One way
to extend our method and to speed up its convergence is
to add a “restricted division” key to our calculator. This
key allows us to “divide” by a fixed scalar b of our choice,
which in the matrix setting corresponds to a matrix–
vector product involving the inverse, B− 1 of a matrix B. We can
speed up our algorithm by pressing the “restricted division” button after each matrix–vector multiplication by
A, giving the following modified recurrence known as
preconditioned richardson iteration:
x(0) = 0
x(i+ 1) = B– 1 b + (I – B– 1 A)x (i) for i > 0.
The matrix B is known as the preconditioner and
instead of solving the system Ax = b, we are essentially
solving the preconditioned system: B− 1 Ax = B−1b. It is
worth emphasizing that each step of this method involves
a matrix–vector multiplication by A followed by a “
division” by the matrix B.
3. 3. measuring similarity between matrices
Looking back at the single variable recurrence, the critical
condition for its convergence is 0 < a < 2. An extension of it
is needed in order to analyze preconditioned iterative methods involving matrices A and B. For matrices A and B, we say
A B when for all vectors x we have
x T Bx ≤ x T Ax.
Unlike the situation with scalars, this ordering is only
“partial”. Even for size 2 diagonal matrices, it is possible
that neither B A nor A B holds. But when A and B are
symmetric, there will be numbers kmax and kmin such that:
kmin A B kmax A.
We will say that B is a k-approximation of A, where
k = kmax/kmin. In this case, after introducing additional
scaling factors, it can be shown that the preconditioned
Richardson’s iteration gives a good approximation in O(k)
iterations. There are iterative methods with faster convergence rates, and—as we will see—our solver relies on one of
them, known as Chebyshev iteration.
3. 4. interpreting similarity
It is interesting to see what this measure of similarity means
in the context of electrical networks, that is when both A and
B are Laplacians. The quadratic form
x T Ax
is equal to the energy dissipation of the network A, when the
voltages at vertices are set to the values in the vector x. Then,
the network B is a k-approximation of the network A whenever for all voltage settings, B dissipates energy which is
within a k factor of that dissipated by A.
So, roughly speaking, two networks are similar when
their “energy profiles” are similar. This definition does not
necessarily correspond to intuitive notions of similarity; two
networks may appear to be very different but still be similar.
An example is shown in Figure 4.
3. 5. What is a good preconditioner?
Armed with the measure of similarity, we are now ready to
face the central problem in solver design: how do we compute a good preconditioner?
To deal with the question we must first understand what
properties are desirable in a preconditioner. A big unknown
in the total running time is the cost incurred by the limited
division button that evaluates B−1y.
To evaluate B−1y we do not need to compute B− 1. We can
instead solve the system Bz = y; the solution z will be equal
to B−1y. Clearly, we would like to solve systems involving
B as quickly as possible. At the same time we would like the
number of iterations to be as small as possible, since each
of them requires at least m operations. Furthermore, a slow
algorithm for computing the preconditioner B would defeat
the purpose of a fast solver. So, we should also be able to find
B quickly. Balancing these three opposing goals makes the
problem quite challenging.
3. 6. Recursion and design conditions
In order to solve the linear system fast, we will need a preconditioner B which is an extremely good approximation
of A and can be solved in linear time. Satisfying both these
requirements is too much to hope for. In practice, any good
graph preconditioner B won’t be significantly easier to solve
Figure 4. two similar graphs: A complete graph and a random small
subset of its edges, made heavier.