[ODE] Croteam's optimizations

[Alen Ladavac]

Hi Russ,

Yes, I am aware of the reasons connected with near-singular matrices. But it
is the part with - sometimes undesired - springiness that bothers us here.
Generally, it is good to have CFM for flexibility (if you want to make some
constraint a bit softer), but it is also nice if the solver doesn't actually
require it.

Thing is that A matrix is built as J*Minv*Jt, and as such, it contains parts
that are combined by various multiplications of smaller blocks like
J1*M2inv*J3t, where J1 and J3 are joint matrices for two joints on body with
mass M2. This is what can make it singular. But a diagonal part, like
J1*M2inv*J1t is never singular, right? GS solver always solves by rows of
the small matrices, in effect solving x=b/a, where a,b,x are all scalars,
and a is never zero. So it will never actually see the singularity or
near-singularity problem.

Granted, the problem that it solves _is_ described by the huge A matrix,
which is near-singular in some cases. But does this signify that the problem
itself is ill-conditioned, or just that the huge A matrix formulation makes
it so. AFAICT, you can make any linear system singular, if you rearrange the
equations badly by multiplying with a wrong preconditioner. Certainly, we
didn't notice any problems with CFM=0, with the iterative solver. As I said,
the solutions look plausible. However, note that you can stop the iterative
solver very early, and the solution is still not that bad, because most of
the constraints are more-or-less satisfied, so perhaps that covers a lot of
problems.

Now, I don't claim to be an expert on matrix analysis, so perhaps I am
entirely wrong on this. Perhaps you can share some more light on what
happens if you never actually build the matrix. Any corrections to my
statements are warmly welcome.

Alen

> a few comments the CFM thing to maybe help you out. the basic role of
> CFM is to make close-to-singular matrices less singular (i.e. "more"
> positive definite) by adding numbers to the diagonal of the system
> matrix. this has two advantages:
>
> (1) a solution can be found even in cases where constraints are
> redundant, for example if there are too many contacts all trying to do
> the same thing. without CFM, tiny imprecisions in the factorizer and LCP
> solver would quickly blow up into major numerical errors, and the
> solution would be useless. you can see this in action if you make piles
> of objects with too many contact points, and set CFM to zero - the pile
> will twitch and jerk occasionally - this is numerical error being
> amplified. with some added CFM, the redundant constraints just share the
> load, and there is no problem.
>
> (2) with added CFM, the constraints become "springy". this can be viewed
> as a disadvantage as well, since often springyness is not what you want.
> but the amount of springyness can be precisely controlled, and this is
> good for modeling very stiff springs. note that, unlike springs modeled
> with externally added forces, springs modeled with CFM can be made very
> stiff without stability problems.
>
> now, an important point is that added CFM will benefit just about any
> matrix solving algorithm: direct methods will have less imprecision, and
> iterative methods will converge more quickly (or alternatively, will
> produce a better solution in a fixed number of iterations). so CFM is
> your friend!
>
> russ.
>
> --
> Russell Smith
> http://www.q12.org
>