triangle(a, b, c) is slow

[saraedum]

For somewhat large angles, triangle() is extremely slow. I tried triangle(a,b,c) for (26, 49, 75), (26, 48, 75), and (27, 47, 75). Neither of these terminated within 300h.

Here is a medium size case that terminates but takes a long time. Maybe that's useful for optimizing things:

>>> %prun -s cumtime flatsurf.polygons.triangle(22, 23, 24)

    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
         1    0.000    0.000    7.378    7.378 {built-in method builtins.exec}
         1    0.000    0.000    7.378    7.378 <string>:1(<module>)
         1    0.000    0.000    7.378    7.378 polygon.py:2665(triangle)
         1    0.000    0.000    7.371    7.371 polygon.py:2001(__init__)
         1    0.097    0.097    7.209    7.209 subfield.py:55(subfield_from_elements)
      2441    4.212    0.002    4.770    0.002 {method 'echelon_form' of 'sage.matrix.matrix_rational_dense.Matrix_rational_dense' objects}
        81    0.000    0.000    2.772    0.034 free_module.py:3880(span)
        81    0.000    0.000    2.771    0.034 free_module.py:7050(__init__)
        81    0.000    0.000    2.771    0.034 free_module.py:6852(__init__)
        81    0.004    0.000    2.771    0.034 free_module.py:5746(__init__)
        40    0.000    0.000    2.758    0.069 free_module.py:3722(__add__)
        81    0.001    0.000    2.514    0.031 free_module.py:6977(_echelonized_basis)
      1208    0.003    0.000    2.509    0.002 free_module.py:1837(coordinates)
 5741/5325    0.067    0.000    2.471    0.000 free_module.py:1062(_element_constructor_)
      1396    0.001    0.000    2.440    0.002 free_module.py:7209(coordinate_vector)
      1396    0.012    0.000    2.439    0.002 free_module.py:6598(echelon_coordinate_vector)
      1396    0.008    0.000    2.386    0.002 free_module.py:7144(echelon_coordinates)
      2360    0.003    0.000    2.305    0.001 free_module.py:3748(echelonized_basis_matrix)
63971/1491    0.996    0.000    1.531    0.001 number_field.py:1622(_element_constructor_)

[saraedum]

I guess that this call is the problem:

https://github.com/flatsurf/sage-flatsurf/blob/master/flatsurf/geometry/subfield.py#L166

We probably don't need this and can use a similar trick we used in GL2ROrbitClosure._rank().

[videlec]

We can definitely shortcut subfield_from_elements in this situation (and many others). I will provide a PR.

[videlec]

See #140 that solves these particular cases. Though

• (26, 48, 75) and (27, 47, 75) takes 10 secs on my computer
• I agree that it would make sense to avoid completely the use of subspace (unless the dimension is very small) and go via rank.

[saraedum]

See #140 that solves these particular cases. Though

* `(26, 48, 75)` and `(27, 47, 75)` takes 10 secs on my computer

They take 20s for me. So maybe I don't want to run them in the CI with every PR.