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)
Change History (20)
Changed 12 years ago by
comment:1 Changed 12 years ago by
- 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)
comment:2 Changed 12 years ago by
- Cc craigcitro added
Changed 12 years ago by
comment:3 follow-up: ↓ 4 Changed 12 years ago by
- 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
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) forsage: 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
- 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
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
- 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
comment:8 Changed 12 years ago by
- 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
comment:9 Changed 12 years ago by
- 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
- 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
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
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
comment:13 Changed 12 years ago by
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
REVIEW:
+1 to the numerical noise doctest fixes
comment:15 Changed 12 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 3.0.4.alpha2
Review report by John Cremona:
In detail:
and
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).