mersenneforum.org Reserved for MF - Sequence 3366
 Register FAQ Search Today's Posts Mark Forums Read

2021-09-02, 15:51   #507
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

499910 Posts

Quote:
 Originally Posted by charybdis The best solution is to make CADO oversieve a bit to reduce the matrix size; you can do this by adding tasks.filter.required_excess = 0.05 to the params file (experiment with different values to see what's best for your system).
I use 0.05 for C140-C160 to reduce matrix time when running all jobs on a single machine; I think EdH (who sieves on a "farm" of a dozen or more smaller machines) uses 0.08 or 0.10. The number is a percentage of total relations, so 0.05 asks CADO to make sure there are 5% more relations than strictly necessary for filtering; this "extra" yields a usefully smaller matrix. There are diminishing returns- do not expect a setting of 0.20 to make a 30-minute matrix!

A setting of 0.04 or 0.05 also reliably (?) produces enough relations for msieve filtering to work, useful if you're using that combination of CADO sievers and msieve postprocessing.

2021-09-02, 17:07   #508
EdH

"Ed Hall"
Dec 2009

3·7·191 Posts

Quote:
 Originally Posted by VBCurtis . . . I think EdH (who sieves on a "farm" of a dozen or more smaller machines) uses 0.08 or 0.10. . .
Actually, I've left that alone and have adjusted rels_wanted such that future runs exceed multiple filtering and Msieve will probably build a matrix, for >c130. c130 and less, I usually just let CADO-NFS finish. I prefer one filtering run and if I've exceeded the minimum required, it's a bonus.

 2021-09-02, 17:54 #509 bur     Aug 2020 79*6581e-4;3*2539e-3 401 Posts Then I'll use P=5M as well, seems like a good middleground between 3M(c195) and 10M(c220). CADO documentation says a large P generally results in better polys, but fewer. Ambiguous as most parameters seem to be... I'll do 10M-11M with nq=5^6. Is incr=420 good for that range?
2021-09-02, 17:55   #510
charybdis

Apr 2020

3×167 Posts

Quote:
 Originally Posted by VBCurtis The number is a percentage of total relations, so 0.05 asks CADO to make sure there are 5% more relations than strictly necessary for filtering...
This is a decent first approximation to what required_excess does in practice, but strictly this isn't quite correct. It's not a proportion of total relations, but rather the number of relations after the first singleton removal step, which must be at least 5% more than the number of ideals remaining at that stage. This will probably require slightly more than 5% additional raw relations.

Edit: just saw bur's post. I'm seeing about 700k thread-seconds per 1M range, or about 0.1% of what I estimate the sieving time ought to be on the same hardware. So 10M is still a "low" leading coefficient in this search and I'd stick with incr=420. If the returns above 10M aren't good then we can consider switching to larger incr.

Last fiddled with by charybdis on 2021-09-02 at 18:03

 2021-09-02, 18:18 #511 bur     Aug 2020 79*6581e-4;3*2539e-3 6218 Posts Slightly off-topic, but I'll take the chance to ask: what are singletons and ideals? In another thread you explained it as "...ideals are essentially the variables that our equations are in." Is it possible to explain it differently? Maybe it's a language problem, but how is an equation in a variable?
 2021-09-02, 18:58 #512 charybdis     Apr 2020 3·167 Posts An ideal is a subset of a ring that forms an additive subgroup and is closed under multiplication by arbitrary elements of the ring. But I don't think that's what you wanted We have an algebraic polynomial f(x), which in this case will be degree 5, and rational polynomial g(x). Our relations are (a,b) pairs for which the algebraic norm b^5*f(a/b) and rational norm b*g(a/b) are both smooth with respect to the chosen bounds. The aim is to find a set of relations for which the products of the algebraic and rational norms are both squares; we therefore need each prime to appear an even number of times in this set on each side. (0 is even of course.) There is a further complication which is that on the algebraic side two copies of the same prime p count as different if they correspond to different roots of the algebraic polynomial mod p; I think I explained this before. But why is this necessary? The answer is that the algebraic norms are actually being used to represent complex numbers in a certain number field, and it's the product of these numbers that needs to be square. The (prime, root) pairs correspond to *ideals* (in fact prime ideals) of a particular ring inside this number field. The same is true on the rational side, but the mathematics is much easier because the number field in question is the rational numbers - hence "rational side" - and the ring is the integers. For each prime p, there is a prime ideal of the integers consisting of the multiples of p, and all prime ideals of the integers are of this form. So on the rational side there is no complication with roots; each prime corresponds to a single ideal. Finding the required set of relations is equivalent to solving a huge system of linear equations mod 2 (i.e. finding linear dependencies of a huge matrix), since we need each ideal to appear an even number of times in our set. The unknowns/variables are "is this relation in the set", which can be either 0 (no) or 1 (yes). There is one equation for each ideal that appears in the relations. Say a particular ideal appears in relations 337, 590 and 4449, and no others. Then the equation will be "is rel 337 in the set" + "is rel 590 in the set" + "is rel 4449 in the set" = 0 (mod 2). The smaller the matrix, the easier it will be to solve. If an ideal only appears once as a factor in the entire dataset, then the relation it's in can't possibly be part of any set that contains each ideal an even number of times. This relation is called a singleton, and can be removed in filtering (we don't want to get rid of it forever, because if we sieve some more we might find another relation containing the given ideal). After all the singletons have been removed, we will have created new singletons, so we repeat this process until none are left. At this stage, we need there to be more relations (unknowns) than ideals (equations), else we won't be able to solve our system of equations. tasks.filter.required_excess = 0.05 means that CADO will only proceed with filtering if there are 5% more relations than ideals left at this stage. This is useful because if we have a large excess, we can afford to throw out some more (carefully chosen) relations in order to obtain a smaller matrix. ...and of course even this is an oversimplification as I haven't mentioned merging, cycles or quadratic characters. But it should hopefully give some idea of what's going on. Last fiddled with by charybdis on 2021-09-02 at 19:14
2021-09-03, 01:57   #513
charybdis

Apr 2020

3×167 Posts

Quote:
 Originally Posted by charybdis I'll do 0-5M with P=5M, nq=15625, incr=420, sopteffort=10, ropteffort=100.
Best was 4.02e-15 which doesn't even beat the c202 record. I'll try the same range with P=10M; not expecting it to be better but I'd like to see how the performance compares.

 2021-09-03, 17:39 #514 bur     Aug 2020 79*6581e-4;3*2539e-3 401 Posts Thanks, that's very helpful again. So we are not looking directly at the prime factors of a and b to create the squares but at the ideals?
 2021-09-03, 20:22 #515 charybdis     Apr 2020 7658 Posts Yes: technically on the algebraic side we're looking at factorizations of (non-prime) ideals rather than of numbers. The product of two ideals is the set of all the finite sums of products of elements of the two ideals (we'd like it to be just the set of products of the elements, but that might not be an ideal). In number fields we don't usually have a direct equivalent of unique prime factorization: for example, in $$\mathbb{Q}[\sqrt{-5}]$$, we have $$6 = (2)(3) = (1+\sqrt{-5})(1-\sqrt{-5})$$ which is not unique - and yes, all those factors are indeed prime in the required sense. However, if instead we look at factorizing ideals into prime ideals, we do have unique factorization, or at least something close enough. The reason that NFS is feasible is that for the ideals we're interested in, there is a direct correspondence between the factorization of the ideal into prime ideals and the prime factorization of an integer called the norm of the ideal. This is the (prime, root) <--> (prime ideal) correspondence I mentioned in the previous post. The norm is the number b^d*f(a/b) that you're familiar with by now.
 2021-09-04, 01:22 #516 charybdis     Apr 2020 3·167 Posts That's more like it: Code: n: 131059381160969890473184300494609882864431978456309837392557442177052630795870868382351497139096300267026719895523089453234540027837272339241326353564822104741922921032481193771448768282517397405699723 skew: 272726903.707 c0: 3419281390608846968778268338419370567158813629362 c1: 258854464423997783647767547760287821024753 c2: -767236135068739573740612500186036 c3: -3287457778282621690365713 c4: 10211483437143594 c5: 12458880 Y0: -575476667446322731628680355694195898900 Y1: 2846500471772809349499599 Score 4.807e-15. Nothing else above 4.2 so this was a lucky hit.
 2021-09-04, 02:18 #517 swellman     Jun 2012 320310 Posts Nice one! Finishing my search Sunday then I’m done regardless of the results.

 Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 And now for something completely different 17 2017-06-13 03:49 RichD Aliquot Sequences 36 2013-11-29 07:03 petrw1 Lone Mersenne Hunters 82 2010-01-11 01:57 roger Puzzles 16 2006-10-18 19:52 Citrix Puzzles 5 2005-09-14 23:33

All times are UTC. The time now is 20:17.

Fri Oct 22 20:17:17 UTC 2021 up 91 days, 14:46, 0 users, load averages: 2.04, 1.84, 1.90

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.