Project

General

Profile

Slug #874

factor: too slow on largish multivariate poly

Added by John Abbott almost 8 years ago. Updated about 5 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
Category:
Improving
Target version:
Start date:
03 May 2016
Due date:
% Done:

20%

Estimated time:
Spent time:

Description

Mario generates lots of multivariate polys (over QQ); most of them are irreducible. He reports that factorization of these polys is sometimes very slow.

Investigate, and improve the impl.


Related issues

Related to CoCoA-5 - Slug #875: Interpreter is too slow reading a big polynomialIn Progress2016-05-03

Related to CoCoALib - Feature #885: IsIrred3: fast 3-way irred test (returning bool3)In Progress2016-05-24

History

#1 Updated by John Abbott almost 8 years ago

Mario has given me an example poly. The poly ring has 84 indets; the poly itself uses 69 indets, and has about 6800 terms. Degree is relatively low: 7. 43 of the indets appear just linearly; and 17 appear quadratically.

Currently factorization takes about 85s (on my MacBook).

#2 Updated by John Abbott almost 8 years ago

  • Status changed from New to In Progress
  • Assignee set to John Abbott
  • % Done changed from 0 to 10

Computing all contents takes about 44s; and computing contents wrt all indets which appear just linearly takes about 33s.

ContentWRT took varying amounts of time: fastest was about 0.19s, slowest was about 0.89s.

It should be enough to compute content for some "linear" indet, see that the content is 1, and then deduce that the poly is irred. This should be possible within 1s; much better than 85s!

#3 Updated by John Abbott almost 8 years ago

  • Subject changed from factor" too slow on largish multivariate poly to factor: too slow on largish multivariate poly

Mario has just sent me an even bigger polynomial to try: 100 indets, about 127000 terms, total degree 9.

He also mentioned that some of his polynomials are reducible, but almost always the factors are a power product and some big irreducible poly.

#4 Updated by John Abbott almost 8 years ago

  • Related to Slug #875: Interpreter is too slow reading a big polynomial added

#5 Updated by John Abbott almost 8 years ago

  • % Done changed from 10 to 20

I have implemented a prototype "heuristic" irred test which returns a bool3.

First it checks for a non-triv common factor among the PPs in the support; if found, we know the poly is reducible.

Then it looks for indets which appear linearly; if there are none, it gives up and returns uncertain3.

Otherwise it picks the indet which appears in fewest terms in the poly, and computes content wrt to that indet. If content is not 1 then poly is reducible; otherwise it is irred.

On Mario's 2 polys this seems sufficient, and it faster than the previous code for IsIrred.

#6 Updated by John Abbott almost 8 years ago

  • Related to Feature #885: IsIrred3: fast 3-way irred test (returning bool3) added

#7 Updated by John Abbott over 6 years ago

  • Target version changed from CoCoALib-0.99560 to CoCoALib-0.99600

#8 Updated by John Abbott almost 6 years ago

  • Target version changed from CoCoALib-0.99600 to CoCoALib-0.99650 November 2019

#9 Updated by John Abbott about 5 years ago

  • Target version changed from CoCoALib-0.99650 November 2019 to CoCoALib-1.0

Also available in: Atom PDF