[ODE] Speeding up iterative techniques

[Russ Smith]

> A question about the LCP solver: given that I will be giving it the same A
> several times, is there a way to save the decomposition of the matrix
> and...

yes and no ... ODE's LCP solver is given low and high bounds for each
solution variable. some of these bounds are -inf...inf. if the whole
matrix had bounds -inf...inf then the problem would no longer be LCP, it
would be a straight A*x=b linear problem. ODE's LCP solver takes the
following approach: first group all the unbounded -inf...inf constraints
together, and do a matrix decomposition on that. then for the remaining
bounded constraints, go through dantzig's algorithm, switching indexes in
and out of the active set and solving various sub-problems. if you wanted
to re-solve the same A matrix for different right hand sides, then you can
re-use that initial factorization, assuming that the unbounded indexes
remain unbounded. it is probably a lot harder to reuse the subsequent work
in the dantzig algorithm, as the path taken thought the 'active index'
space is likely to be different. perhaps a clever caching scheme could be
invented, but it's likely to be complicated. anyway, reusing the initial
factorization will give the best savings and will be relatively simple -
but note that i have not actually implemented a way to do this.

russ.

--
Russ Smith
http://www.q12.org/