mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-04-11, 13:41   #56
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

348910 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-04-17, 22:51   #57
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32·227 Posts
Default

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 <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 2009-04-17 at 22:55
frmky is offline   Reply With Quote
Old 2009-04-18, 00:36   #58
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

1101101000012 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2009-04-18, 00:57   #59
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

32×227 Posts
Default

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.
frmky is offline   Reply With Quote
Old 2009-04-18, 23:19   #60
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

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
jasonp is offline   Reply With Quote
Old 2009-04-19, 03:52   #61
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

111111110112 Posts
Default

Quote:
Originally Posted by frmky View Post
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.
frmky is offline   Reply With Quote
Old 2009-04-19, 04:23   #62
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2009-04-20, 18:09   #63
10metreh
 
10metreh's Avatar
 
Nov 2008

1001000100102 Posts
Unhappy 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
File Type: txt msieve.txt (8.9 KB, 82 views)

Last fiddled with by 10metreh on 2009-04-20 at 18:46
10metreh is offline   Reply With Quote
Old 2009-04-20, 18:34   #64
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29·41 Posts
Default

Next time, attach the log and only post the relevant lines between code tags.

http://www.mersenneforum.org/showpos...4&postcount=20
smh is offline   Reply With Quote
Old 2009-04-20, 18:37   #65
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Default

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)
Batalov is offline   Reply With Quote
Old 2009-04-20, 18:42   #66
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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
jasonp is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 11:28.

Fri Oct 23 11:28:13 UTC 2020 up 43 days, 8:39, 0 users, load averages: 1.28, 1.40, 1.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.