[Bf-committers] Durian/Hair Troubles

[bjornmose]

Hi Brecht,
sure when the single hair systems do not interact, it is far more 
efficient to solve them separately.

I don't know too much about Daniels implementation of the ODE solver.
But in general:
GC  is known to find a local minimum if:
a. there is one
b. it starts close enough so it can run 'downhill' and come to rest.
   Once it crossed a saddle it will happily run into the neighbour valley.
   From there the valley may open to the 'great plains' -> the solution 
will randomly search the next water hole.     

My guess would be that the starting vector ( which is at t =(t -dt)) is 
for some reasons too far away.
Most likely the variations in the goals are spoiling things here again.
As far as i remember the cloth solver uses fixed step sizes.
Adaptive stepping as seen in the soft body solver might be the cure to it.
However the SB solver is 'explicit' and not suited for stiff systems 
like that.
I am not really sure if a similar step size estimation is as easily 
implemented for 'implicit'.
Especially it needs a reliable estimation for the 'solver error'.

A cheap but not really reliable method is to watch some kind of 
'distance'  |S(t)-S(t-dt)|
/* where S is the position and velocity vector */
and reduce dt if the distance is too big. Pretty bad task to tune 'too 
big' in this case.

Once again id like to point at the book 'Numerical Recipes'.
They clearly focus on coding ( solving numerical problems ) without 
drowning you in mathematical details.
note 1:  you must not use code found there for licence issues but it is 
very inspiring.
note 2: i would not because i don't like the way they code liner algebra
In this case the chapter on  CG and the one on solving stiff ODEs.
Though the solver proposed there did not work for me, (*)
it gives a nice insight why implicit is a must here.

(*)
I tried with SB and superLU .. some commented fragments still there :) 
.. in 2.49 i think i did clean up 2.5 a bit.
The jacobian/hesse matrix was not good enough. I think i did not build 
carefully enough.
Well I failed. Does not mean it is not worth a try. I think you are more 
familiar inverting matrix monsters like that.

I hope i could give some hints.
If I was not clear enough, don't hesitate to ask.
Some times I assume 'simple facts' to be known, ignoring it took me 20+ 
years to sort it out :)
BM

some more theory hints:
If you run a 'normalized' (**) CG on a functional s=F(x1,x2 ... ,xn),
s is scalar, then |d(s)/(dxn)| (vector) and |det[d^2(s)/(dxn dxm)]| 
(matrix) should be smaller than 1 .. other ways it may, not necessarily 
will, explode.
And if [d^2(s)/(dxn dxm)] has complex  eigenvalues  expect oscillations 
that need to be damped away.
On the other hand if above conditions hold, the banach fixpunktsatz will 
(almost (***)) work and you can be sure it won't explode!
Got to love it:
 http://en.wikipedia.org/wiki/Banach_fixed_point_theorem
most of the convergence proofs end there.


(**) solution is boxed by unit cube
(***) contracting condition might be violated .. we are only sure about 
lamba here ( referring German text )

Brecht Van Lommel schrieb:
> Hi,
>
> I've been looking into the implicit solver code since yesterday, and
> made one change which seems to help stability (will be committed
> soon). Instead of doing the implicit integration on all hairs at once,
> it is now done on individual hairs. I found that usually the conjugate
> gradient takes about 4-8 steps, but it sometimes takes 20 or even does
> not converge, and returns bogus velocities. I'm not entirely sure why
> that is, but it seems logical that a smaller system would be more
> numerically stable. What I suspect is that since there are many hairs,
> and it tests for the average error of those hairs, a few hairs may be
> able to hide their high error in this average. This is just a guess
> though, but I looked at all the values coming into the CG function,
> the forces, their derivatives, etc, on the frames that explode, and
> couldn't find anything out of the ordinary compared to other frames.
>
>