series acceleration

[quaz0r]

im not sure what exact methodologies you mandelbrot guys are using with your handling of series approximation, but lately ive decided that i am rather dissatisfied with my own experience with it.  i found the mandelmachine thread where he mentions checking terms against each other and bailing when a term grows too large, and that is the general idea of anything i recall reading on the matter on these forums.  ive tried a few variations on this, all with similar results.  plenty of times it works out rather well and other times it leaves you holding a bigger bag of iterations to burn through than you would like, with respect to what actually ends up being the lowest iteration for a given location.

i decided to experiment with series acceleration with the hope that it could help improve matters, and indeed it seems to be the magic bullet i was hoping it would be.  my test for when to bail on series approximation now consists of checking for when the series approximation starts to deviate from the result of running it through the Levin u-transform available in the gnu scientific library.  so far in my tests this is taking me right up to the event horizon of what will end up being the lowest iteration, even in locations that used to cause the other methods to bail on the series approximation way sooner, but it also does not seem to be going too far so as to cause glitchy artifacts.  it seems to be just right, across the board, which i find to be rather exciting!  maybe you guys were already doing it better than i was doing it, but this is turning out to be a huge improvement for me at least.

[mclarekin]

 

[claude]

rather exciting!

cool stuff!  are you using the accelerated series to initialize points?  or just for stopping condition?  how are you choosing thresholds for stopping?  Need to read up more on the u-transform, any pages/papers you recommend?

[skychurch]

Are you still running with this Quazor? 'Cos this would be the paradigm to follow. If it's still good then I will need to implement it.
Since no replies from the established publishers then I can only assume they're relying on the glitch fix stage.

regards skychurch. 

[quaz0r]

oops, i never noticed i got any replies to this.  well, it seemed great at the time, but after a while it seemed to be taking the series approximation too far, resulting in some glitchy locations, so i ended up reverting to the old way.  though the rest of my code wasnt as solid as it is now, so it might be worth another look to make sure.

are you using the accelerated series to initialize points?  or just for stopping condition?  how are you choosing thresholds for stopping?

when i first wondered if series acceleration could be useful at all, i imagined using it to make the approximation itself more accurate, though in my tests it seemed to not change the value at all.  given that it wasnt having any effect on the value, i decided to try using it as a stop condition, simply stopping when there was any difference between the series approximation and the accelerated approximation.  this is where my experimenting stopped.  this was getting me very close to the min iteration each time but eventually it seemed to be taking me too far sometimes (i think).  though like i say i should give it another try now that the rest of my code is pretty solid and glitch-free; my program was still less than perfect at the time.  also you guys are the math professors not me, maybe there is some other way of doing things that would work better.  i just like to screw around and try different things and hope that i hit on something once in a while.  

some further thoughts:

im sure there has to be some more direct, less rube-goldberg way of measuring the error, such that it gets you as far as you can go but also does not bail prematurely.  knighty posted some math to this effect in one of the other perturbation threads somewhat recently, though it sounded like the consensus was that it would both be computationally expensive and result in bailing prematurely.  so it seems this is still an open problem.

[quaz0r]

ok, so it turns out, rather unsurprisingly, that my memory of my screwing around with this stuff a year ago was no good, and my program was no good back then either, so my previous post last night about what i thought i was remembering was also no good.

my previous check was just what i gleaned from the discussion on the forums here, checking for when the last term in the series grows larger by a few orders of magnitude than any of the other terms.  maybe that is an incomplete or otherwise flawed solution, and maybe you guys did it better or more complete than how i did it, i dont know.  i reimplemented the acceleration check, and it looks very promising indeed.  similar to the other method, i check for when the accelerated sum differs from the unaccelerated sum by a few orders of magnitude as the bail condition.  in my bit of testing this morning, when testing the other method with a setting that causes it to go far enough that it starts producing some questionable results, the method of checking the accelerated sum is able to go substantially farther than that, but with what appears to be correct results.  this indicates to me that the other method or at least my implementation of it is flawed / incomplete / unreliable, sometimes stopping in time and sometimes going too far, whereas the method of checking the accelerated sum looks to be more consistent.  more testing is necessary, but it looks promising and i am kind of hopeful about this again.  im glad you guys resurrected this post  

...i also wonder again if there could be any benefit in actually utilizing the accelerated sum to initialize points.  should test that also.  in my mind im not sure if the result should actually be a better value, or the opposite, a magnification of the error.

another thing, if one was to decide to call this good and roll with it, i guess you would need to strip the acceleration routine out of libgsl and modify it (or write your own routine) so that it can use more than just doubles, like our extended-exponent types. (groan)   well, looking at the gsl code, its only a few pages long, so it shouldnt be too big a deal.

[skychurch]

Good work! 

[quaz0r]

thanks 

i check for when the accelerated sum differs from the unaccelerated sum by a few orders of magnitude as the bail condition.

i said that wrong.  what im currently doing is checking if the larger sum divided by the smaller sum is greater than bailCondition, setting bailCondition to something like 1.001.  so its when the accelerated sum starts to diverge from the unaccelerated sum past a certain number of mantissa digits?  or however you would best say it

[claude]

however you would best say it

I'd say it was something like "relative error exceeds a threshold".

Thanks for the additional infomration!  I might try it out at some point.  If I do, I'll report back on this thread.