Skip to content

Instantly share code, notes, and snippets.

@cswiercz
Created January 11, 2016 17:13
Show Gist options
  • Save cswiercz/c136eda374d04a9d2172 to your computer and use it in GitHub Desktop.
Save cswiercz/c136eda374d04a9d2172 to your computer and use it in GitHub Desktop.
Pure-Sage Integral Basis timings
f = -y^8 + x^6 + 2*x^5
Fri Jan 8 11:53:49 2016 test.profile
10111400 function calls (10092038 primitive calls) in 18.657 seconds
Ordered by: internal time
List reduced from 1618 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
23382 1.540 0.000 4.408 0.000 qqbar.py:7433(_interval_fast)
161795/161708 1.430 0.000 1.631 0.000 complex_interval_field.py:364(__call__)
24650 1.230 0.000 2.266 0.000 {method '_rational_' of 'sage.rings.number_field.number_field_element.NumberFieldElement' objects}
101293 0.973 0.000 2.212 0.000 polynomial_ring.py:318(_element_constructor_)
616/280 0.787 0.001 1.033 0.004 qqbar.py:2444(super_poly)
2749578 0.674 0.000 0.674 0.000 {isinstance}
57756 0.607 0.000 1.239 0.000 multi_polynomial_ring.py:184(__call__)
58491 0.546 0.000 0.564 0.000 {method '_coerce_' of 'sage.structure.parent_old.Parent' objects}
1648 0.492 0.000 5.643 0.003 puiseux_series_ring_element.py:291(_add_)
158911 0.392 0.000 5.264 0.000 qqbar.py:3151(__init__)
50759 0.381 0.000 1.318 0.000 rings.py:708(__getitem__)
23662 0.377 0.000 1.246 0.000 {method 'polynomial' of 'sage.rings.number_field.number_field_element.NumberFieldElement' objects}
1504 0.359 0.000 3.669 0.002 puiseux_series_ring_element.py:318(_mul_)
51054 0.344 0.000 0.802 0.000 polynomial_ring_constructor.py:47(PolynomialRing)
16163 0.332 0.000 1.322 0.000 laurent_series_ring.py:273(_element_constructor_)
18622 0.291 0.000 2.664 0.000 qqbar.py:2778(an_muldiv_element)
8364 0.267 0.000 2.980 0.000 {method 'laurent_polynomial' of 'sage.rings.laurent_series_ring_element.LaurentSeries' objects}
36347 0.242 0.000 0.297 0.000 number_field.py:6660(_coerce_non_number_field_element_in)
115705/112301 0.240 0.000 1.066 0.000 qqbar.py:4158(__eq__)
24235 0.239 0.000 0.928 0.000 power_series_ring.py:647(_element_constructor_)
Fri Jan 8 11:53:49 2016 test.profile
10111400 function calls (10092038 primitive calls) in 18.657 seconds
Ordered by: cumulative time
List reduced from 1618 to 20 due to restriction <20>
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 18.664 18.664 integralbasis.py:171(integral_basis)
1 0.001 0.001 18.656 18.656 integralbasis.py:217(_integral_basis_monic)
7 0.033 0.005 15.365 2.195 integralbasis.py:265(compute_bd)
1072/688 0.012 0.000 9.877 0.014 {sum}
736 0.071 0.000 7.186 0.010 integralbasis.py:302(<genexpr>)
49657 0.126 0.000 6.819 0.000 qqbar.py:3291(_mul_)
1648 0.492 0.000 5.643 0.003 puiseux_series_ring_element.py:291(_add_)
37432 0.204 0.000 5.448 0.000 multi_polynomial_element.py:220(_mul_)
150897 0.128 0.000 5.312 0.000 qqbar.py:4018(__init__)
158911 0.392 0.000 5.264 0.000 qqbar.py:3151(__init__)
23382 1.540 0.000 4.408 0.000 qqbar.py:7433(_interval_fast)
1504 0.359 0.000 3.669 0.002 puiseux_series_ring_element.py:318(_mul_)
8360 0.042 0.000 3.326 0.000 puiseux_series_ring_element.py:143(__init__)
2 0.000 0.000 3.276 1.638 integralbasis.py:129(compute_series_truncations)
8364 0.267 0.000 2.980 0.000 {method 'laurent_polynomial' of 'sage.rings.laurent_series_ring_element.LaurentSeries' objects}
27631 0.115 0.000 2.718 0.000 qqbar.py:7136(__new__)
18622 0.291 0.000 2.664 0.000 qqbar.py:2778(an_muldiv_element)
24650 1.230 0.000 2.266 0.000 {method '_rational_' of 'sage.rings.number_field.number_field_element.NumberFieldElement' objects}
101293 0.973 0.000 2.212 0.000 polynomial_ring.py:318(_element_constructor_)
18 0.023 0.001 1.882 0.105 integralbasis.py:320(solve_coefficient_system)
b =
[1, y, y^2/x, y^3/x, y^4/x^2, y^5/x^3, y^6/x^3, y^7/x^4]
@cswiercz
Copy link
Author

All of this is moot, for the moment, because I found out that Singular implements an integral basis algorithm over Q[x,y] that is (a) fast and (b) works.

Based on van Hoeij's paper it seems like his algorithm allows for arbitrary (at least, algebraic) extensions of Q as base rings. So there is potentially good reason to keep this version around.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment