#10659: Improve performance of matrix group morphisms
----------------------------+-----------------------------------------------
Reporter: SimonKing | Owner: joyner
Type: defect | Status: new
Priority: major | Milestone: sage-4.6.2
Component: group theory | Keywords: matrix group morphism
Author: Simon King | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
----------------------------+-----------------------------------------------
I met the following example, that took unnecessarily long:
{{{
sage: O = WeylGroup(['D',6])
sage: r = prod(O.gens())
sage: r_ = r^-1
sage: f = O.hom([r*x*r_ for x in O.gens()]) # long
sage: Im = [f(x) for x in O.gens()] # very long
}}}
I found the following oddities in
`sage.groups.matrix_gps.matrix_group_morphism`:
1. There was a string `self._gap_hom_string` that, when evaluated in Gap,
had the side-effect of defining (or, in bad cases, overriding!) something
called `Phi` - a very common name.
2. The string `self._gap_hom_string` was evaluated whenever `self` was
called. That was very bad waste of time, because it checks over and over
again whether the input data actually yield a group homomorphism. That
takes a very long time.
3. There was a `__call__` method, rather than a `_call_` and a
`pushforward` method.
4. `image` and `kernel` return a Gap-readable ''string'', rather than a
subgroup or a group element!
With my patch, it is only tested ''once'' whether or not the input data
provide a group homomorphism, namely in the `__init__` method. Moreover,
`image` is renamed to `pushforward`, and returns a subgroup (and so does
`kernel`).
'''__Examples__'''
The example above still takes a while, since gap needs long to check
sanity. However, the execution time considerably dropped.
Here, the last line used to return a string:
{{{
sage: F = GF(7); MS = MatrixSpace(F,2,2)
sage: F.multiplicative_generator()
3
sage: G = MatrixGroup([MS([3,0,0,1])])
sage: a = G.gens()[0]^2
sage: phi = G.hom([a])
sage: phi.kernel()
Matrix group over Finite Field of size 7 with 1 generators:
[[[6, 0], [0, 1]]]
}}}
Here, `image` used to return a string. The last line didn't work at all.
{{{
sage: F = GF(7); MS = MatrixSpace(F,2,2)
sage: F.multiplicative_generator()
3
sage: G = MatrixGroup([MS([3,0,0,1])])
sage: a = G.gens()[0]^2
sage: phi = G.hom([a])
sage: phi.image(G.gens()[0])
[2 0]
[0 1]
sage: H = MatrixGroup([MS(a.list())])
sage: H
Matrix group over Finite Field of size 7 with 1 generators:
[[[2, 0], [0, 1]]]
sage: phi(H)
Matrix group over Finite Field of size 7 with 1 generators:
[[[4, 0], [0, 1]]]
}}}
I marked the ticket as "defect", since returning a string rather than an
element is nasty.
The patch depends on #10496, that cleans up the generic code for maps.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10659>
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.
