Slug #866: implicit, ImplicitHypersurface: improve output verification - CoCoALib - CoCoA Project

Slug #866

implicit, ImplicitHypersurface: improve output verification

Added by John Abbott about 8 years ago. Updated about 1 month ago.

Status:

In Progress

Priority:

Normal

Assignee:

Category:

Tidying

Target version:

CoCoALib-0.99880

Start date:

13 Apr 2016

Due date:

% Done:

20%

Estimated time:

20.00 h

Spent time:

3.55 h

Description

The current impl of SliceCoreQQ is simple rather than efficient.
It uses modular+CRT to build the answer.
Currently if RatReconstructPoly succeeds, it checks whether the answer is right (but substitution). Does the substitution ever fail? (if so, it could be very costly).

It would be nice not to treat the first prime as a special case (i.e. just have a loop which keeps trying successive primes). Investigate!

Related issues

History

#1 Updated by John Abbott about 8 years ago

Related to Feature #651: Optimized algorithms for implicitization (slicing algorithm, elim, subalgebra..) added

#2 Updated by John Abbott about 8 years ago

Status changed from New to In Progress
% Done changed from 0 to 10

The example below takes about 12s on my computer, but only about 0.25s if the coeff field is ZZ/(32003). Why is it almost 50 times slower? Internally it should be using modular+CRT+FTRR and supposedly the FTRR phase is cheap.

k ::= QQ;
kst ::= k[s,t];
use kst;
-- Dongming example 13:
L := [ s^3+3*t^3-3*s^2-6*t^2+6*s+3*t-1,
      3*s^3+t^3-6*s^2+3*s+3*t,
      -3*s^3*t^3-3*s^3*t^2+15*s^2*t^3+6*s^3*t-18*s^2*t^2-15*s*t^3+9*s^2*t+27*s*t^2-3*s^2-18*s*t-3*t^2+3*s+3*t];
P ::= k[x,y,z];
t0 := CpuTime();
f := ImplicitHypersurface(P, L, "Direct");
println "Time taken: ", TimeFrom(t0);

#3 Updated by Anna Maria Bigatti about 8 years ago

% Done changed from 10 to 20

John Abbott wrote:

The example below takes about 12s on my computer, but only about 0.25s if the coeff field is ZZ/(32003). Why is it almost 50 times slower? Internally it should be using modular+CRT+FTRR and supposedly the FTRR phase is cheap.

Yes, I had observed in many examples that FTRR is amazingly cheap.
However the final verification process (actual substitution) can be quite slow.
(maybe I could add a flag to print in CoCoA these logging informations)

#4 Updated by John Abbott about 8 years ago

I suggest adding a probabilistic check of correctness: use the parametric formulas to generate a random (numerical) point, and verify that the point satisfies the implicit equation. In principle one could generate several random points and test them all; or perhaps generate several random points, and test just the simplest looking one(s)?

It may also be nice to offer the user the possibility to say that the final "absolute test" may be skipped (to save time).

#5 Updated by Anna Maria Bigatti about 8 years ago

John Abbott wrote:

I suggest adding a probabilistic check of correctness: use the parametric formulas to generate a random (numerical) point, and verify that the point satisfies the implicit equation. In principle one could generate several random points and test them all; or perhaps generate several random points, and test just the simplest looking one(s)?

It may also be nice to offer the user the possibility to say that the final "absolute test" may be skipped (to save time).

True.
But I'd like another try: I'm planning to try to implement a sort of recursive Horner. Maybe that will give a decent enough improvement.
(I have a little more time this week, I hope I can implement it)

#6 Updated by Anna Maria Bigatti about 8 years ago

Anna Maria Bigatti wrote:

But I'd like another try: I'm planning to try to implement a sort of recursive Horner. Maybe that will give a decent enough improvement.

working on it now

#7 Updated by John Abbott about 8 years ago

I seem to recall vaguely seeing a paper by Mourrain (or someone in his group) possibly about this. I think the question was how best to exploit sparseness. I may be completely wrong though; I don't think I read beyond the abstract anyway.

#8 Updated by Anna Maria Bigatti about 8 years ago

Anna Maria Bigatti wrote:

But I'd like another try: I'm planning to try to implement a sort of recursive Horner. Maybe that will give a decent enough improvement.

working on it now

:-( :-(
no, it doesn't work at all well.
:-( :-(
General implementation is fine and goes
very well in case of 1 param,
well in case of 2 params,
not well for more.
Now, it may improve using geobuckets, but I'm no longer hopeful for a great improvement (without a major new idea which might be worth a paper by itself...)

#9 Updated by Anna Maria Bigatti about 8 years ago

I checked in IsZeroEvalHorner in case you want to play with it.
The call is currently commented out. Just look for it in TmpImplicit.C.

#10 Updated by John Abbott almost 8 years ago

I have not yet had time to look at your horner code. Anyway, I would expect it work fairly well provided the "variables are evaluated in the right order": my expectation is that indets which map to simpler values should be the outermost ones for the multivariate horner implementation.

I'm pretty certain that some orders will be better than others, but do not really have any idea how much better... Could a factor of 2 be possible? Even greater gain?