Singular
https://www.singular.uni-kl.de/forum/

factorize command really slow (or sometimes fast??!)
https://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1652		 Page 1 of 1
Author:  jbmohler [ Fri Nov 23, 2007 5:08 pm ]
Post subject:  factorize command really slow (or sometimes fast??!)
I've been noticing that singular's factoring is grotesquely slow at times. What's really strange is that the speed fluctuates wildly. I've observed this speed fluctuation other places in singular as well. I'm a sage user and I thought it might be a manifestation of:
http://www.sagetrac.org/sage_trac/ticket/872
but the version I'm on has that issue fixed. I also tried the vanilla ix86-Linux .tar.gz from singular's web-site and it also is affected (version 3-0-4).

Here's where I'm seeing the bug: Try to factor the following fairly modest 8 variable polynomial. I'm not going to hazard a guess how long the factorize will take.

Code:
ring R=0,(p10,g0,g1,g2,g3,g4,X1,X2),dp;
poly t=-p10^170*X1^10*X2^10+p10^130*X1^10*X2^5+p10^130*X1^5*X2^10-p10^90*X1^5*X2^5+p10^80*X1^5*X2^5-p10^40*X1^5-p10^40*X2^5+1;
factorize(t);


Now, Up-Arrow-Enter at the singular prompt to "factorize(t);" again and you'll wait some very different time to get the same answer. I've seen the answer nearly instantaneously some times, but other times I'm waiting 5 minutes (or more).
Author:  hannes [ Mon Dec 03, 2007 1:03 pm ]
Post subject:  Re: different spped for gcd and factorize
the factorization depends on 2 main routines: gcd (for content, squre free etc.)
and the factorization of a squerefree polynomial.
Both depends heavily on random values - so it is quite natural
to have different timing for each run.

The gcd is (by default) ezgcd (from factory/fac_ezgcd.cc)
which substitutes random values into all but one variable and tries
to lift the univariate gcd to the real one.
This could be improved by a better heuristic for the main variable.

The factorization of a squerefree polynomial (ZFactorizeMulti from
factory/fac_multivar.cc) also substitutes random values
to reduce the polynomial to an univarite one.
Here also bad evalution point may occur, but also the number of factors
are important.

So it is not a bug, it is missing some good heuristics at several points:
decide FAST, if a random point is a good one.
Page 1 of 1 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/