Opened 7 years ago

Closed 7 years ago

Last modified 7 years ago

#9400 closed enhancement (fixed)

modify the NumberField constructor to pass in optional integer B such that all the internal pari routines will replace the discriminant by its gcd with B, making some things massively faster.

Reported by: was Owned by: jdemeyer
Priority: major Milestone: sage-4.6
Component: number fields Keywords: PARI number field
Cc: jdemeyer Merged in: sage-4.6.alpha1
Authors: William Stein, Jeroen Demeyer Reviewers: Jeroen Demeyer, John Cremona
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by jdemeyer)

Also:

  • ReSTify residue class fields
  • massively optimize reduction modulo a prime (e.g., the first interesting example I tried, I got a speedup of a factor of 500,000! Yes half a million times faster!).

Parts of this patch have been moved to #9764.

Apply only 9400_combined.patch and apply it on top of the patches from #9343. See also http://wiki.sagemath.org/NewPARI.

Attachments (5)

trac_9400.patch (47.3 KB) - added by was 7 years ago.
apply only this patch (which also addresses the referees issue with hash)
9400_maximize_at_primes.patch (31.2 KB) - added by jdemeyer 7 years ago.
Patch for the "maximize at primes" part, rebased to sage-4.6.prealpha1 (see #9343)
9400_jd_review.patch (23.2 KB) - added by jdemeyer 7 years ago.
Apply on top of 9400_maximize_at_primes.patc
9400_docfix.patch (2.3 KB) - added by jdemeyer 7 years ago.
Apply on top of previous 2 patches, small documentation fixes
9400_combined.patch (47.3 KB) - added by jdemeyer 7 years ago.
All 3 patches combined (apply only this patch)

Download all attachments as: .zip

Change History (40)

comment:1 Changed 7 years ago by was

  • Description modified (diff)

comment:2 Changed 7 years ago by was

  • Description modified (diff)

comment:3 Changed 7 years ago by was

Example of what this makes possible:

~wstein/bin/sagedb
----------------------------------------------------------------------
| Sage Version 4.4.4, Release Date: 2010-06-23                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: R.<x> = QQ[]
sage: f = (x^20 - 3*x^19 - 29*x^18 + 91*x^17 + 338*x^16 - 1130*x^15 -
2023*x^14 +
....: 7432*x^13 + 6558*x^12 - 28021*x^11 - 10909*x^10 + 61267*x^9 + 6954*x^8 -
....: 74752*x^7 + 1407*x^6 + 46330*x^5 - 1087*x^4 - 12558*x^3 - 942*x^2 +
....: 960*x + 148)
sage: K.<a> = NumberField(f^2+2, maximize_at_primes=[2])
sage: K.degree()
40
sage: time z = K.factor(2)
CPU times: user 0.59 s, sys: 0.01 s, total: 0.60 s
Wall time: 0.60 s
sage: time k = z[0][0].residue_field()
CPU times: user 1.68 s, sys: 0.03 s, total: 1.71 s
Wall time: 1.98 s
sage: time k(a^3+3)
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s
abar^3 + 1

comment:4 Changed 7 years ago by was

  • Status changed from new to needs_review

comment:5 Changed 7 years ago by jdemeyer

It is clear from a very first look at the patch that this will massively conflict with #9343 (why did nobody point this out to me earlier???). Personally, I would prefer to postpone the last two points of the description, i.e.

  • implement hashing for number field ideals that isn't a stupid string repr, hence vastly faster
  • make number field ideals *not* print in reduced form; this will look uglier, but is massively faster and more sensible for any real applications, as people learned constantly at sage days 22.

and do them after #9343 is merged (I also want to change the hashing of PARI objects, see #9667). Also, I'm personally not completely convinced about the best way to print NumberFieldIdeals? (see also my post at sage-devel).

comment:6 follow-up: Changed 7 years ago by was

It is clear from a very first look at the patch that this will massively conflict with #9343 (why

I'm sure this will be easy to merge with #9343. It's probably best to get 9343 in first, since it is much more difficult, then rebase the current patch against it.

I would prefer to postpone: hashing, printing

The current hashing and printing setup is complete and total crap, and needs to be removed ASAP. It renders number fields completely useless for any nontrivial applications that involve prime ideals.

Also, I'm personally not completely convinced about the best way to print

I saw that. I think the best solution is exactly what I implemented in the attached patch. Hash based on gens (trivial, as a hash should be). Print in reduced form only in small trivial cases (by default), but allow the user to easily up the cutoff if they want, for some reason.

comment:7 in reply to: ↑ 6 ; follow-up: Changed 7 years ago by jdemeyer

Replying to was:

I saw that. I think the best solution is exactly what I implemented in the attached patch. Hash based on gens (trivial, as a hash should be).

Why not hash based on the HNF representation, as I propsed in #9666? I think this is more canonical than gens() and it is the native PARI format.

comment:8 Changed 7 years ago by jdemeyer

  • Cc jdemeyer added

comment:9 in reply to: ↑ 7 Changed 7 years ago by was

Replying to jdemeyer:

Replying to was:

I saw that. I think the best solution is exactly what I implemented in the attached patch. Hash based on gens (trivial, as a hash should be).

Why not hash based on the HNF representation, as I propsed in #9666? I think this is more canonical than gens() and it is the native PARI format.

CONS: I think number fields will frequently be relative extensions, and we'll also consider ideals both in the maximal order and in suborders. Pari will likely have almost nothing to do with our general relative extensions (it's only currently used for relative extensions as a miserable crutch), and HNF doesn't apply for ideals in orders.

PROS: When it works, hashing based on the HNF has the property that if I==J then hash(I) == hash(J). That's a very good property to have. With hashing of gens that fails.

Thus taken together, I'm OK with your proposal with the caveat that at some future time it has to be revisited for *relative* extensions.

Changed 7 years ago by was

apply only this patch (which also addresses the referees issue with hash)

comment:10 Changed 7 years ago by was

OK, new patch up that changes hash. It passes all doctests on sage.math.

comment:11 follow-up: Changed 7 years ago by jdemeyer

The patch introduces an inconsistency:

sage: K.<a> = NumberField(x^3-7)
sage: K.ideal(12*a + 5).factor()
(Fractional ideal (101, a - 8)) * (Fractional ideal (11, a + 5))^2
sage: K.<b> = NumberField(x^3-10001)
sage: L.ideal(b+1).factor()
(Fractional ideal (b + 1, 1667)) * (Fractional ideal (b + 1, 2)) * (Fractional ideal (b + 1, 3))

Note how the integer is printed first in the first case but last in the second case (and personally I find it clearer when the integer is put first). Maybe the sorting and uniqueing should be done in the NumberFieldIdeal? constructor instead of when the ideal is printed?

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by was

Note how the integer is printed first in the first case but last in the second case (and personally I find it clearer when the integer is put first). Maybe the sorting and uniqueing should be done in the NumberFieldIdeal? constructor instead of when the ideal is printed?

Would that make any difference? The difference above is that in one case the number field has a very small discriminant (-1323), and in the other it doesn't (-2700540027). When the discriminant is small, then reduced generators are used for printing. A solution could be to apply the sorting and "uniquing" in both cases before printing -- right now it is only applied in the case of large discriminant.

comment:13 in reply to: ↑ 12 Changed 7 years ago by was

Hi,

I retract my comment. The issue may be that sorting of elements of number fields is now useless. Observe:

sage: L.<b> = NumberField(x^3-10001)
sage: b+1 < L(1667)
False
sage: L(1667) < b + 1
False

Thus it doesn't matter *what* you do with sorting and uniquing the gens before or after -- there's no sensible ordering that will come out of this, unless elements of number fields get a total (non-algebraic) ordering. I thought they had one.

Oh, now I remember -- there is a *major bug* in the way elements of number fields are ordered. You can see this by looking at the code (I think Joel Mohler) wrote in number_field_element.pyx. I fixed this a few weeks ago as part of the patch bomb #9541.

So my advice is to not worry about sorting issues as part of *this* patch, but keep in mind that it is has to be fixed later. I've opened ticket #9752 to fix this.

comment:14 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-4.5.3 to sage-4.6

Always using gens() for printing is also silly, because for larger degrees you can get something like:

sage: x=polygen(QQ); K.<a> = NumberField(x^8+x-1);
sage: J1 = K.ideal(a+1); J2 = K.ideal(a+2); J = J1.intersection(J2)
sage: J
Fractional ideal (a^2 + 249, -a^7 + 125, a + 2, a^3 + 8, a^4 + 237, -a^7 - a^6 + 189, a^7 + a^6 + a^5 + 96, 253)

In my opinion, the best way would be to use idealtwoelt() for large discriminants instead of simply printing all generators (or alternatively: reduce the generators using idealtwoelt() in __init__).

comment:15 Changed 7 years ago by was

On Tue, Aug 17, 2010 at 5:03 PM, Chan-Ho Kim <chanho.math> wrote:
> Dear William,
> I think that there is a bug on trac 9400 patch.
> My current SAGE is (SAGE 4.5.2 + trac 9400 patch only) in VM.
> When I use `maximize_at_prime,'
>
> K.<a> = NumberField(x^6 + 9*x^5 - 8410*x^4 - 88580*x^3 + 18705368*x^2 +
> 99820416*x - 12230355456, maximize_at_primes=[3]) ; K.primes_above(3)
> this decomposition in K works as you mentioned.
>
> However, in this ``small'' number field
>
> F.<a> = NumberField(x^3 - x^2 - 24*x + 32, maximize_at_primes=[3]) ;
> F.primes_above(3)
> the low precision error occurs if I add `maximize_at_primes=[3].'

That's not a bug in maximize_at_primes or finding the primes above 3.   But it *is* an issue with *printing* the ideals out that it finds over 3.   Evidently, when printing is_principal is called on each ideal currently, and this leads to a problem.  This is not surprising, given that deciding whether or not an ideal is principal requires knowing the class group in general, and the equation order of F that you define above is not only deficient at 3.  You need to also maximize at 2.   See:

sage: F.<a> = NumberField(x^3 - x^2 - 24*x + 32, maximize_at_primes=[2,3]) 
sage: F.primes_above(3)
[Fractional ideal (-1/2*a^2 - 3/2*a + 5), Fractional ideal (-1/2*a^2 + 5/2*a - 1)]

So in short, this is not a bug.  If you try to compute with number fields and pass in the maximize_at_primes option, certain things can't possibly work.

That said, I'm not a big fan of how ideals print.  Maybe Jereon's suggestion -- just *always* print with the PARI 2-element representation -- is the way to go.  That might get around this problem. 


> BTW, I also have one more question:
> Can I add `maximize_at_prime=[p]' in `hecke_eigenvalue_field()'?

You'll have to dive in and start hacking at the source code of Sage to do that....

 -- William

comment:16 Changed 7 years ago by jdemeyer

I am not familiar with _pari_ and _pari_init_, but why does NumberField? need _pari_init_? Can't we add instead a _pari_ method which returns pari_nf()?

comment:17 Changed 7 years ago by jdemeyer

Rebasing to #9343 will be easier if we seperate the "maximize_at_primes part" from the "printing and hashing of ideals" part. So I will cut this patch in two pieces.

Changed 7 years ago by jdemeyer

Patch for the "maximize at primes" part, rebased to sage-4.6.prealpha1 (see #9343)

comment:18 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:19 Changed 7 years ago by jdemeyer

I attached a big reviewer patch (to be applied on top of 9400_maximize_at_primes.patch) changing:

  • the PARI functions nfbasis() and nfinit(): document and fix implementation.
  • change pari_nf() to always use integral_basis() (this means that all the maximize_at_primes code can be moved out of pari_nf()).
  • rename _compute_integral_basis to _pari_integral_basis and don't convert from PARI to Sage.
  • make the code for CyclotomicField? more analogous to NumberField_generic (such that only _pari_integral_basis needs to be specialized, not integral_basis().

Since the purpose of _pari_init_() is very unclear to me, I'm not sure what to do with that.

Changed 7 years ago by jdemeyer

Apply on top of 9400_maximize_at_primes.patc

comment:20 Changed 7 years ago by jdemeyer

  • Authors set to William Stein, Jeroen Demeyer
  • Keywords PARI number field added
  • Owner changed from davidloeffler to jdemeyer

comment:21 Changed 7 years ago by cremona

Since this ismarked "needs review" could the authors clarify which patches are up for review? I assume it is

9400_maximize_at_primes.patch 
Patch for the "maximize at primes" part, rebased to sage-4.6.prealpha1 (see #9343)

and

9400_jd_review.patch 
Apply on top of 9400_maximize_at_primes.patch

and not the first one.

Secondly, since these patches have been merged into 4.6.prealpha3 which I have successfully built and tested, I reckon that the only (!) remaining task as a reviewer is to look at the code in the patch, with the additional explanations on the ticket, and approve (or otherwise, maybe) of it?

I will try to do this before I go away on Friday for a week. No promises...

comment:22 follow-up: Changed 7 years ago by cremona

  • Reviewers set to Jeroen Demeyer, William Stein, John Cremona
  • Status changed from needs_review to needs_work

Looking at the 2nd and 3rd patches (separately) it looks very good to me. For the benefit of others reading this, the essence of these patches (apart from some ReSTification) is to expose some additional functionality from the pari library to Sage, so that some computations can be mande very much faster (a *lot* faster!).

I spotted a few minor issues in docstrings (numbers refer to the ones I see in the third patch):

6451: second 'it' --> 'the'

6466: should have a preceding #, or replace ":" by "::" and insert a blank line after and change the preceding "TESTS::" to "TESTS:"

6592: change "TESTS::" to "TESTS:"

and also when I rebuilt the docs after "sage -ba" (using 4.6.prealpha3) I got these ReST warnings:

docstring of sage.libs.pari.gen:136: (WARNING/2) Literal block expected; none found.
docstring of sage.libs.pari.gen.gen.nfbasis:8: (WARNING/2) Definition list ends without a blank line; unexpected unindent.
docstring of sage.libs.pari.gen.gen.nfinit:19: (WARNING/2) Literal block expected; none found.

Modulo these, a positive review is on offer. Hence "needs work", but it is only trivial work.

comment:23 Changed 7 years ago by jdemeyer

Thanks John, I will take care of these issues when I have time.

comment:24 Changed 7 years ago by jdemeyer

  • Description modified (diff)

Changed 7 years ago by jdemeyer

Apply on top of previous 2 patches, small documentation fixes

comment:25 Changed 7 years ago by jdemeyer

  • Reviewers changed from Jeroen Demeyer, William Stein, John Cremona to Jeroen Demeyer, John Cremona
  • Status changed from needs_work to needs_review

Changed 7 years ago by jdemeyer

All 3 patches combined (apply only this patch)

comment:26 Changed 7 years ago by jdemeyer

  • Description modified (diff)

comment:27 in reply to: ↑ 22 Changed 7 years ago by jdemeyer

I did all the changes requested by the reviewer.

Replying to cremona:

docstring of sage.libs.pari.gen:136: (WARNING/2) Literal block expected; none found.

This belongs to #9636 and is fixed there. The other warnings are fixed here.

comment:28 follow-up: Changed 7 years ago by was

  • Status changed from needs_review to needs_work

Hi,

I tried to apply my patch to 4.5.2.rc0 and it works fine:

adding trac_9400.patch to series file
applying trac_9400.patch
now at: trac_9400.patch

I tried to apply your patch (9400_combined.patch) and there are a massive number of rejects:

adding 9400_combined.patch to series file
applying 9400_combined.patch
patching file sage/libs/pari/gen.pyx
Hunk #1 succeeded at 6408 with fuzz 2 (offset -32 lines).
Hunk #4 FAILED at 6964
Hunk #5 FAILED at 6991
2 out of 7 hunks FAILED -- saving rejects to file sage/libs/pari/gen.pyx.rej
patching file sage/rings/number_field/number_field.py
Hunk #13 FAILED at 2870
Hunk #16 FAILED at 3727
2 out of 25 hunks FAILED -- saving rejects to file sage/rings/number_field/number_field.py.rej
patching file sage/rings/number_field/number_field_ideal_rel.py
Hunk #2 FAILED at 592
1 out of 2 hunks FAILED -- saving rejects to file sage/rings/number_field/number_field_ideal_rel.py.rej
patching file sage/rings/polynomial/polynomial_quotient_ring.py
Hunk #1 FAILED at 688
Hunk #2 FAILED at 1068
2 out of 2 hunks FAILED -- saving rejects to file sage/rings/polynomial/polynomial_quotient_ring.py.rej
patching file sage/rings/residue_field.pyx
Hunk #17 succeeded at 427 with fuzz 2 (offset 0 lines).
Hunk #18 succeeded at 444 with fuzz 2 (offset 0 lines).
Hunk #19 FAILED at 463
Hunk #26 succeeded at 572 with fuzz 1 (offset -1 lines).
Hunk #27 FAILED at 589
2 out of 48 hunks FAILED -- saving rejects to file sage/rings/residue_field.pyx.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh 9400_combined.patch

comment:29 in reply to: ↑ 28 Changed 7 years ago by jdemeyer

  • Description modified (diff)
  • Status changed from needs_work to needs_review

Replying to was:

I tried to apply your patch (9400_combined.patch) and there are a massive number of rejects:

It is meant to be applied after #9343, then it works fine.

comment:30 follow-ups: Changed 7 years ago by mpatel

John, do Jeroen's most recent changes look good to you?

comment:31 in reply to: ↑ 30 Changed 7 years ago by cremona

Replying to mpatel:

John, do Jeroen's most recent changes look good to you?

Sorry for delay -- Jeroen has nudged me on this and I'll look at it as soon as I can, but I'm at a conference this week...

comment:32 in reply to: ↑ 30 ; follow-up: Changed 7 years ago by cremona

Replying to mpatel:

John, do Jeroen's most recent changes look good to you?

The new combined patch does look good. It applies smoothly to 4.6.alpha0, and the docs (re)build with no warnings. I am currently doing a full test just to make sure. Will report back shortly.

comment:33 in reply to: ↑ 32 Changed 7 years ago by cremona

  • Status changed from needs_review to positive_review

Replying to cremona:

Replying to mpatel:

John, do Jeroen's most recent changes look good to you?

The new combined patch does look good. It applies smoothly to 4.6.alpha0, and the docs (re)build with no warnings. I am currently doing a full test just to make sure. Will report back shortly.

All (long) tests pass -- positive review.

comment:34 follow-up: Changed 7 years ago by mpatel

  • Merged in set to sage-4.6.alpha1
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:35 in reply to: ↑ 34 Changed 7 years ago by jdemeyer

Replying to mpatel:

Note that I mentioned in this ticket (and on sage-devel) that I do not understand _pari_init_(). I don't know if the reviewers do, so I'm a little bit worried about this.

Note: See TracTickets for help on using tickets.