random / non-deterministic behavior of pyamg

[lukeolson]

I'm running experiments that should be reproducible and thus deterministic. However, pyamg somewhere makes use of randomness and I can't figure out where this happens (and why). The following lines illustrate the problem (A is an SPD csr_matrix and b is a vector):

Aamg = smoothed_aggregation_solver(A).aspreconditioner()
x1 = Aamg * b

Aamg = smoothed_aggregation_solver(A).aspreconditioner()

x2 = Aamg * b

I expect x1-x2 to be zero which is not the case. A workaround for me is to fix numpy's random seed (e.g. by inserting np.random.seed(1337)) before both calls to smoothed_aggregation_solver, but I would be happy to know the source of the randomness and how to 'fix' it. :)

A minimal example is attached in a file.

Migrated from http://code.google.com/p/pyamg/issues/detail?id=139

---

earlier comments

jacob.b....@gmail.com said, at 2013-01-09T19:27:46.000Z:

The spectral radius computation for the Jacobi prolongation smoother is likely at least one reason. PyAMG uses standard Arnoldi iteration to approximate the spectral radius for Jacobi and this includes a random initial guess for the Arnoldi process. If this is the issue, perhaps we should fix a numpy.random.seed(...) value when the setup phase initializes.

• Jacob

  gaul@web-yard.de said, at 2013-01-16T15:53:14.000Z:

Thanks, the Jacobi smoother seems to be the cause. If I use -------------------- Aamg = smoothed_aggregation_solver(A, smooth=None).aspreconditioner() -------------------- or smooth='richardson' or smooth='energy' then the randomness disappears. What do you think about including the initial vector for Arnoldi/Lanczos as an optional parameter? A random guess for Arnoldi/Lanczos is fine in most cases, but in special cases you might already have a good vector (for example from previous outer iterations).

jacob.b....@gmail.com said, at 2013-01-17T00:30:51.000Z:

Hi Andre,

I'm glad that that seems to be the problem. It's the pyamg.util.linalg.approximate_spectral_radius(...) routine that provides the randomness for the Jacobi prolongation smoother.

Your suggestion is a good one, and I think that PyAMG largely already does this. The routine pyamg.util.linalg._approximate_eigenvalues(...) does carry out Arnoldi/Lanczos based on an initial guess. The routine approximate_spectral_radius(...) calls _approximate_eigenvalues(...) multiple times like an outer Krylov iteration, while using a random initial guess for only the first outer iteration.

What I'm wondering is whether or not to fix a random.seed(...) value somewhere, so that the preconditioner is the same every time you run the code.

Thoughts?

• Jacob

  gaul@web-yard.de said, at 2013-01-21T09:44:42.000Z:

Hi Jacob,

I'd say that the random.seed() can be fixed by the user. However, I would add a few words about the background of the randomness in the documentation of smoothed_aggregation_solver and/or jacobi_prolongation_smoother.

As for the initial guess, I suggest to add the optional parameter initial_guess also to approximate_spectral_radius and jacobi_prolongation_smoother. Then, as far as I can see, the user would also be able to provide an initial guess when calling smoothed_aggregation_solver.

In my opinion, providing an initial guess is the cleaner way since you may already have a good guess at hand. What do you think of that?

Cheers,
André

jacob.b....@gmail.com said, at 2013-01-23T16:59:29.000Z:

Hi Andre,

I've added "Notes" to jacobi_prolongation_smoother indicating that results are not precisely reproducible, unless the random number generator is seeded with the same value for each test. I agree that this must have been confusing at first!

I also added an initial guess option to approximate_spectral_radius, because this seems quite useful. However, I don't want to add more parameters to the jacobi_prolongation_smoother interface, unless absolutely necessary. This interface is already fairly complicated and somewhat intimidating. I hope this works for you.

Thanks for finding and reporting this,

Jacob

gaul@web-yard.de said, at 2013-01-23T19:22:19.000Z:

Hey Jacob,

thanks for your commit! Of course, I leave it up to you what to put in the jacobi_prolongation_smoother interface. I wouldn't say that it's too complicated but I'm also happy with the seed() variant and I think this issue can be closed. :)

-- André

jacob.b....@gmail.com said, at 2013-01-23T19:31:16.000Z:

Hi Andre,

Sounds good! I'm closing the ticket.

Thanks again,

Jacob