#11538: Improve efficiency of fgp_module over integers
---------------------------+------------------------------------------------
Reporter: nbruin | Owner: tbd
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.7.1
Component: performance | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author:
Merged: | Dependencies:
---------------------------+------------------------------------------------
The functionality of fgp_module is excellent, but its performance for FG
modules over integers is not very good. Given how (finite) abelian groups
could really be worked with in this setting, it's probably worthwhile
specializing this case, which allows it to be vastly more efficient. Just
as an example, consider the following code:
{{{
Z3=ZZ^3
F=Z3/Z3.span([])
G=F/F.submodule([12*F.0,4*F.1+8*F.2,16*F.2])
H=G/G.submodule([2*g for g in G.gens()])
phi=G.hom([H(g) for g in G.gens()])
def faster_hom(phi):
dom=phi.domain()
codom=phi.codomain()
M=matrix([vector(phi(g)) for g in G.gens()])
inv=codom.invariants()
r=len(inv)
def fast_hom(v):
w=vector(v)*M
return codom([w[i] % inv[i] for i in xrange(r)])
return fast_hom
faster_phi=faster_hom(phi)
timeit("phi(G.random_element())")
timeit("faster_phi(G.random_element())")
}}}
with results
{{{
125 loops, best of 3: 2.03 ms per loop
625 loops, best of 3: 907 µs per loop
}}}
That's already a factor of 2. And that's only replacing it with python
code! (though it is assuming the codomain is in "optimized" form, but that
is clearly what one should ensure)
A little profiling shows that calling "phi" incurs 5 calls to
{{{sage.matrix.matrix0.Matrix.linear_combination_of_rows}}}.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11538>
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.
