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.