mersenneforum.org Msieve 1.41 Feedback
 Register FAQ Search Today's Posts Mark Forums Read

 2009-04-11, 13:41 #56 jasonp Tribal Bullet     Oct 2004 3×1,181 Posts Actually, the problem with the Laguerre code I wrote seems to be that for some inputs I get cycling behavior. According to NR this is supposed to be rare, but the code they add to break out of the cycling behavior doesn't work very well. Even simple polynomials cause trouble (try 3x^5 - 6292 , first reported by Torbjorn Alm, or x^5 + 12 , reported by FactorEyes). Occaisionally that cycling causes an infinity, then an exception soon afterwards. My guess is that you get cycling behavior when multiple roots have similar magnitudes. There are lots of references on 'homotopy continuation', sounds like I either need to use that or a globally convergent method like J-T. Perhaps Laguerre's method has a fractal basin of convergence around complex roots, for some polynomials; anyone care to draw a picture? :) Last fiddled with by jasonp on 2009-04-11 at 13:47
 2009-04-17, 22:51 #57 frmky     Jul 2003 So Cal 5×11×41 Posts I tried 1.41 on the complete relation set for 2,908+, but didn't get very far. It segfaults shortly after starting it. Here's the info. Edit: Ah, probably the error mentioned above. msieve.fb: Code: N 1523730872006476065948363676129458676149278444031460349472566973967334168144122839831601974268424799167249117433966350288390769855219490595979807225811317497929238722439950754301281289518517474506321086318238010563399750224881258591495613213552981037427691447296080033 A6 4 A5 0 A4 0 A3 0 A2 0 A1 0 A0 1 R1 1 R0 -2854495385411919762116571938898990272765493248 FAMAX 90000000 FRMAX 90000000 SRLPMAX 4294967296 SALPMAX 4294967296 gdb output: Code: Starting program: /work/gnfs/2p908_141/msieve_d -nc1 -nc2 -v [Thread debugging using libthread_db enabled] [New Thread 46912496301008 (LWP 10879)] Msieve v. 1.41 Fri Apr 17 15:40:10 2009 random seeds: 8a7409a0 75e06769 factoring 1523730872006476065948363676129458676149278444031460349472566973967334168144122839831601974268424799167249117433966350288390769855219490595979807225811317497929238722439950754301281289518517474506321086318238010563399750224881258591495613213552981037427691447296080033 (268 digits) no P-1/P+1/ECM available, skipping commencing number field sieve (268-digit input) Program received signal SIGSEGV, Segmentation fault. [Switching to Thread 46912496301008 (LWP 10879)] 0x000000000044f574 in dickman (aux=0x7fff8c162cc8, arg=nan(0x8000000000000)) at common/dickman.c:151 151 num_coeffs = line->num_coeffs; (gdb) where #0 0x000000000044f574 in dickman (aux=0x7fff8c162cc8, arg=nan(0x8000000000000)) at common/dickman.c:151 #1 0x0000000000425b98 in murphy_integrand (r=-nan(0x8000000000000), h=0, params=0x7fff8c1621a0) at gnfs/poly/size_score.c:460 #2 0x000000000045289d in de_run_core (aux=0x7fff8c162ca8, func=0x4257c8 , params=0x7fff8c1621a0, range=0x1d356df0) at common/integrate.c:282 #3 0x0000000000453362 in de_run (aux=0x7fff8c162ca8, func=0x4257c8 , params=0x7fff8c1621a0, endpoints=0x7fff8c161f60, num_endpoints=9) at common/integrate.c:438 #4 0x00000000004537e9 in integrate_run (aux=0x7fff8c162ca8, func=0x4257c8 , params=0x7fff8c1621a0, endpoints=0x7fff8c161f60, num_endpoints=9) at common/integrate.c:518 #5 0x0000000000426029 in analyze_poly_murphy (integ_aux=0x7fff8c162ca8, dickman_aux=0x7fff8c162cc8, rpoly=0x7fff8c162370, root_score_r=0, apoly=0x7fff8c1622e0, root_score_a=1.9466829539863062, skewness=1, result=0x7fff8c162c58) at gnfs/poly/size_score.c:536 #6 0x00000000004220c1 in analyze_poly (config=0x7fff8c162c70, poly=0x7fff8c162480) at gnfs/poly/polyutil.c:99 #7 0x0000000000422864 in analyze_one_poly (obj=0x1d33e250, rpoly=0x7fff8c163170, apoly=0x7fff8c162d80, skewness=1) at gnfs/poly/polyutil.c:124 #8 0x000000000041934f in factor_gnfs (obj=0x1d33e250, n=0x7fff8c163720, factor_list=0x7fff8c1637a0) at gnfs/gnfs.c:79 #9 0x0000000000403d5c in msieve_run_core (obj=0x1d33e250, n=0x7fff8c163720, factor_list=0x7fff8c1637a0) at common/driver.c:147 #10 0x00000000004040fe in msieve_run (obj=0x1d33e250) at common/driver.c:238 #11 0x0000000000402a1f in factor_integer ( buf=0x7fff8c164240 "15237308720064760659483636761294586761492784440314603494725669739673341681441228398316019742684247991672491174339663502883907698552194905959798072258113174979292387224399507543012812895185174745063210"..., flags=771, savefile_name=0x0, logfile_name=0x0, nfs_fbfile_name=0x0, seed1=0x7fff8c16423c, seed2=0x7fff8c164238, max_relations=0, nfs_lower=0, nfs_upper=0, cpu=cpu_opteron, cache_size1=65536, cache_size2=2097152, num_threads=0) at demo.c:177 #12 0x00000000004038f0 in main (argc=4, argv=0x7fff8c164518) at demo.c:496 (gdb) print num_coeffs $1 = 2146959360 (gdb) print line$2 = (dickman_line_t *) 0xfffffffc1d359cf0 (gdb) print line->num_coeffs Cannot access memory at address 0xfffffffc1d359cf0 Last fiddled with by frmky on 2009-04-17 at 22:55
 2009-04-18, 00:36 #58 jasonp Tribal Bullet     Oct 2004 3×1,181 Posts There's a call to analyze_one_poly in gnfs/gnfs.c which is the root of the problem (pun intended, since it's yet another SNFS polynomial whose roots give trouble to the polynomial rootfinder). Things should work if you comment out the call.
 2009-04-18, 00:57 #59 frmky     Jul 2003 So Cal 5·11·41 Posts Thanks. The filtering of 2,908+ with the full relation set is running with 1.41 now. Let's see how well the changes do with this huge set. I'm also rerunning the filtering on 11,244+. It's somewhat oversieved, but I'm not sure it's enough to trigger your changes.
 2009-04-18, 23:19 #60 jasonp Tribal Bullet     Oct 2004 354310 Posts Okay, keep me posted. The new filtering only kicks in if you had to move to 3-cliques and beyond when using older msieve versions
2009-04-19, 03:52   #61
frmky

Jul 2003
So Cal

5×11×41 Posts

Quote:
 Originally Posted by frmky I'm also rerunning the filtering on 11,244+. It's somewhat oversieved, but I'm not sure it's enough to trigger your changes.
It wasn't. I got the same matrix as with 1.39.

 2009-04-19, 04:23 #62 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 11·881 Posts As requested, I've re-run the filtering for 5,362+, too. The results are posted side-by-side. This just goes to support Jason's prediction that after a certain starting max_weight the matrix changes very little. The w<=30 was luckily that point.
2009-04-20, 18:09   #63
10metreh

Nov 2008

91216 Posts
Oops...

An error I've heard about but never seen before just occurred:

Code:
Mon Apr 20 18:48:31 2009  matrix is 113103 x 113292 (32.1 MB) with weight 10904624 (96.25/col)
Mon Apr 20 18:48:31 2009  sparse part has weight 7510031 (66.29/col)
Mon Apr 20 18:48:37 2009  filtering completed in 2 passes
Mon Apr 20 18:48:38 2009  matrix is 112810 x 112775 (32.1 MB) with weight 10886812 (96.54/col)
Mon Apr 20 18:48:38 2009  sparse part has weight 7501649 (66.52/col)
Mon Apr 20 18:48:44 2009  read 112775 cycles
Mon Apr 20 18:48:49 2009  matrix is 112810 x 112775 (32.1 MB) with weight 10886812 (96.54/col)
Mon Apr 20 18:48:49 2009  sparse part has weight 7501649 (66.52/col)
Mon Apr 20 18:48:49 2009  matrix must have more columns than rows
And with only 35 more rows than columns! I removed a few relations and ended up with 5000 more rows than columns. Does this mean that oversieving is the best solution to this?
Attached Files
 msieve.txt (8.9 KB, 123 views)

Last fiddled with by 10metreh on 2009-04-20 at 18:46

 2009-04-20, 18:34 #64 smh     "Sander" Oct 2002 52.345322,5.52471 29·41 Posts Next time, attach the log and only post the relevant lines between code tags. http://www.mersenneforum.org/showpos...4&postcount=20
 2009-04-20, 18:37 #65 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 25DB16 Posts As the number of collected relations grows, there are four "zones": 1) far too few relations; then -nc1 doesn't produce cycles and asks for more relns => Sieve some more; 2) (rarely visited; you are here!) almost enough relations; -nc1 makes cycles, -nc2 builds a matrix, cleans it up and then the matrix is not useable => Sieve some more; 3) convergent zone; here's some freedom of choice: with more relns, the matrix gets better and better, but it is well established that you generally do not save any overall time anymore => Build the matrix and do -nc2, -nc3 4) far too many relations => trim free relations from the end of .dat file (these are short lines), then trim some more, goto zone 3). But not too much or you will end up in zones 1-2)
2009-04-20, 18:42   #66
jasonp
Tribal Bullet

Oct 2004

3·1,181 Posts

Quote:
 Originally Posted by 10metreh And with only 35 more rows than columns! I removed a few relations and ended up with 5000 more rows than columns. Does this mean that oversieving is the best solution to this?
For now, I think yes. You have just enough relations to create a matrix, but the filtering deliberately creates a few extra very heavy columns. When the linear algebra starts, those columns are stripped away and that modifies the number of empty rows. The problem is that if there are very few columns to spare, too many other columns become empty and the nullspace of the matrix is wiped out.

Fixing this problem requires either making the filtering produce a matrix that is deliberately larger, or making the filtering smart enough to realize this is about to happen.

PS: I see that Serge has already explained this better than I have. Note that you don't have to manually delete relations from the data file anymore; -nc1 has optional arguments that let you ignore the last few relations in the list.

Last fiddled with by jasonp on 2009-04-20 at 18:49

 Similar Threads Thread Thread Starter Forum Replies Last Post xilman Msieve 149 2018-11-12 06:37 firejuggler Msieve 99 2013-02-17 11:53 Jeff Gilchrist Msieve 48 2011-06-10 18:18 Jeff Gilchrist Msieve 47 2009-11-24 15:53 Andi47 Msieve 167 2009-10-18 19:37

All times are UTC. The time now is 14:38.

Sat Jan 22 14:38:04 UTC 2022 up 183 days, 9:07, 0 users, load averages: 1.40, 1.22, 1.18