Opened 12 years ago

Closed 12 years ago

#3533 closed enhancement (fixed)

[with patch, with positive review] better number fields (mostly cyclotomic)

Reported by: fwclarke Owned by: was
Priority: major Milestone: sage-3.0.4
Component: number theory Keywords:
Cc: craigcitro, mhansen Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

This attached patch makes several changes to sage/rings/number_field/number_field.py and sage/rings/number_field/morphism.py that are mainly concerned with improving performance for cyclotomic fields, but also tidy up various other things. The main changes are summarised below.

There is a serious bug in roots_of_unity when applied to relative number fields:

sage: K.<a> = NumberField([x^2 + 3, x^2 + 1])
sage: K.roots_of_unity()
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

But

sage: K.absolute_field('b').roots_of_unity()
[1/8*b^3 + 1/4*b^2 + 3/4*b + 1,
 1/8*b^3 + 5/4*b + 1/2,
...

so it is clear how to deal with the problem.

In addition, the roots_of_unity and number_of_roots_of_unity methods can rather obviously be made much faster for cyclotomic fields.

Similarly, I've written a method for listing the embeddings of a cyclotomic field in a number field which runs much more quickly than at present.

For the general case of finding embeddings of number fields, at the moment SAGE asks PARI to look for roots when a simple degree check indicates that there are none. It is, of course, very easy to avoid this wasted time.

A method for complex embeddings of cyclotomic fields already exists, but it is inadequate in two ways. First, it handles the default precision in a different way from the method for generic complex embeddings. Second, it fails to cache the result. These faults have been corrected, and the change in respect of precision also applied to complex_embedding (in the singular).

There is also a slight problem with the embeddings function (used by the generic complex_embeddings and real_embeddings). It caches its output, but the first time it is called it returns something different from what has been cached (a list rather than a Sequence). This has been changed for both the generic field and the relative field methods. In addition the code now avoids the printing of empty lists of field embeddings on three lines.

I've added a method for real embeddings of cyclotomic fields. Nobody who knows what they're doing would use this function, but it might as well be efficient.

Many other functions can be speeded up for cyclotomic fields, because of the vast amount of theory about these fields. As well as the above, I've implemented signature, discriminant and is_isomorphic for cyclotomic fields. Probably more could be done. Galois groups are an obvious example, but that had better wait until ticket #133 is sorted out.

Some of the existing doctests have been moved when they apply to cyclotomic fields. Others have been added.

Attachments (5)

sage-3533.patch (27.7 KB) - added by fwclarke 12 years ago.
sage.3533a.patch (3.1 KB) - added by fwclarke 12 years ago.
sage.3533b.patch (3.4 KB) - added by fwclarke 12 years ago.
sage.3533c.patch (2.5 KB) - added by cremona 12 years ago.
trac_3533_doctest_fixes.patch (2.4 KB) - added by mabshoff 12 years ago.
cleaned up version of the previous diff.

Download all attachments as: .zip

Change History (20)

Changed 12 years ago by fwclarke

comment:1 Changed 12 years ago by cremona

  • Summary changed from [with patch, needs review] better number fields (mostly cyclotomic) to [with patch, with review, needs a little work] better number fields (mostly cyclotomic)

Review report by John Cremona:

  1. The aims of the patch all look good to me.
  2. Reading the patch diffs it looked ok. It would be better if someone else took a look too.
  3. The patch applied cleanly to 3.0.4.alpha0
  4. I tested all the number_fields directory but found the following failures:
	sage -t  sage-3.0.4.alpha0/devel/sage-3533/sage/rings/number_field//number_field_element.pyx
	sage -t  sage-3.0.4.alpha0/devel/sage-3533/sage/rings/number_field//number_field.py

In detail:

File "/home/jec/sage-current/tmp/number_field_element.py", line 523:
    sage: abs(z)
Expected:
    1.00000000000000
Got:
    1.0
**********************************************************************
File "/home/jec/sage-current/tmp/number_field_element.py", line 525:
    sage: abs(z^2 + 17*z - 3)
Expected:
    16.0604426799931
Got:
    16.06044268

and

File "/home/jec/sage-current/tmp/number_field.py", line 5552:
    sage: C.complex_embeddings()
Expected:
    [
    Ring morphism:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Complex Double Field
      Defn: zeta4 |--> 2.77555756156e-17 - 1.0*I,
    Ring morphism:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Complex Double Field
      Defn: zeta4 |--> -1.83690953073e-16 + 1.0*I
    ]
Got:
    [
    Ring morphism:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Complex Double Field
      Defn: zeta4 |--> 2.77555756156e-17 - 1.0*I,
    Ring morphism:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Complex Double Field
      Defn: zeta4 |--> -1.83697019872e-16 + 1.0*I
    ]

These do not look serious, they are to do with outputting floating point numbers, but there must be a way to get the tests to pass ("#random low order bits" if desperate).

comment:2 Changed 12 years ago by craigcitro

  • Cc craigcitro added

Changed 12 years ago by fwclarke

comment:3 follow-up: Changed 12 years ago by fwclarke

  • Summary changed from [with patch, with review, needs a little work] better number fields (mostly cyclotomic) to [with extra patch, needs re-reviewing] better number fields (mostly cyclotomic)

The varying results for abs derive from the changed default precision used for cyclotomic fields (so that they're compatible with generic number fields). Using the generic methods, the same answers are obtained (with or without the patch) for

sage: z = NumberField(cyclotomic_polynomial(7), 'a').gen()
sage: abs(z)
1.0
sage: (z^2 + 17*z - 3).abs(i=5)
16.06044268

(i=5 is necessary because the ordering of the embeddings is different for the two ways of constructing the same field.)

I have therefore made the appropriate changes to the doctest in number_field_element.pyx in a new patch.

The second doctest failure is both more trivial and more worrying. I don't actually understand the following behaviour:

sage: z = exp(I*pi/2); z
I
sage: [CDF(I), CDF(z)]
[1.0*I, 6.12303176911e-17 + 1.0*I]

But anyway, the issue here is nothing to do with number fields. The easy way out is to change the example to make it less trivial, and this is done in the new patch.

Haven't tried it with 3.0.4.alpha0, but with 3.0.3 and both patches all tests pass.

comment:4 in reply to: ↑ 3 Changed 12 years ago by cremona

Replying to fwclarke:

The varying results for abs derive from the changed default precision used for cyclotomic fields (so that they're compatible with generic number fields). Using the generic methods, the same answers are obtained (with or without the patch) for

sage: z = NumberField(cyclotomic_polynomial(7), 'a').gen()
sage: abs(z)
1.0
sage: (z^2 + 17*z - 3).abs(i=5)
16.06044268

(i=5 is necessary because the ordering of the embeddings is different for the two ways of constructing the same field.)

I have therefore made the appropriate changes to the doctest in number_field_element.pyx in a new patch.

The second doctest failure is both more trivial and more worrying. I don't actually understand the following behaviour:

sage: z = exp(I*pi/2); z
I
sage: [CDF(I), CDF(z)]
[1.0*I, 6.12303176911e-17 + 1.0*I]

Does this explain it?

sage: z = exp(I*pi/2); z
I
sage: type(z)           
<class 'sage.calculus.calculus.SymbolicComposition'>
sage: type(I)           
<class 'sage.functions.constants.I_class'>

So z displays as I but it is not I. Hmmm

sage: z is I
False
sage: z == I
I == I
sage: bool(z == I)
True

But anyway, the issue here is nothing to do with number fields. The easy way out is to change the example to make it less trivial, and this is done in the new patch.

Haven't tried it with 3.0.4.alpha0, but with 3.0.3 and both patches all tests pass.

I'll check out the second patch now.

comment:5 Changed 12 years ago by cremona

  • Summary changed from [with extra patch, needs re-reviewing] better number fields (mostly cyclotomic) to [with extra patch, non-negative review] better number fields (mostly cyclotomic)

Nearly there but not quite:

sage -t  sage-3.0.4.alpha0/devel/sage-3533/sage/rings/number_field//number_field.py**********************************************************************
File "/home/jec/sage-current/tmp/number_field.py", line 5551:
    sage: CyclotomicField(5).complex_embeddings()
Expected:
    [
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> 0.309016994375 - 0.951056516295*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> -0.809016994375 - 0.587785252292*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> -0.809016994375 + 0.587785252292*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> 0.309016994375 + 0.951056516295*I
    ]
Got:
    [
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> 0.309016994375 + 0.951056516295*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> -0.809016994375 + 0.587785252292*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> -0.809016994375 - 0.587785252292*I,
    Ring morphism:
      From: Cyclotomic Field of order 5 and degree 4
      To:   Complex Double Field
      Defn: zeta5 |--> 0.309016994375 - 0.951056516295*I
    ]

**********************************************************************
1 items had failures:
   1 of   2 in __main__.example_165
***Test Failed*** 1 failures.

The only difference is in the order of the 4 elements in the list. I think you need to apply sort() to the list returned by complex_embeddings() to ensure consistency.

comment:6 Changed 12 years ago by robertwb

I would like to note that there have been significant changes to the number field files in the coercion branch. I think most of the changes in this ticket are orthogonal to the coercion ones, but this is something we should be aware of and I'm not so sure how clean the merge will be.

comment:7 Changed 12 years ago by fwclarke

  • Summary changed from [with extra patch, non-negative review] better number fields (mostly cyclotomic) to [with another patch, needs review] better number fields (mostly cyclotomic)

I think the order of embeddings is reasonable: in terms of the powers of a primitive n-th root. But what this failure has exposed is that CDF.zeta(n) uses the generic method in ring.pyx. This certainly needs changing. At the moment we have

sage: version()
'SAGE Version 3.0.3, Release Date: 2008-06-17'
sage: timeit('CDF.zeta(117)')
5 loops, best of 3: 42.3 ms per loop
sage: timeit('ComplexField(64).zeta(117)')
625 loops, best of 3: 77 µs per loop

CDF is supposed to be faster than ComplexField!

I've written a patch to include a new zeta method for CDF and modify two doctests so that they comply. All tests pass with 3.0.3.

After the patch:

sage: timeit('CDF.zeta(117)')
625 loops, best of 3: 22.9 µs per loop

I don't think there are likely to be any coercion problems, since all the code in these patches is just a minor adaptation of code used elsewhere.

Changed 12 years ago by fwclarke

comment:8 Changed 12 years ago by cremona

  • Summary changed from [with another patch, needs review] better number fields (mostly cyclotomic) to [with yet another patch, with positive review] better number fields (mostly cyclotomic)

The patches (all three in succession) apply cleanly to 3.0.4.alpha0, and all tests (in sage/rings/number_field) pass.

To be really picky, the new CDF.zeta(n) returns None if n<=0. This could conceivably trip someone up -- and I haven't checked to see what the other .zeta() functions do for arguments which are not positive. I think one might argue for CDF.zeta(-n)=CDF.zeta(n) and CDF.zeta(0)=1, but it might be better to throw a ValueError if n<1. In the 4th patch sage.3533c.patch I added tests to this effect and corresponding doctests. I also deleted some weird stuff at the end of complex_double.pyx which I assume is garbage.

Changed 12 years ago by cremona

comment:9 Changed 12 years ago by robertwb

  • Cc mhansen added

My concerns about coercion were not that things would become incompatible, it was just that there have been so many changes to the number field file (especially cyclotomic fields) that the resulting merge could be painful. It would just be a question of timing, the code (what I've looked at) looks good. Mike Hansen has volunteered to do the merge with 3.0.4, so perhaps he should comment on whether or not it would cause any problems (if not, I don't want to hold it up).

comment:10 Changed 12 years ago by mabshoff

  • Summary changed from [with yet another patch, with positive review] better number fields (mostly cyclotomic) to [with patch, with positive review] better number fields (mostly cyclotomic)

Mike said in IRC minutes ago:

mhansen: mabshoff: I looked at #3533 and it's good to go.  I can handle the merge issues.

so I am merging those patches ASAP.

Cheers,

Michael

comment:11 Changed 12 years ago by mabshoff

I am seeing some trivial to fix numerical noise doctest failures:

mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2$ sage -t -long devel/sage/sage/modular/dirichlet.py # 5 doctests failed
sage -t -long devel/sage/sage/modular/dirichlet.py          **********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/dirichlet.py", line 674:
    sage: e.gauss_sum_numerical()
Expected:
    5.55111512312578e-16 + 1.73205080756888*I
Got:
    9.43689570931e-16 + 1.73205080757*I
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/dirichlet.py", line 676:
    sage: abs(e.gauss_sum_numerical())
Expected:
    1.73205080756888
Got:
    1.73205080757
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/dirichlet.py", line 680:
    sage: e.gauss_sum_numerical(a=2)
Expected:
    -1.11022302462516e-15 - 1.73205080756888*I
Got:
    -1.33226762955e-15 - 1.73205080757*I
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/dirichlet.py", line 686:
    sage: e.gauss_sum_numerical()
Expected:
    -3.07497205899524 + 1.88269669261902*I
Got:
    -3.074972059 + 1.88269669262*I
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/dirichlet.py", line 688:
    sage: abs(e.gauss_sum_numerical())
Expected:
    3.60555127546399
Got:
    3.60555127546
**********************************************************************
1 items had failures:
   5 of  13 in __main__.example_23
***Test Failed*** 5 failures.
For whitespace errors, see the file /scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/.doctest_dirichlet.py
	 [3.4 s]
exit code: 1024
 
----------------------------------------------------------------------
The following tests failed:


	sage -t -long devel/sage/sage/modular/dirichlet.py
Total time for all tests: 3.4 seconds
mabshoff@sage:/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2$ sage -t -long devel/sage/sage/matrix/matrix_cyclo_dense.pyx # 3 doctests failed
sage -t -long devel/sage/sage/matrix/matrix_cyclo_dense.pyx 
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/matrix_cyclo_dense.py", line 664:
    sage: (A[1,0]).abs()
Expected:
    12.9975436637560
Got:
    12.9975436638
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/matrix_cyclo_dense.py", line 697:
    sage: A.height()
Expected:
    12.9975436637560
Got:
    12.9975436638
**********************************************************************
File "/scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/matrix_cyclo_dense.py", line 699:
    sage: (A[1,0]).abs()
Expected:
    12.9975436637560
Got:
    12.9975436638
**********************************************************************
2 items had failures:
   1 of   5 in __main__.example_20
   2 of   5 in __main__.example_21
***Test Failed*** 3 failures.
For whitespace errors, see the file /scratch/mabshoff/release-cycle/sage-3.0.4.alpha2/tmp/.doctest_matrix_cyclo_dense.py
	 [9.8 s]
exit code: 1024

Patch coming up.

Cheers,

Michael

comment:12 Changed 12 years ago by mabshoff

For the record (and so that I do not forget): I already have applied

  • sage-3533.patch
  • sage.3533a.patch
  • sage.3533b.patch
  • sage.3533c.patch

to my Sage 3.0.4.alpha2 repo and am waiting for #3557 to be fixed and a review before applying the doctest fix patch.

Cheers,

Michael

Changed 12 years ago by mabshoff

cleaned up version of the previous diff.

comment:13 Changed 12 years ago by mabshoff

Note that in the last doctest fix patch I am removing

e.gauss_sum_numerical() 

from dirichlet.py since it is numerically unstable and would require an ellipsis at the start of a line which is not allowed. We still test the absolute, so I think we are covered.

Cheers,

Michael

comment:14 Changed 12 years ago by was

REVIEW:

+1 to the numerical noise doctest fixes

comment:15 Changed 12 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 3.0.4.alpha2

Note: See TracTickets for help on using tickets.