#1134: optimize creating elements of orders and number fields by coercing in
lists
---------------------------------+-----------------------------
Reporter: was | Owner: davidloeffler
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-6.3
Component: number fields | Resolution:
Keywords: | Merged in:
Authors: Mike Hansen | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
Dependencies: | Stopgaps:
---------------------------------+-----------------------------
Changes (by vdelecroix):
* status: needs_review => needs_info
Comment:
With some careful merge I was able to make the patch applied and work on
sage-6.3.beta3. But, the map `list_to_quadratic_field_element` is
completely useless as there is no gain at all. Moreover, it is one more
map added to the list of conversions. So I would suggest to not add it
with that ticket.
One interesting optimization in the ticket is the `check` parameter added
to the `_element_constructor_`. Do you agree if I provide a branch that
contains only that?
Also, as it was said in comment:9 most of the time in the construction is
spent in checking. So it would be worth to optimize it. The longest part
comes from decomposing a vector on a given basis as the timings below
show.
The construction takes roughly 600 micro seconds
{{{
sage: K = NumberField(x^2-x-1, 't')
sage: Z_F = K.maximal_order()
sage: x = K([5,1])
sage: %timeit Z_F(x)
1000 loops, best of 3: 674 µs per loop
}}}
But most of the time is spent in checking that some vector belong to some
submodule
{{{
sage: %timeit K.vector_space() # <--- this is very quick
1000000 loops, best of 3: 431 ns per loop
sage: embedding = K.vector_space()[2]
sage: embedding
Isomorphism map:
From: Number Field in t with defining polynomial x^2 - x - 1
To: Vector space of dimension 2 over Rational Field
sage: %timeit embedding(x) # <--- this is quick
10000 loops, best of 3: 49.8 µs per loop
sage: v = phi(x)
sage: %timeit v in Z_F._module_rep # <--- this is damn slow
1000 loops, best of 3: 608 µs per loop
}}}
And in `__contains__` of `FreeModule`, the mess comes from calling
`coordinates` that decompose the vector on the basis of the module:
{{{
sage: V = Z_F._module_rep
sage: %timeit V.coordinates(v)
1000 loops, best of 3: 612 µs per loop
}}}
--
Ticket URL: <http://trac.sagemath.org/ticket/1134#comment:14>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
