Opened 7 years ago
Last modified 3 years ago
#17895 closed defect
Computing all roots is faster than computing a single one — at Version 3
| Reported by: | gagern | Owned by: | |
|---|---|---|---|
| Priority: | major | Milestone: | sage-8.9 |
| Component: | number fields | Keywords: | qqbar polynomial_root roots performance |
| Cc: | sbrandhorst | Merged in: | |
| Authors: | Reviewers: | ||
| Report Upstream: | N/A | Work issues: | |
| Branch: | Commit: | ||
| Dependencies: | Stopgaps: |
Status badges
Description (last modified by )
The following example comes from comment:27:ticket:16964 via comment:2:ticket:17886.
sage: x,y = polygens(QQ,"x,y") sage: p1 = x^5 + 6*x^4 - 42*x^3 - 142*x^2 + 467*x + 422 sage: p2 = p1(x=(x-1)^2) sage: p3 = p2(x=x*y).resultant(p2,x).univariate_polynomial() sage: p4, = [f[0] for f in p3.factor() if f[0].degree() == 80] sage: ival = CIF((0.77, 0.78), (-0.08, -0.07)) sage: %time z1, = [r for r in p4.roots(QQbar, False) if r in ival] CPU times: user 1.43 s, sys: 195 ms, total: 1.62 s Wall time: 1.47 s sage: %time z2 = QQbar.polynomial_root(p4, ival) CPU times: user 1min 5s, sys: 212 ms, total: 1min 5s Wall time: 1min 5s
The computation for z1 works reasonably well and completes in under 2 seconds, but the one for z2 takes over a minute. Which is definitely wrong, since computing all roots and then choosing the right one should be more work, not less than just computing a single one!
The reason for this is the time spent in the square-free decomposition (called from sage/rings/polynomial/complex_roots.py) which behave differently depending whether the polynomial is defined with coefficients in QQ or AA
sage: %time _ = p4.squarefree_decomposition() CPU times: user 807 µs, sys: 0 ns, total: 807 µs Wall time: 883 µs sage: %time _ = p4.change_ring(AA).squarefree_decomposition() CPU times: user 40.1 s, sys: 3.21 ms, total: 40.1 s Wall time: 40.1 s
Change History (3)
comment:1 Changed 7 years ago by
comment:2 Changed 3 years ago by
For the record, here is what profiling shows
ncalls tottime percall cumtime percall filename:lineno(function)
6320 23.769 0.004 23.769 0.004 {built-in method _operator.sub}
6481 17.266 0.003 17.266 0.003 {built-in method _operator.mul}
2 0.225 0.112 0.231 0.116 {method 'roots' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
16711 0.188 0.000 0.188 0.000 sets_cat.py:974(_element_constructor_from_element_class)
89 0.069 0.001 0.070 0.001 {sage.rings.polynomial.refine_root.refine_root}
15053 0.037 0.000 0.272 0.000 qqbar.py:3074(__init__)
15287 0.031 0.000 0.227 0.000 qqbar.py:5723(_interval_fast)
1 0.028 0.028 41.429 41.429 fields.py:218(_gcd_univariate_polynomial)
14889 0.024 0.000 41.096 0.003 qqbar.py:7736(an_binop_rational)
15052 0.024 0.000 0.036 0.000 qqbar.py:5653(__init__)
47328 0.022 0.000 0.022 0.000 {built-in method builtins.isinstance}
15052 0.017 0.000 0.297 0.000 qqbar.py:4712(__init__)
6481 0.014 0.000 17.451 0.003 qqbar.py:3240(_mul_)
6320 0.012 0.000 23.946 0.004 qqbar.py:3284(_sub_)
15449 0.009 0.000 0.009 0.000 {built-in method sage.rings.real_mpfi.RealIntervalField}
15287 0.006 0.000 0.008 0.000 qqbar.py:4730(_ensure_real)
2088 0.003 0.000 0.022 0.000 qqbar.py:3271(_add_)
15450 0.003 0.000 0.003 0.000 {sage.rings.complex_interval.is_ComplexIntervalFieldElement}
448/160 0.002 0.000 0.004 0.000 complex_field.py:389(_element_constructor_)
4 0.002 0.000 0.024 0.006 {method 'derivative' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
2088 0.002 0.000 0.002 0.000 {built-in method _operator.add}
484 0.001 0.000 0.005 0.000 qqbar.py:4023(interval)
1322/1000 0.001 0.000 0.005 0.000 complex_interval_field.py:427(__call__)
484 0.001 0.000 0.003 0.000 qqbar.py:3999(interval_diameter)
216 0.001 0.000 0.003 0.000 {method 'n' of 'sage.structure.element.Element' objects}
1 0.001 0.001 41.766 41.766 qqbar.py:6487(_complex_refine_interval)
4 0.001 0.000 0.005 0.001 {built-in method builtins.sorted}
81 0.001 0.000 0.001 0.000 qqbar.py:5809(invert)
628/324 0.001 0.000 0.005 0.000 complex_field.py:352(__call__)
561 0.001 0.000 0.001 0.000 {built-in method builtins.hasattr}
240 0.001 0.000 0.004 0.000 misc.py:5558(_key_complex_for_display)
144 0.001 0.000 0.001 0.000 {method '__copy__' of 'sage.categories.map.Map' objects}
719 0.000 0.000 0.000 0.000 {method 'diameter' of 'sage.rings.real_mpfi.RealIntervalFieldElement' objects}
15 0.000 0.000 0.007 0.000 polynomial_element_generic.py:1052(__init__)
161/155 0.000 0.000 0.001 0.000 homset.py:84(Hom)
312 0.000 0.000 0.001 0.000 copy.py:66(copy)
2 0.000 0.000 0.086 0.043 complex_roots.py:47(interval_roots)
235 0.000 0.000 0.001 0.000 qqbar.py:3905(_more_precision)
1 0.000 0.000 41.757 41.757 complex_roots.py:147(complex_roots)
162 0.000 0.000 0.001 0.000 qqbar.py:5244(real_number)
161 0.000 0.000 0.001 0.000 qqbar.py:3970(interval_fast)
1067 0.000 0.000 0.000 0.000 complex_field.py:289(_real_field)
11 0.000 0.000 0.000 0.000 homset.py:582(__init__)
81 0.000 0.000 0.004 0.000 qqbar.py:3262(__invert__)
235 0.000 0.000 0.001 0.000 qqbar.py:4751(_more_precision)
2 0.000 0.000 0.000 0.000 polynomial_ring.py:234(__init__)
469 0.000 0.000 0.001 0.000 <frozen importlib._bootstrap>:1009(_handle_fromlist)
85 0.000 0.000 0.000 0.000 qqbar.py:3386(__bool__)
2 0.000 0.000 0.000 0.000 complex_field.py:193(__init__)
82 0.000 0.000 0.001 0.000 qqbar.py:720(_element_constructor_)
671 0.000 0.000 0.000 0.000 complex_interval_field.py:266(prec)
160 0.000 0.000 0.000 0.000 {method 'real' of 'sage.rings.complex_number.ComplexNumber' objects}
1 0.000 0.000 41.766 41.766 qqbar.py:6320(refine_interval)
218 0.000 0.000 0.001 0.000 complex_field.py:91(ComplexField)
80 0.000 0.000 0.003 0.000 fields.py:767(inverse_of_unit)
1 0.000 0.000 0.001 0.001 {method 'change_ring' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
216 0.000 0.000 0.000 0.000 {method 'abs' of 'sage.structure.element.RingElement' objects}
6 0.000 0.000 0.001 0.000 polynomial_ring_constructor.py:52(PolynomialRing)
1 0.000 0.000 41.436 41.436 fields.py:441(_squarefree_decomposition_univariate_polynomial)
160 0.000 0.000 0.000 0.000 {method 'imag' of 'sage.rings.complex_number.ComplexNumber' objects}
1 0.000 0.000 0.001 0.001 complex_roots.py:85(intervals_disjoint)
17 0.000 0.000 0.000 0.000 dynamic_class.py:127(dynamic_class)
160 0.000 0.000 0.000 0.000 {method 'real' of 'sage.rings.complex_interval.ComplexIntervalFieldElement' objects}
1 0.000 0.000 0.000 0.000 {method 'monic' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
9 0.000 0.000 0.008 0.001 polynomial_ring.py:320(_element_constructor_)
80 0.000 0.000 0.000 0.000 complex_roots.py:118(row_disjoint)
6 0.000 0.000 0.000 0.000 polynomial_ring_constructor.py:677(_single_variate)
1 0.000 0.000 0.000 0.000 dynamic_class.py:346(dynamic_class_internal)
6/5 0.000 0.000 0.000 0.000 {method 'has_coerce_map_from' of 'sage.structure.parent.Parent' objects}
496 0.000 0.000 0.000 0.000 complex_interval_field.py:255(is_exact)
2 0.000 0.000 0.000 0.000 category.py:499(__repr_object_names)
91 0.000 0.000 0.000 0.000 weakref.py:341(__init__)
6 0.000 0.000 0.000 0.000 homset.py:40(RingHomset)
468 0.000 0.000 0.000 0.000 {method 'precision' of 'sage.rings.real_mpfi.RealIntervalFieldElement' objects}
8 0.000 0.000 0.000 0.000 rings.py:322(_Hom_)
1 0.000 0.000 41.757 41.757 qqbar.py:6060(complex_roots)
160 0.000 0.000 0.000 0.000 {method 'imag' of 'sage.rings.complex_interval.ComplexIntervalFieldElement' objects}
36 0.000 0.000 0.000 0.000 complex_roots.py:112(column_disjoint)
85 0.000 0.000 0.000 0.000 {method 'contains_zero' of 'sage.rings.real_mpfi.RealIntervalFieldElement' objects}
3 0.000 0.000 0.000 0.000 {method '_coerce_map_via' of 'sage.structure.parent.Parent' objects}
97 0.000 0.000 0.000 0.000 weakref.py:336(__new__)
5 0.000 0.000 0.001 0.000 rings.py:845(__getitem__)
80 0.000 0.000 0.001 0.000 misc.py:5634(<lambda>)
152 0.000 0.000 0.000 0.000 {built-in method builtins.issubclass}
8 0.000 0.000 0.000 0.000 pushout.py:817(__init__)
97 0.000 0.000 0.000 0.000 {built-in method __new__ of type object at 0x7fc5f0f21a00}
6 0.000 0.000 0.000 0.000 {built-in method sage.structure.category_object.normalize_names}
333 0.000 0.000 0.000 0.000 {method 'append' of 'list' objects}
155 0.000 0.000 0.000 0.000 homset.py:1174(domain)
318 0.000 0.000 0.000 0.000 {method 'get' of 'dict' objects}
5 0.000 0.000 0.000 0.000 polynomial_ring.py:661(_coerce_map_from_)
306 0.000 0.000 0.000 0.000 complex_field.py:43(late_import)
1 0.000 0.000 41.768 41.768 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 qqbar.py:6545(<listcomp>)
144 0.000 0.000 0.000 0.000 {method 'precision' of 'sage.rings.real_mpfr.RealNumber' objects}
5 0.000 0.000 0.000 0.000 {method 'coerce_map_from' of 'sage.structure.parent.Parent' objects}
2 0.000 0.000 0.000 0.000 polynomial_singular_interface.py:355(can_convert_to_singular)
4 0.000 0.000 0.000 0.000 {method '_populate_coercion_lists_' of 'sage.structure.parent.Parent' objects}
162 0.000 0.000 0.000 0.000 {method 'precision' of 'sage.rings.real_mpfr.RealField_class' objects}
3 0.000 0.000 0.000 0.000 complex_field.py:431(_coerce_map_from_)
1 0.000 0.000 0.000 0.000 sequence.py:80(Sequence)
8 0.000 0.000 0.000 0.000 polynomial_ring.py:628(construction)
2 0.000 0.000 0.000 0.000 polynomial_ring.py:1650(__init__)
3 0.000 0.000 0.000 0.000 rational_field.py:349(_coerce_map_from_)
16 0.000 0.000 0.000 0.000 <frozen importlib._bootstrap>:416(parent)
1 0.000 0.000 41.768 41.768 <string>:1(<module>)
1 0.000 0.000 0.000 0.000 qqbar.py:6533(<listcomp>)
146 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
200 0.000 0.000 0.000 0.000 {built-in method builtins.len}
2 0.000 0.000 0.000 0.000 polynomial_ring.py:1826(__init__)
4 0.000 0.000 0.000 0.000 polynomial_ring_constructor.py:672(_save_in_cache)
155 0.000 0.000 0.000 0.000 homset.py:1189(codomain)
149 0.000 0.000 0.000 0.000 copy.py:111(_copy_immutable)
2 0.000 0.000 0.000 0.000 category.py:525(_repr_object_names)
1 0.000 0.000 41.757 41.757 qqbar.py:6060(complex_roots)
1 0.000 0.000 41.768 41.768 qqbar.py:6171(__init__)
1 0.000 0.000 41.436 41.436 {method 'squarefree_decomposition' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
1 0.000 0.000 41.768 41.768 qqbar.py:1361(polynomial_root)
1 0.000 0.000 41.757 41.757 qqbar.py:6637(_complex_isolate_interval)
comment:3 Changed 3 years ago by
- Description modified (diff)
Note: See
TracTickets for help on using
tickets.
If the interval is close enough to the root,
QQbar.polynomial_rootis fast