Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: factorize command really slow (or sometimes fast??!)
PostPosted: Fri Nov 23, 2007 5:08 pm 

Joined: Fri Nov 23, 2007 4:51 pm
Posts: 1
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).


Report this post
Top
 Profile  
Reply with quote  
 Post subject: Re: different spped for gcd and factorize
PostPosted: Mon Dec 03, 2007 1:03 pm 

Joined: Wed May 25, 2005 4:16 pm
Posts: 275
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.


Report this post
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

It is currently Fri May 13, 2022 10:56 am
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group