20090411, 13:41  #56 
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 JT. 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 20090411 at 13:47 
20090417, 22:51  #57 
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 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 P1/P+1/ECM available, skipping commencing number field sieve (268digit 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 <murphy_integrand>, params=0x7fff8c1621a0, range=0x1d356df0) at common/integrate.c:282 #3 0x0000000000453362 in de_run (aux=0x7fff8c162ca8, func=0x4257c8 <murphy_integrand>, params=0x7fff8c1621a0, endpoints=0x7fff8c161f60, num_endpoints=9) at common/integrate.c:438 #4 0x00000000004537e9 in integrate_run (aux=0x7fff8c162ca8, func=0x4257c8 <murphy_integrand>, 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 20090417 at 22:55 
20090418, 00:36  #58 
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.

20090418, 00:57  #59 
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. 
20090418, 23:19  #60 
Tribal Bullet
Oct 2004
3543_{10} Posts 
Okay, keep me posted. The new filtering only kicks in if you had to move to 3cliques and beyond when using older msieve versions

20090419, 03:52  #61 
Jul 2003
So Cal
5×11×41 Posts 

20090419, 04:23  #62 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
11·881 Posts 
As requested, I've rerun the filtering for 5,362+, too. The results are posted sidebyside. 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.

20090420, 18:09  #63 
Nov 2008
912_{16} 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 Last fiddled with by 10metreh on 20090420 at 18:46 
20090420, 18:34  #64 
"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 
20090420, 18:37  #65 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
25DB_{16} 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 12) 
20090420, 18:42  #66  
Tribal Bullet
Oct 2004
3·1,181 Posts 
Quote:
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 20090420 at 18:49 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Msieve 1.53 feedback  xilman  Msieve  149  20181112 06:37 
Msieve 1.50 feedback  firejuggler  Msieve  99  20130217 11:53 
Msieve v1.48 feedback  Jeff Gilchrist  Msieve  48  20110610 18:18 
Msieve 1.43 feedback  Jeff Gilchrist  Msieve  47  20091124 15:53 
Msieve 1.42 feedback  Andi47  Msieve  167  20091018 19:37 