Cleanup and speedup in QQbar

[videlec]

This is a task ticket for speed up and cleaning in sage.rings.qqbar

Prerequisites on number fields/polynomials/interval arithmetic

• 18332: implement is_integer and is_rational on number field elements

• 18334: implement unique_sign and unique_trunc on interval field elements

• 18337: implement real and imag on real intervals

• 17830: consider the natural order induced from RR for number fields with real embedding

• 19362, #28191: refine root

• 18356: implement composed_op from [BFSS]

• 19824: faster comparison for (real) embedded number fields

• 24503: enhanced LazyAlgebraic

Tasks in AA/QQbar:

• 18303: better comparisons

• 17886, #18242: faster exactification operations using power series and resultants (see also #18356)

• 15600: exactification is slow in do_polred

• 16222, #18122, #31889: enhanced minpoly

• 19954 and #19955: remove all descriptors except ANRoot, ANExtension and ANRational

• 20074: simplify method dispatcher for binary operators

• 12745: conversion issue QQbar -> AA

• 18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls

• 12715: number field embeddings should always have target in AA or QQbar

• 19356: QQbar.polynomial_root(): allow approximate root

• 21095: slowness in exactification

• 21838: do not make appear the imaginary (or real) part in QQbar when it is known to be zero

• 5574: Implement QQbar^QQ as action

• use firstly interval arithmetic for sign/floor/ceil/trunc/round instead of the _floor_ceil helper
• remove the following methods from ANDescr:
  • rational_value
  • is_field_element
  • is_exact
• (?) enhanced sage_input for ANExtension
• better powering (__pow__) using ANExtension and fix convention for powering in AA vs QQbar
• reimplement _real_refine_interval without these ugly dictionaries (see also #17895)
• use directly embedded number fields in AlgebraicGenerator as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them (let say 64) to avoid reevaluation in most cases

• 26944: improve hashing to avoid exact computations

• more generally, track down code in qqbar.py that may lead to larger extensions than necessary if an exact computation is triggered (for example, see if the formulas in ANUnaryExpr.exactify() can be optimized).

• 31767: more capable sign

Bugs

• 20209: QQbar -> RIF conversion fails

• 12745: Coercion problem with Algebraic Real Field

• 20288: representation and mutability of the description

CC: @mezzarobba @gagern @cheuberg

Component: number fields

Author: Vincent Delecroix

Issue created by migration from https://trac.sagemath.org/ticket/18333

[videlec]

Description changed:

--- 
+++ 
@@ -1,5 +1,9 @@
-This is a task ticket for speed up cleaning in `sage.rings.qqbar`
+This is a task ticket for speed up and cleaning in `sage.rings.qqbar`

 - #18332: implement `is_integer` and `is_rational` on number field elements
 - #18303: better comparisons
-- implement `unique_sign` and `unique_trunc` on interval field elements and use it for faster `sign`/`floor`/`ceil`/`trunc`/`round` on algebraic elements
+- #18334: implement `unique_sign` and `unique_trunc` on interval field elements
+- use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
+- enhanced `sage_input` for `ANRoot`
+- remove `ANRootOfUnity` as one of the descriptor
+- better powering (`__pow__`) and fix convention for powering in `AA` vs `QQbar`

[videlec]

Description changed:

--- 
+++ 
@@ -5,5 +5,10 @@
 - #18334: implement `unique_sign` and `unique_trunc` on interval field elements
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
 - enhanced `sage_input` for `ANRoot`
+- remove the following methods from `ANDescr`:
+   - `rational_value`
+   - `is_field_element`
+   - `is_exact`
 - remove `ANRootOfUnity` as one of the descriptor
 - better powering (`__pow__`) and fix convention for powering in `AA` vs `QQbar`
+- reimplement `_real_refine_interval` without these ugly dictionaries

[videlec]

Description changed:

--- 
+++ 
@@ -4,11 +4,11 @@
 - #18303: better comparisons
 - #18334: implement `unique_sign` and `unique_trunc` on interval field elements
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
-- enhanced `sage_input` for `ANRoot`
 - remove the following methods from `ANDescr`:
    - `rational_value`
    - `is_field_element`
    - `is_exact`
-- remove `ANRootOfUnity` as one of the descriptor
-- better powering (`__pow__`) and fix convention for powering in `AA` vs `QQbar`
+- fusion `ANRoot` and `ANRootOfUnity` within `ANExtension`
+- enhanced `sage_input` for `ANExtension`
+- better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries

[videlec]

Description changed:

--- 
+++ 
@@ -1,8 +1,14 @@
 This is a task ticket for speed up and cleaning in `sage.rings.qqbar`

+Prerequisites on number fields/interval arithmetic
 - #18332: implement `is_integer` and `is_rational` on number field elements
+- #18334: implement `unique_sign` and `unique_trunc` on interval field elements
+- #18337: implement `real` and `imag` on real intervals
+
+Actual tasks:
 - #18303: better comparisons
-- #18334: implement `unique_sign` and `unique_trunc` on interval field elements
+- #17886 and #18242: faster qqbar operations using resultants
+- #15600: exactification is slow in `do_polred`
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
 - remove the following methods from `ANDescr`:
    - `rational_value`
@@ -11,4 +17,5 @@
 - fusion `ANRoot` and `ANRootOfUnity` within `ANExtension`
 - enhanced `sage_input` for `ANExtension`
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
-- reimplement `_real_refine_interval` without these ugly dictionaries
+- reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
+- make number field elements compare themselves and use that

[videlec]

Description changed:

--- 
+++ 
@@ -9,6 +9,7 @@
 - #18303: better comparisons
 - #17886 and #18242: faster qqbar operations using resultants
 - #15600: exactification is slow in `do_polred`
+- #16222, #18122: enhanced minpoly
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
 - remove the following methods from `ANDescr`:
    - `rational_value`

[videlec]

Description changed:

--- 
+++ 
@@ -4,19 +4,21 @@
 - #18332: implement `is_integer` and `is_rational` on number field elements
 - #18334: implement `unique_sign` and `unique_trunc` on interval field elements
 - #18337: implement `real` and `imag` on real intervals
+- #17830: consider the natural order induced from `RR` for number fields with real embedding

-Actual tasks:
+Tasks in `AA/QQbar`:
 - #18303: better comparisons
 - #17886 and #18242: faster qqbar operations using resultants
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
-- use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round`
+- use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`
    - `is_field_element`
    - `is_exact`
 - fusion `ANRoot` and `ANRootOfUnity` within `ANExtension`
+- remove redundancy between the unary operators `norm`, `abs`, `real`, `imag` and `conjugate`
 - enhanced `sage_input` for `ANExtension`
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
-- make number field elements compare themselves and use that
+- use directly embedded number fields in `AlgebraicGenerator`

[videlec]

Description changed:

--- 
+++ 
@@ -11,6 +11,7 @@
 - #17886 and #18242: faster qqbar operations using resultants
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
+- #12745: conversion issue `QQbar -> AA`
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[videlec]

Description changed:

--- 
+++ 
@@ -12,6 +12,7 @@
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
 - #12745: conversion issue `QQbar -> AA`
+- #18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[videlec]

Description changed:

--- 
+++ 
@@ -8,7 +8,7 @@

 Tasks in `AA/QQbar`:
 - #18303: better comparisons
-- #17886 and #18242: faster qqbar operations using resultants
+- #17886, #18356, #18242: faster qqbar operations using resultants
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
 - #12745: conversion issue `QQbar -> AA`

[zimmermann6]

comment:11

about slowness of QQbar, see #19910.

[videlec]

Description changed:

--- 
+++ 
@@ -1,14 +1,16 @@
 This is a task ticket for speed up and cleaning in `sage.rings.qqbar`

-Prerequisites on number fields/interval arithmetic
+Prerequisites on number fields/polynomials/interval arithmetic
 - #18332: implement `is_integer` and `is_rational` on number field elements
 - #18334: implement `unique_sign` and `unique_trunc` on interval field elements
 - #18337: implement `real` and `imag` on real intervals
 - #17830: consider the natural order induced from `RR` for number fields with real embedding
+- #19362: refine root
+- #18356: implement composed_op from [BFSS]

 Tasks in `AA/QQbar`:
 - #18303: better comparisons
-- #17886, #18356, #18242: faster qqbar operations using resultants
+- #17886, #18242: faster exactification operations using power series and resultants (see also #18356)
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
 - #12745: conversion issue `QQbar -> AA`
@@ -23,4 +25,4 @@
 - enhanced `sage_input` for `ANExtension`
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
-- use directly embedded number fields in `AlgebraicGenerator`
+- use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases.

[videlec]

Description changed:

--- 
+++ 
@@ -7,6 +7,7 @@
 - #17830: consider the natural order induced from `RR` for number fields with real embedding
 - #19362: refine root
 - #18356: implement composed_op from [BFSS]
+- #19824: faster comparison for (real) embedded number fields

 Tasks in `AA/QQbar`:
 - #18303: better comparisons

[videlec]

Description changed:

--- 
+++ 
@@ -14,6 +14,7 @@
 - #17886, #18242: faster exactification operations using power series and resultants (see also #18356)
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
+- #19954 and #19955: remove all descriptors except `ANRoot`, `ANExtension` and `ANRational`
 - #12745: conversion issue `QQbar -> AA`
 - #18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
@@ -21,9 +22,7 @@
    - `rational_value`
    - `is_field_element`
    - `is_exact`
-- fusion `ANRoot` and `ANRootOfUnity` within `ANExtension`
-- remove redundancy between the unary operators `norm`, `abs`, `real`, `imag` and `conjugate`
-- enhanced `sage_input` for `ANExtension`
+- (?) enhanced `sage_input` for `ANExtension`
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
 - use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases.

[videlec]

Description changed:

--- 
+++ 
@@ -15,6 +15,7 @@
 - #15600: exactification is slow in `do_polred`
 - #16222, #18122: enhanced minpoly
 - #19954 and #19955: remove all descriptors except `ANRoot`, `ANExtension` and `ANRational`
+- #20074: simplify method dispatcher for binary operators
 - #12745: conversion issue `QQbar -> AA`
 - #18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper

[nbruin]

comment:16

There's an issue on QQBar element powering reported in #18836 comment 9 that may have interaction with what you're doing here (perhaps you're solving the issue?). Perhaps it's worthwhile including that problem in this QQbar cleanup operation somewhere.

[videlec]

Description changed:

--- 
+++ 
@@ -27,3 +27,7 @@
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
 - use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases.
+
+Bugs
+
+- #20209: `QQbar -> RIF` conversion fails

[videlec]

Description changed:

--- 
+++ 
@@ -18,6 +18,8 @@
 - #20074: simplify method dispatcher for binary operators
 - #12745: conversion issue `QQbar -> AA`
 - #18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls
+- #12715: number field embeddings should always have target in `AA` or `QQbar`
+- #19356: QQbar.polynomial_root(): allow approximate root
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[videlec]

Description changed:

--- 
+++ 
@@ -20,6 +20,7 @@
 - #18106: introduce a polynomial descriptor, make sum and product be n-ary instead of binary and get rid of recursive calls
 - #12715: number field embeddings should always have target in `AA` or `QQbar`
 - #19356: QQbar.polynomial_root(): allow approximate root
+- #21095: slowness in exactification
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[videlec]

Description changed:

--- 
+++ 
@@ -34,3 +34,4 @@
 Bugs

 - #20209: `QQbar -> RIF` conversion fails
+- #12745: Coercion problem with Algebraic Real Field

[videlec]

Description changed:

--- 
+++ 
@@ -21,6 +21,7 @@
 - #12715: number field embeddings should always have target in `AA` or `QQbar`
 - #19356: QQbar.polynomial_root(): allow approximate root
 - #21095: slowness in exactification
+- #21838: do not make appear the imaginary (or real) part in QQbar when it is known to be zero
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`
@@ -35,3 +36,4 @@

 - #20209: `QQbar -> RIF` conversion fails
 - #12745: Coercion problem with Algebraic Real Field
+- #20288: representation and mutability of the description

[videlec]

Description changed:

--- 
+++ 
@@ -8,6 +8,7 @@
 - #19362: refine root
 - #18356: implement composed_op from [BFSS]
 - #19824: faster comparison for (real) embedded number fields
+- #24503: enhanced `LazyAlgebraic`

 Tasks in `AA/QQbar`:
 - #18303: better comparisons

[jdemeyer]

Description changed:

--- 
+++ 
@@ -22,7 +22,9 @@
 - #12715: number field embeddings should always have target in `AA` or `QQbar`
 - #19356: QQbar.polynomial_root(): allow approximate root
 - #21095: slowness in exactification
-- #21838: do not make appear the imaginary (or real) part in QQbar when it is known to be zero
+- #21838: do not make appear the imaginary (or real) part in QQbar when 
+it is known to be zero
+- #5574: Implement QQbar^QQ as action
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[jdemeyer]

Description changed:

--- 
+++ 
@@ -22,8 +22,7 @@
 - #12715: number field embeddings should always have target in `AA` or `QQbar`
 - #19356: QQbar.polynomial_root(): allow approximate root
 - #21095: slowness in exactification
-- #21838: do not make appear the imaginary (or real) part in QQbar when 
-it is known to be zero
+- #21838: do not make appear the imaginary (or real) part in QQbar when it is known to be zero
 - #5574: Implement QQbar^QQ as action
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:

[jdemeyer]

Description changed:

--- 
+++ 
@@ -23,7 +23,7 @@
 - #19356: QQbar.polynomial_root(): allow approximate root
 - #21095: slowness in exactification
 - #21838: do not make appear the imaginary (or real) part in QQbar when it is known to be zero
-- #5574: Implement QQbar^QQ as action
+- #5574: Implement QQbar<sup>QQ</sup> as action
 - use firstly interval arithmetic for `sign`/`floor`/`ceil`/`trunc`/`round` instead of the `_floor_ceil` helper
 - remove the following methods from `ANDescr`:
    - `rational_value`

[mezzarobba]

Description changed:

--- 
+++ 
@@ -32,7 +32,9 @@
 - (?) enhanced `sage_input` for `ANExtension`
 - better powering (`__pow__`) using `ANExtension` and fix convention for powering in `AA` vs `QQbar`
 - reimplement `_real_refine_interval` without these ugly dictionaries (see also #17895)
-- use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases.
+- use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases
+- #26944: improve hashing to avoid exact computations
+- more generally, track down code in qqbar.py that may lead to larger extensions than necessary if an exact computation is triggered (for example, see if the formulas in `ANUnaryExpr.exactify()` can be optimized).

 Bugs

[videlec]

Description changed:

--- 
+++ 
@@ -5,7 +5,7 @@
 - #18334: implement `unique_sign` and `unique_trunc` on interval field elements
 - #18337: implement `real` and `imag` on real intervals
 - #17830: consider the natural order induced from `RR` for number fields with real embedding
-- #19362: refine root
+- #19362, #28191: refine root
 - #18356: implement composed_op from [BFSS]
 - #19824: faster comparison for (real) embedded number fields
 - #24503: enhanced `LazyAlgebraic`

[slel]

comment:30

• sage-devel, 2021-04-29: The sign() method in QQbar overlooks some (presumably) easy shortcuts

[videlec]

Description changed:

--- 
+++ 
@@ -14,7 +14,7 @@
 - #18303: better comparisons
 - #17886, #18242: faster exactification operations using power series and resultants (see also #18356)
 - #15600: exactification is slow in `do_polred`
-- #16222, #18122: enhanced minpoly
+- #16222, #18122, #31889: enhanced minpoly
 - #19954 and #19955: remove all descriptors except `ANRoot`, `ANExtension` and `ANRational`
 - #20074: simplify method dispatcher for binary operators
 - #12745: conversion issue `QQbar -> AA`
@@ -35,6 +35,7 @@
 - use directly embedded number fields in `AlgebraicGenerator` as comparison there is faster (see #17830 and #19824). We might want that these embedded number field carries an interval of fixed precision with them  (let say `64`) to avoid reevaluation in most cases
 - #26944: improve hashing to avoid exact computations
 - more generally, track down code in qqbar.py that may lead to larger extensions than necessary if an exact computation is triggered (for example, see if the formulas in `ANUnaryExpr.exactify()` can be optimized).
+- #31767: more capable sign 

 Bugs