#15280: Extensions of PALP normal form, affine normal form and isomorphisms
-------------------------------------+-------------------------------------
Reporter: jkeitel | Owner:
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-6.3
Component: geometry | Resolution:
Keywords: toric | Merged in:
Authors: Jan Keitel | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
u/jkeitel/normal_form_codimension | 4e8dace1658e2565a2f391e1528083d0c277235c
Dependencies: #13525 | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by jkeitel):
Here are some timings, showing that the effect of computing the
permutations can in fact be largely neglected:
{{{
sage: o = lattice_polytope.cross_polytope(2)
sage: %timeit o._palp_native_normal_form(permutation=False)
10 loops, best of 3: 43.8 ms per loop
sage: %timeit o._palp_native_normal_form(permutation=True)
10 loops, best of 3: 43.9 ms per loop
sage: %timeit o._palp_modified_normal_form(permutation=False)
10 loops, best of 3: 36 ms per loop
sage: %timeit o._palp_modified_normal_form(permutation=True)
10 loops, best of 3: 36.1 ms per loop
sage: %timeit o._normal_form_full_dimensional(permutation=False)
10 loops, best of 3: 8.91 ms per loop
sage: %timeit o._normal_form_full_dimensional(permutation=True)
10 loops, best of 3: 9.12 ms per loop
}}}
However, the same tests show (again) that our python implementations from
#13525 are really, really slow:
{{{
sage: o = lattice_polytope.cross_polytope(4)
sage: %timeit o._palp_native_normal_form(permutation=False)
1 loops, best of 3: 33.7 s per loop
sage: %timeit o._palp_native_normal_form(permutation=True)
1 loops, best of 3: 33.6 s per loop
sage: %timeit o._palp_modified_normal_form(permutation=False)
1 loops, best of 3: 1.4 s per loop
sage: %timeit o._palp_modified_normal_form(permutation=True)
1 loops, best of 3: 1.38 s per loop
sage: %timeit o._normal_form_full_dimensional(permutation=False)
10 loops, best of 3: 11.2 ms per loop
sage: %timeit o._normal_form_full_dimensional(permutation=True)
10 loops, best of 3: 11.5 ms per loop
}}}
The following isn't really relevant for this ticket, but the reason that
they are so slow are the calls to GAP:
{{{
%prun o._palp_native_normal_form(permutation=True)
38627975 function calls (38584943 primitive calls) in 39.390 seconds
Ordered by: internal time
ncalls tottime percall cumtime percall filename:lineno(function)
428940 9.260 0.000 23.171 0.000 pexpect.py:918(expect_list)
19600688 4.943 0.000 4.943 0.000 {method 'search' of
'_sre.SRE_Pattern' objects}
98854 3.581 0.000 3.655 0.000 {method
'with_permuted_rows_and_columns' of 'sage.matrix.matrix0.Matrix' objects}
796103 2.139 0.000 2.139 0.000 {select.select}
796103 2.135 0.000 8.395 0.000
pexpect.py:502(read_nonblocking)
796103 1.921 0.000 1.921 0.000 {posix.read}
171376 1.513 0.000 1.513 0.000 {posix.write}
1 1.383 1.383 39.131 39.131
lattice_polytope.py:3109(_palp_PM_max)
85688 1.050 0.000 26.405 0.000 gap.py:576(_execute_line)
22916 1.049 0.000 18.948 0.001
lattice_polytope.py:3169(PGE)
796103 0.919 0.000 1.819 0.000 pexpect.py:743(isalive)
1592206 0.900 0.000 0.900 0.000 {posix.waitpid}
19818 0.833 0.000 14.553 0.001 permgroup.py:594(__call__)
42815 0.476 0.000 11.385 0.000 expect.py:1154(eval)
85688 0.428 0.000 26.977 0.000 gap.py:664(_eval_line)
42942 0.382 0.000 1.034 0.000
permutation.py:5608(from_cycles)
99725 0.346 0.000 0.472 0.000 free_module.py:899(__call__)
46719 0.317 0.000 0.412 0.000 permutation.py:542(__init__)
639678 0.286 0.000 0.286 0.000 {isinstance}
838918 0.270 0.000 0.270 0.000 {method 'find' of 'str'
objects}
615296 0.267 0.000 0.267 0.000 {method 'index' of 'list'
objects}
42815 0.247 0.000 11.715 0.000 gap.py:510(eval)
85884/42942 0.222 0.000 0.441 0.000 {repr}
2328491 0.221 0.000 0.221 0.000 {method 'start' of
'_sre.SRE_Match' objects}
171376 0.205 0.000 1.894 0.000 pexpect.py:660(send)
128426 0.202 0.000 0.222 0.000 expect.py:1310(_check_valid)
22917 0.194 0.000 0.429 0.000
permgroup_named.py:158(__classcall__)
171376 0.177 0.000 0.177 0.000 {time.sleep}
42815 0.160 0.000 12.065 0.000
interface.py:675(__contains__)
42873 0.151 0.000 16.769 0.000 expect.py:1276(__init__)
978573 0.150 0.000 0.196 0.000 {len}
42815 0.148 0.000 0.148 0.000
interface.py:508(__getattr__)
99709 0.144 0.000 0.144 0.000
free_module.py:330(create_key)
839045 0.131 0.000 0.131 0.000 {method 'lower' of 'str'
objects}
405591 0.123 0.000 0.157 0.000
combinat.py:1086(__getitem__)
42873 0.120 0.000 16.926 0.000 interface.py:162(__call__)
46719 0.116 0.000 0.116 0.000
permutation.py:4476(__classcall_private__)
42865 0.113 0.000 0.228 0.000 expect.py:1326(__del__)
85688 0.111 0.000 2.005 0.000 pexpect.py:672(sendline)
207596 0.100 0.000 0.100 0.000 {range}
42942 0.096 0.000 0.314 0.000 permutation.py:675(_repr_)
42873 0.094 0.000 16.473 0.000 gap.py:1294(set)
46719 0.085 0.000 0.498 0.000
sets_cat.py:310(_element_constructor_from_element_class)
857880 0.085 0.000 0.085 0.000 {method 'end' of
'_sre.SRE_Match' objects}
42942 0.074 0.000 0.118 0.000
global_options.py:664(__getitem__)
42815 0.072 0.000 11.788 0.000 gap.py:797(_contains)
602437 0.068 0.000 0.068 0.000 {method 'append' of 'list'
objects}
42873 0.062 0.000 16.600 0.000 interface.py:387(_create)
...
}}}
Maybe that could be improved at some point. In any case, I'll now remove
the permutation flag.
--
Ticket URL: <http://trac.sagemath.org/ticket/15280#comment:28>
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.
