#13958: number of generators of number field ideal blows up under multiplication
-----------------------------------------------------------+----------------
Reporter: mstreng | Owner:
davidloeffler
Type: defect | Status:
new
Priority: major | Milestone:
sage-5.7
Component: number fields | Resolution:
Keywords: number field ideal multiplication power | Work issues:
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: | Stopgaps:
-----------------------------------------------------------+----------------
Comment (by mderickx):
I did some profiling and from this it seems that gens_two is faster then
pari_hnf.
See: http://pastebin.com/aejaKMds for timings with principal ideals and
http://pastebin.com/HU2DExLH for timings with ideals generated by multiple
random elements (where the amount or random elements changes).
The documentation says that gens_two runs in randomized polynomial time
(but does not say anything about the degree of the polynomial).
I think that at least in __mul__ it would make a lot of sense to call
gens_two on both ideals before multiplication (at least if I.ngens()>2).
Not doing this causes I.ngens() to explode as mentioned above. And my
timing suggest that calling gens_two before multiplication and then
multiplying is cheaper then first multiplying and then doing something
like pari_hnf or gens_two . The reason is that as soon as your ideal is
given by n!^2 generators (where n is the degree of the function field)
then any operation to reduce the ammount of generators is going to be very
costly, simply because the ammount of input generators is so big.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/13958#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
