Project

General

Profile

Feature #651

Optimized algorithms for implicitization (slicing algorithm, elim, subalgebra..)

Added by Anna Maria Bigatti over 9 years ago. Updated about 9 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
New Function
Target version:
Start date:
13 Nov 2014
Due date:
% Done:

10%

Estimated time:
100.00 h
Spent time:

Description

(may keywords in the title to simplify future searches ;-)

Investigate new algorithms for implicitization, i.e. finding the kernel of

k[x_1,...,x_n] --> k[f_1,..,f_n]


Related issues

Related to CoCoA-5 - Feature #600: efficient subalgebrasNew2014-07-16

Related to CoCoALib - Slug #866: implicit, ImplicitHypersurface: improve output verificationIn Progress2016-04-13

History

#1 Updated by John Abbott over 9 years ago

JAA has implemented in C++/CoCoALib (first prototypes of): ImplicitDirect (with variants LPP and WithCond), also ImplicitByPoints (with variant @LPP).

No documentation; no formal tests.

These fns are also available from CoCoA-5 (no documentation!)

#2 Updated by John Abbott over 9 years ago

The very latest version of ImplicitByPoints3 does occasionally go a little faster than ImplicitDirectLPP2, but it also seems to display worse empirical complexity (i.e. it become slower than ImplicitDirectLPP2 as the inputs get bigger). I think this may be because ImplicitByPoints3 works with an essentially random matrix (which has to be triangularised), whereas I believe that ImplicitDirectLPP2 builds a "matrix" which is no far from triangular (and so needs little work to be triangularized).

I also point out that ImplicitByPoints3 does not verify its answer while the result of ImplicitDirectLPP2 is guaranteed correct.

Overall, I conclude that ImplicitByPoints probably cannot be refined enough to make it significantly better than ImplicitDirect -- not even in certain special circumstances.

It could be that profiling ImplicitByPoints3 would let me improve a bit further, but the observed poorer empirical complexity (with "heuristic explanation") is discouraging.

Note profiling on a GNU/linux VM showed that the main cost was accessing entries in the std::map<PPMonoidElem, int>

#3 Updated by John Abbott over 9 years ago

At a meeting yesterday it was decided that effort should be put into developing/refining ImplicitDirectWithCond. Anna did report disappointing performance from the initial implementation -- she will investigate the cause.

#4 Updated by Anna Maria Bigatti over 9 years ago

John Abbott wrote:

Anna did report disappointing performance from the initial implementation -- she will investigate the cause.

Indeed I was running my (supposedly random) test in a particularly unfavourable case for ImplicitDirect.
So it not a problem with overhead.
so: now comparing with other tests.

#5 Updated by John Abbott over 9 years ago

One problem with ImpliciDirectWithCond is that the normal form computations take too long. Here is an idea which might make the NF computations a bit faster (at the risk of creating some false positives).

Instead of computing NF modulo the ideal I we could compute modulo I+J (or better I+J1 and I+J2) where the ideal J is chosen to be convenient, e.g. J = ideal(s-1234).

If we can do this in such a way that there are not too many false positives then I think we could gain speed.

#6 Updated by Anna Maria Bigatti over 9 years ago

I'm running tests with the profiler on our linux virtual machine.
One surprise was that the profiler gave a mysterious

[19]    12.5    0.01    0.47  695808        RingDistrMPolyInlFpPPImpl::myNegate
                0.00    0.47  695808/851237 DistrMPolyInlFpPP::operator=

but those "=" calls (doing nothing) do not seem relevant: I commented out the " = " line in RingDistrMPolyInFpPP (in our context it is called only with two identical arguments) and the timing was effectively identical.
That surprised me a bit for two reasons: I expected...
1 - the profiler to be more reliable
2 - 695808 (useless) function calls to be more time consuming

#7 Updated by Anna Maria Bigatti about 9 years ago

I changed all ring names into Kt and Kx in TmpImplicit.C

#8 Updated by John Abbott almost 8 years ago

  • Related to Slug #866: implicit, ImplicitHypersurface: improve output verification added

Also available in: Atom PDF