barbagroup / inexact-gmres

Paper: inexact GMRES with fast multipole method and low-p relaxation
9 stars 4 forks source link

Is the error bound used to pick the relaxed p? #14

Closed labarba closed 8 years ago

labarba commented 9 years ago

In Chapter 3 (Methods) of the thesis, section 3.2 talks about relaxation strategies. It presents the error bound for the multipole expansion and says: '…we can form the following expression for the number of terms needed for a given accuracy"

screen shot 2015-06-06 at 8 44 33 am

That's it. Then it goes on about preconditioners on the next page and the section is over. The subject of picking the value of p in the relaxation is never mentioned again.

The first results with relaxation are with the Laplace equation _"…Figure 5.4 shows how both |rk| and p change over the course of a solve … as the residual drops, the p required to maintain convergence of the solver drops" —but no mention of how the values of p were picked. In particular, no mention of using the error bound. The same applies for subsequent results.

I vaguely remember that @slayton58 tried to use the error bound to pick p, but possibly the bounds are too lose and the p did not relax enough. So I have a hunch the results were actually produced with an empirical approach to picking p. But this is not said anywhere!

slayton58 commented 9 years ago

I used 3.28 to choose a suitable error for each iteration, then use that error with 3.31 to get p for that iteration. Only other step is that I bound the predicted p to the range [1, initial_p)

On Jun 6, 2015, at 3:56 AM, Lorena A. Barba notifications@github.com wrote:

In Chapter 3 (Methods) of the thesis, section 3.2 talks about relaxation strategies. It presents the error bound for the multipole expansion and says: '…we can form the following expression for the number of terms needed for a given accuracy"

https://cloud.githubusercontent.com/assets/4800109/8018863/48cfd10a-0c28-11e5-962b-ea55d2e224c3.png That's it. Then it goes on about preconditioners on the next page and the section is over. The subject of picking the value of p in the relaxation is never mentioned again.

The first results with relaxation are with the Laplace equation "…Figure 5.4 shows how both |r_k| and p change over the course of a solve … as the residual drops, the p required to maintain convergence of the solver drops" —but no mention of how the values of p were picked. In particular, no mention of using the error bound. The same applies for subsequent results.

I vaguely remember that @slayton58 https://github.com/slayton58 tried to use the error bound to pick p, but possibly the bounds are too lose and the p did not relax enough. So I have a hunch the results were actually produced with an empirical approach to picking p. But this is not said anywhere!

— Reply to this email directly or view it on GitHub https://github.com/barbagroup/inexact-gmres/issues/14.

labarba commented 9 years ago

There are some discrepancies between (3.28) and the cited reference.

screen shot 2015-06-06 at 6 54 32 pm

They define as \eta the "final tolerance required for the solution of the linear system." You are saying instead that \varepsilon is the "the desired tolerance of the solution." So it appears that you mixed this up in the text of the thesis. I'm going to go for the description in the reference, and add the bit about how p was obtained.

Also note that the reference has r_{k-1} in the denominator, because r_k would not be known yet. So I'm also going to write it that way. Let us know if you disagree with any of this.