Slug #1165: MinPoly over QQ: verification may be very slow - CoCoALib - CoCoA Project

Slug #1165

MinPoly over QQ: verification may be very slow

Added by Anna Maria Bigatti about 6 years ago. Updated over 5 years ago.

Status:

Closed

Priority:

Normal

Assignee:

Anna Maria Bigatti

Category:

Improving

Target version:

CoCoALib-0.99600

Start date:

12 Mar 2018

Due date:

% Done:

100%

Estimated time:

7.70 h

Spent time:

7.00 h

Description

The verification step after the modular algorithm may be very slow.
On the other side it is easy to construct examples on which MinPolyHeuristic fails (despite very unlikely in general).
Investigate on how to make a faster verification.

Related issues

History

#1 Updated by Anna Maria Bigatti about 6 years ago

% Done changed from 0 to 10

An impressive example is given by 87 points in QQ^3.
MinPoly takes ~4s and the verification take 44s on my Mac.

Improvement in doing NF at every Horner step instead of every second step. (used to be ~80s)

#2 Updated by Anna Maria Bigatti about 6 years ago

Tried with TwinFloat: good for the 87 points (10 times faster) bad for example QQ-rand (10 times slower)

#3 Updated by Anna Maria Bigatti about 6 years ago

Assignee set to Anna Maria Bigatti
% Done changed from 10 to 70

After many many experiments, code is settled as this:
- MinPolyQuot(f, I, x) makes the complete verification (over QQ)
- MinPolyQuot(f, I, x, N) makes N verifications mod N random primes ~2*10^9

(N in CoCoA-5 is an integer, and in CoCoALib is a VerificationLevel)

With 3 primes takes < 1s in all examples from "UsingMinPoly"