Skip to content
This repository was archived by the owner on Jan 31, 2023. It is now read-only.

Latest commit

 

History

History
898 lines (683 loc) · 73 KB

20749.md

File metadata and controls

898 lines (683 loc) · 73 KB

Issue 20749: Use PARI nfeltup() for inclusion of base field into relative number field

archive/issues_020512.json:

{
    "assignees": [],
    "body": "<div id=\"comment:0\"></div>\n\nAs noticed in #20693, construction of elements of a relative number field from elements of the base field is extremely slow.  This is because `NumberField_relative.__base_inclusion()` uses the PARI function `eltreltoabs`, which converts arbitrary relative number field elements into absolute representation; instead, it should use the much faster `nfeltup`.\n\nCC:  @sagetrac-ehlen @jdemeyer\n\nComponent: **number fields**\n\nKeywords: **relative number field pari**\n\nAuthor: **Peter Bruin**\n\nBranch/Commit: **[`2cb5c94`](https://github.com/sagemath/sagetrac-mirror/commit/2cb5c94937b32696f607d6cc901b34dabd1e33a8)**\n\nReviewer: **Stephan Ehlen**\n\n_Issue created by migration from https://trac.sagemath.org/ticket/20749_\n\n",
    "closed_at": "2016-06-11T22:28:19Z",
    "created_at": "2016-06-01T13:33:11Z",
    "labels": [
        "https://github.com/sagemath/sage/labels/c%3A%20number%20fields",
        "https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
        "https://github.com/sagemath/sage/labels/enhancement"
    ],
    "milestone": "https://github.com/sagemath/sage/milestones/sage-7.3",
    "reactions": [],
    "repository": "https://github.com/sagemath/sage",
    "title": "Use PARI nfeltup() for inclusion of base field into relative number field",
    "type": "issue",
    "updated_at": "2016-06-11T22:28:19Z",
    "url": "https://github.com/sagemath/sage/issues/20749",
    "user": "https://github.com/pjbruin"
}

As noticed in #20693, construction of elements of a relative number field from elements of the base field is extremely slow. This is because NumberField_relative.__base_inclusion() uses the PARI function eltreltoabs, which converts arbitrary relative number field elements into absolute representation; instead, it should use the much faster nfeltup.

CC: @sagetrac-ehlen @jdemeyer

Component: number fields

Keywords: relative number field pari

Author: Peter Bruin

Branch/Commit: 2cb5c94

Reviewer: Stephan Ehlen

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

archive/issue_events_289575.json:

{
    "actor": "https://github.com/pjbruin",
    "created_at": "2016-06-01T13:33:11Z",
    "event": "milestoned",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "milestone_number": null,
    "milestone_title": "sage-7.3",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289575"
}

archive/issue_events_289576.json:

{
    "actor": "https://github.com/pjbruin",
    "created_at": "2016-06-01T13:33:11Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/c%3A%20number%20fields",
    "label_color": "0000ff",
    "label_name": "c: number fields",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289576"
}

archive/issue_events_289577.json:

{
    "actor": "https://github.com/pjbruin",
    "created_at": "2016-06-01T13:33:11Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/p%3A%20major%20/%203",
    "label_color": "ffbb00",
    "label_name": "p: major / 3",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289577"
}

archive/issue_events_289578.json:

{
    "actor": "https://github.com/pjbruin",
    "created_at": "2016-06-01T13:33:11Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/enhancement",
    "label_color": "696969",
    "label_name": "enhancement",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289578"
}

archive/issue_comments_300819.json:

{
    "body": "Changed keywords from **pari** to **relative number field pari**",
    "created_at": "2016-06-01T14:51:09Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300819",
    "user": "https://github.com/pjbruin"
}

Changed keywords from pari to relative number field pari

archive/issue_comments_300820.json:

{
    "body": "<div id=\"comment:1\" align=\"right\">comment:1</div>\n\nAs I just discovered, I already made an attempt at this about a year ago as a follow-up to #252.  I finished it and made it into the attached branch.  Now testing...",
    "created_at": "2016-06-01T14:51:09Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300820",
    "user": "https://github.com/pjbruin"
}
comment:1

As I just discovered, I already made an attempt at this about a year ago as a follow-up to #252. I finished it and made it into the attached branch. Now testing...

archive/issue_comments_300821.json:

{
    "body": "Branch: **[u/pbruin/20749-pari_nfeltup](https://github.com/sagemath/sagetrac-mirror/tree/u/pbruin/20749-pari_nfeltup)**",
    "created_at": "2016-06-01T14:51:09Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300821",
    "user": "https://github.com/pjbruin"
}

Branch: u/pbruin/20749-pari_nfeltup

archive/issue_comments_300822.json:

{
    "body": "Commit: **[`9f1d90b`](https://github.com/sagemath/sagetrac-mirror/commit/9f1d90be8d3f05b6d5de8ee75e36e6d17ad52095)**",
    "created_at": "2016-06-01T14:51:09Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300822",
    "user": "https://github.com/pjbruin"
}

Commit: 9f1d90b

archive/issue_comments_300823.json:

{
    "body": "<div id=\"comment:2\" align=\"right\">comment:2</div>\n\nSince I'm very interested in this and its implications for computing newforms  (#20693), I can review it once you'e happy with the patch. Thanks a lot for digging into this!",
    "created_at": "2016-06-01T15:03:45Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300823",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:2

Since I'm very interested in this and its implications for computing newforms (#20693), I can review it once you'e happy with the patch. Thanks a lot for digging into this!

archive/issue_events_289579.json:

{
    "actor": "https://github.com/pjbruin",
    "created_at": "2016-06-01T20:18:04Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289579"
}

archive/issue_comments_300824.json:

{
    "body": "<div id=\"comment:3\" align=\"right\">comment:3</div>\n\nAll doctests passed.",
    "created_at": "2016-06-01T20:18:04Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300824",
    "user": "https://github.com/pjbruin"
}
comment:3

All doctests passed.

archive/issue_comments_300825.json:

{
    "body": "Reviewer: **Stephan Ehlen**",
    "created_at": "2016-06-01T22:55:18Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300825",
    "user": "https://github.com/sagetrac-ehlen"
}

Reviewer: Stephan Ehlen

archive/issue_comments_300826.json:

{
    "body": "<div id=\"comment:5\" align=\"right\">comment:5</div>\n\nI started to review your changes. So far I can confirm that this does what it's supposed to do (see some timings below) but there seem to be some negative side-effects on the creation of relative extension.\n\nI tried the following example (which occurred when computing newforms at some point):\n\n```\nsage: K.<zeta10>=CyclotomicField(10)\nsage: y=polygen(K)\nsage: %prun L.<a> = K.extension(y^8 + (15*zeta10^3 - 33*zeta10^2 + 33*zeta10 - 15)*y^7 + (2712*zeta10^3 + 474*zeta10 - 474)*y^6 + (39516*zeta10^3 - 67788*zeta10^2 + 39516*zeta10)*y^5 + (-799088*zeta10^2 - 1185224*zeta10 - 799088)*y^4 + (20680992*zeta10^3 - 20680992*zeta10^2 + 11168256)*y^3 + (-432096000*zeta10^3 + 155681408*zeta10^2 - 155681408*zeta10 + 432096000)*y^2 + (1391139840*zeta10^3 - 2598142464*zeta10 + 2598142464)*y + 24488994816*zeta10^3 - 2361024512*zeta10^2 + 24488994816*zeta10)\n```\n\nIn sage 7.1, the extension is much faster created than in this branch.\nHere are the top contributions in sage 7.1:\n\n```\n         676 function calls (670 primitive calls) in 0.056 seconds\n\n   Ordered by: internal time\n\n   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n        1    0.049    0.049    0.049    0.049 {method '_nf_rnfeq' of 'sage.libs.pari.gen.gen' objects}\n        1    0.003    0.003    0.003    0.003 {method 'polisirreducible' of 'sage.libs.pari.gen.gen' objects}\n       10    0.001    0.000    0.001    0.000 polynomial_ring.py:299(_element_constructor_)\n      5/4    0.001    0.000    0.002    0.000 number_field.py:1403(_element_constructor_)\n        1    0.001    0.001    0.056    0.056 <string>:1(<module>)\n        1    0.000    0.000    0.055    0.055 number_field_rel.py:170(__init__)\n        2    0.000    0.000    0.000    0.000 {method '_pari_with_name' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}\n        4    0.000    0.000    0.000    0.000 number_field_rel.py:1824(absolute_polynomial_ntl)\n        2    0.000    0.000    0.000    0.000 homset.py:542(__init__)\n       26    0.000    0.000    0.000    0.000 number_field.py:9271(_element_constructor_)\n        4    0.000    0.000    0.000    0.000 homset.py:86(Hom)\n        2    0.000    0.000    0.001    0.000 {method '_generic_convert_map' of 'sage.structure.parent_old.Parent' objects}\n      261    0.000    0.000    0.000    0.000 {isinstance}\n       26    0.000    0.000    0.000    0.000 number_field.py:6684(_coerce_non_number_field_element_in)\n        1    0.000    0.000    0.000    0.000 number_field.py:1140(__init__)\n        1    0.000    0.000    0.000    0.000 {method '_first_ngens' of 'sage.structure.category_object.CategoryObject' objects}\n        3    0.000    0.000    0.000    0.000 {hasattr}\n        2    0.000    0.000    0.000    0.000 number_field_rel.py:824(_coerce_non_number_field_element_in)\n        1    0.000    0.000    0.049    0.049 number_field_rel.py:1845(absolute_polynomial)\n        2    0.000    0.000    0.000    0.000 {method '_eltreltoabs' of 'sage.libs.pari.gen.gen' objects}\n```\n\nAnd here in this branch:\n\n```\n         694 function calls (688 primitive calls) in 0.674 seconds\n\n   Ordered by: internal time\n\n   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n        1    0.617    0.617    0.617    0.617 {method '_nf_nfzk' of 'sage.libs.pari.gen.gen' objects}\n        1    0.049    0.049    0.049    0.049 {method '_nf_rnfeq' of 'sage.libs.pari.gen.gen' objects}\n        1    0.003    0.003    0.003    0.003 {method 'polisirreducible' of 'sage.libs.pari.gen.gen' objects}\n       10    0.001    0.000    0.001    0.000 polynomial_ring.py:300(_element_constructor_)\n        1    0.001    0.001    0.674    0.674 <string>:1(<module>)\n      5/4    0.001    0.000    0.619    0.155 number_field.py:1408(_element_constructor_)\n        1    0.000    0.000    0.000    0.000 {method '_nfeltup' of 'sage.libs.pari.gen.gen' objects}\n        2    0.000    0.000    0.000    0.000 {method '_pari_with_name' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}\n        1    0.000    0.000    0.673    0.673 number_field_rel.py:171(__init__)\n```\n\nThe call to `'_nf_nfzk'` is now the main contributor and creating the extension is almost 12 times slower.\n@pjbruin: Do you think we can avoid slowing down the creation of extensions somehow?\n\nCoercing elements from the base into the extension, however, is now faster in general (but not always).\n\nSage 7.1:\n\n```\nsage: %timeit r=L(K.gen())\n1000 loops, best of 3: 503 \u00b5s per loop\nsage: %timeit r=L(K.gen()^2)\n10 loops, best of 3: 61.1 ms per loop\nsage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)\n10 loops, best of 3: 124 ms per loop\nsage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)\n10 loops, best of 3: 126 ms per loop\n```\n\n\nThis branch:\n\n```\nsage: %timeit r=L(K.gen())\n1000 loops, best of 3: 908 \u00b5s per loop\nsage: %timeit r=L(K.gen()^2)\n1000 loops, best of 3: 899 \u00b5s per loop\nsage: sage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)\n1000 loops, best of 3: 1.03 ms per loop\nsage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)\n```\n\nIn particular, the new function seems to scale much much better.",
    "created_at": "2016-06-01T23:17:06Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300826",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:5

I started to review your changes. So far I can confirm that this does what it's supposed to do (see some timings below) but there seem to be some negative side-effects on the creation of relative extension.

I tried the following example (which occurred when computing newforms at some point):

sage: K.<zeta10>=CyclotomicField(10)
sage: y=polygen(K)
sage: %prun L.<a> = K.extension(y^8 + (15*zeta10^3 - 33*zeta10^2 + 33*zeta10 - 15)*y^7 + (2712*zeta10^3 + 474*zeta10 - 474)*y^6 + (39516*zeta10^3 - 67788*zeta10^2 + 39516*zeta10)*y^5 + (-799088*zeta10^2 - 1185224*zeta10 - 799088)*y^4 + (20680992*zeta10^3 - 20680992*zeta10^2 + 11168256)*y^3 + (-432096000*zeta10^3 + 155681408*zeta10^2 - 155681408*zeta10 + 432096000)*y^2 + (1391139840*zeta10^3 - 2598142464*zeta10 + 2598142464)*y + 24488994816*zeta10^3 - 2361024512*zeta10^2 + 24488994816*zeta10)

In sage 7.1, the extension is much faster created than in this branch. Here are the top contributions in sage 7.1:

         676 function calls (670 primitive calls) in 0.056 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.049    0.049    0.049    0.049 {method '_nf_rnfeq' of 'sage.libs.pari.gen.gen' objects}
        1    0.003    0.003    0.003    0.003 {method 'polisirreducible' of 'sage.libs.pari.gen.gen' objects}
       10    0.001    0.000    0.001    0.000 polynomial_ring.py:299(_element_constructor_)
      5/4    0.001    0.000    0.002    0.000 number_field.py:1403(_element_constructor_)
        1    0.001    0.001    0.056    0.056 <string>:1(<module>)
        1    0.000    0.000    0.055    0.055 number_field_rel.py:170(__init__)
        2    0.000    0.000    0.000    0.000 {method '_pari_with_name' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
        4    0.000    0.000    0.000    0.000 number_field_rel.py:1824(absolute_polynomial_ntl)
        2    0.000    0.000    0.000    0.000 homset.py:542(__init__)
       26    0.000    0.000    0.000    0.000 number_field.py:9271(_element_constructor_)
        4    0.000    0.000    0.000    0.000 homset.py:86(Hom)
        2    0.000    0.000    0.001    0.000 {method '_generic_convert_map' of 'sage.structure.parent_old.Parent' objects}
      261    0.000    0.000    0.000    0.000 {isinstance}
       26    0.000    0.000    0.000    0.000 number_field.py:6684(_coerce_non_number_field_element_in)
        1    0.000    0.000    0.000    0.000 number_field.py:1140(__init__)
        1    0.000    0.000    0.000    0.000 {method '_first_ngens' of 'sage.structure.category_object.CategoryObject' objects}
        3    0.000    0.000    0.000    0.000 {hasattr}
        2    0.000    0.000    0.000    0.000 number_field_rel.py:824(_coerce_non_number_field_element_in)
        1    0.000    0.000    0.049    0.049 number_field_rel.py:1845(absolute_polynomial)
        2    0.000    0.000    0.000    0.000 {method '_eltreltoabs' of 'sage.libs.pari.gen.gen' objects}

And here in this branch:

         694 function calls (688 primitive calls) in 0.674 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.617    0.617    0.617    0.617 {method '_nf_nfzk' of 'sage.libs.pari.gen.gen' objects}
        1    0.049    0.049    0.049    0.049 {method '_nf_rnfeq' of 'sage.libs.pari.gen.gen' objects}
        1    0.003    0.003    0.003    0.003 {method 'polisirreducible' of 'sage.libs.pari.gen.gen' objects}
       10    0.001    0.000    0.001    0.000 polynomial_ring.py:300(_element_constructor_)
        1    0.001    0.001    0.674    0.674 <string>:1(<module>)
      5/4    0.001    0.000    0.619    0.155 number_field.py:1408(_element_constructor_)
        1    0.000    0.000    0.000    0.000 {method '_nfeltup' of 'sage.libs.pari.gen.gen' objects}
        2    0.000    0.000    0.000    0.000 {method '_pari_with_name' of 'sage.rings.polynomial.polynomial_element.Polynomial' objects}
        1    0.000    0.000    0.673    0.673 number_field_rel.py:171(__init__)

The call to '_nf_nfzk' is now the main contributor and creating the extension is almost 12 times slower. @pjbruin: Do you think we can avoid slowing down the creation of extensions somehow?

Coercing elements from the base into the extension, however, is now faster in general (but not always).

Sage 7.1:

sage: %timeit r=L(K.gen())
1000 loops, best of 3: 503 µs per loop
sage: %timeit r=L(K.gen()^2)
10 loops, best of 3: 61.1 ms per loop
sage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)
10 loops, best of 3: 124 ms per loop
sage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)
10 loops, best of 3: 126 ms per loop

This branch:

sage: %timeit r=L(K.gen())
1000 loops, best of 3: 908 µs per loop
sage: %timeit r=L(K.gen()^2)
1000 loops, best of 3: 899 µs per loop
sage: sage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3)
1000 loops, best of 3: 1.03 ms per loop
sage: %timeit r=L(1000/1303673*zeta10^2-37472365478234/3456354634*zeta10^3+234678234782637842736426342/2374723423423874723*zeta10)

In particular, the new function seems to scale much much better.

archive/issue_comments_300827.json:

{
    "body": "<div id=\"comment:6\" align=\"right\">comment:6</div>\n\n@pjbruin I can confirm the speedup mentioned in [#20693 comment:14](https://github.com/sagemath/sage/issues/20693#comment:14). For example, I tried\n\n```\n%time N=Newforms(DirichletGroup(23).gen()^2,4, names='a')\n```\nwhich now (with #20749 applied) runs 34.5s on my machine and 50.4s with sage 7.1.\nHowever, 27.9s out of those 34.5s are now spent in the (new) `_nf_nfzk`, which still seems a lot.\n\nHowever, my old examples still crash, but differently (see [#20693 comment:15](https://github.com/sagemath/sage/issues/20693#comment:15))",
    "created_at": "2016-06-01T23:42:49Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300827",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:6

@pjbruin I can confirm the speedup mentioned in #20693 comment:14. For example, I tried

%time N=Newforms(DirichletGroup(23).gen()^2,4, names='a')

which now (with #20749 applied) runs 34.5s on my machine and 50.4s with sage 7.1. However, 27.9s out of those 34.5s are now spent in the (new) _nf_nfzk, which still seems a lot.

However, my old examples still crash, but differently (see #20693 comment:15)

archive/issue_comments_300828.json:

{
    "body": "<div id=\"comment:7\" align=\"right\">comment:7</div>\n\nReplying to [@sagetrac-ehlen](#comment%3A5):\n> I started to review your changes. So far I can confirm that this does what it's supposed to do (see some timings below) but there seem to be some negative side-effects on the creation of relative extension.\n> [...]\n> The call to `'_nf_nfzk'` is now the main contributor and creating the extension is almost 12 times slower.\n> @pjbruin: Do you think we can avoid slowing down the creation of extensions somehow?\n\nSee #20759; we can postpone the call to `_nf_nfzk`, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.",
    "created_at": "2016-06-02T11:06:45Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300828",
    "user": "https://github.com/pjbruin"
}
comment:7

Replying to @sagetrac-ehlen:

I started to review your changes. So far I can confirm that this does what it's supposed to do (see some timings below) but there seem to be some negative side-effects on the creation of relative extension. [...] The call to '_nf_nfzk' is now the main contributor and creating the extension is almost 12 times slower. @pjbruin: Do you think we can avoid slowing down the creation of extensions somehow?

See #20759; we can postpone the call to _nf_nfzk, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.

archive/issue_comments_300829.json:

{
    "body": "<div id=\"comment:8\" align=\"right\">comment:8</div>\n\nReplying to [@pjbruin](#comment%3A7):\n> See #20759; we can postpone the call to `_nf_nfzk`, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.\n\nOK, #20759 is a good idea and I really think that your changes are great. However, the time spend in `nf_nfzk` is really a lot of time when the degree of the extension increases (and maybe it depends on the absolute degree in fact?). When investigating the crashes in #20693, I found the following example, which causes problems and makes it very hard to initialize a relative extension which only took a few seconds in sage 7.1:\n\n```\nsage: K.<zeta22> = CyclotomicField(22)\nsage: x = polygen(K)\nsage: f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096\nL.<a> = K.extension(f)\n```\nFirst of all, this takes 3.569s in sage 7.1. In your branch, I get after quite a while (a few minutes):\n\n```\nPariError: the PARI stack overflows (current size: 2147483648; maximum size: 2147483648)\nYou can use pari.allocatemem() to change the stack size and try again\n```\nThen I did:\n\n```\nsage: pari.allocatemem(2*2147483648)\n```\nand now it works but takes **very** long: 525.961s!\n\nOf course, working with elements in the extension became now more manageable:\nIn sage 7.1, we get \n\n```\nsage: %time r=L(K.gen())\nCPU times: user 7.68 ms, sys: 84 \u00b5s, total: 7.77 ms\nWall time: 7.77 ms\nsage: %time r=L(K.gen()^2)\nCPU times: user 3.97 s, sys: 1.56 ms, total: 3.97 s\nWall time: 3.97 s\nsage: %time r=L(K.gen()^3)\nCPU times: user 7.96 s, sys: 8.36 ms, total: 7.96 s\nWall time: 7.97 s\n```\nand in your branch\n\n```\nsage: %time r=L(K.gen())\nCPU times: user 19 ms, sys: 97 \u00b5s, total: 19.1 ms\nWall time: 19.1 ms\nsage: %time r=L(K.gen()^2)\nCPU times: user 19.1 ms, sys: 505 \u00b5s, total: 19.6 ms\nWall time: 19.6 ms\nsage: %time r=L(K.gen()^3)\nCPU times: user 19.1 ms, sys: 34 \u00b5s, total: 19.1 ms\nWall time: 19.1 ms\n```\n\nHowever, even if _nf_nfzk would be called later, waiting almost 9 minutes for a degree 9 extension seems ridiculously long.\nDon't we have any chance to improve this? Or is this a known issue in pari?\nAlso, the stack overflow should somehow be taken care of, don't you think?",
    "created_at": "2016-06-02T17:39:11Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300829",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:8

Replying to @pjbruin:

See #20759; we can postpone the call to _nf_nfzk, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.

OK, #20759 is a good idea and I really think that your changes are great. However, the time spend in nf_nfzk is really a lot of time when the degree of the extension increases (and maybe it depends on the absolute degree in fact?). When investigating the crashes in #20693, I found the following example, which causes problems and makes it very hard to initialize a relative extension which only took a few seconds in sage 7.1:

sage: K.<zeta22> = CyclotomicField(22)
sage: x = polygen(K)
sage: f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096
L.<a> = K.extension(f)

First of all, this takes 3.569s in sage 7.1. In your branch, I get after quite a while (a few minutes):

PariError: the PARI stack overflows (current size: 2147483648; maximum size: 2147483648)
You can use pari.allocatemem() to change the stack size and try again

Then I did:

sage: pari.allocatemem(2*2147483648)

and now it works but takes very long: 525.961s!

Of course, working with elements in the extension became now more manageable: In sage 7.1, we get

sage: %time r=L(K.gen())
CPU times: user 7.68 ms, sys: 84 µs, total: 7.77 ms
Wall time: 7.77 ms
sage: %time r=L(K.gen()^2)
CPU times: user 3.97 s, sys: 1.56 ms, total: 3.97 s
Wall time: 3.97 s
sage: %time r=L(K.gen()^3)
CPU times: user 7.96 s, sys: 8.36 ms, total: 7.96 s
Wall time: 7.97 s

and in your branch

sage: %time r=L(K.gen())
CPU times: user 19 ms, sys: 97 µs, total: 19.1 ms
Wall time: 19.1 ms
sage: %time r=L(K.gen()^2)
CPU times: user 19.1 ms, sys: 505 µs, total: 19.6 ms
Wall time: 19.6 ms
sage: %time r=L(K.gen()^3)
CPU times: user 19.1 ms, sys: 34 µs, total: 19.1 ms
Wall time: 19.1 ms

However, even if _nf_nfzk would be called later, waiting almost 9 minutes for a degree 9 extension seems ridiculously long. Don't we have any chance to improve this? Or is this a known issue in pari? Also, the stack overflow should somehow be taken care of, don't you think?

archive/issue_comments_300830.json:

{
    "body": "<div id=\"comment:9\" align=\"right\">comment:9</div>\n\n@pjbruin: I don't think this is really related to this issue but now I think I also know where the crashes in #20693 come from. Should I open a new issue for this? \n\nYou can get such a crash by taking the example extension from above and then do the following:\nFirst, before I come to the crash, I observed that the new fast coercion seems not to be used when doing arithmetic between elements of K and L (which should also be changed, I guess; create a new issue for this one as well?):\n\n```\nsage: a*zeta22\n```\ntakes **extremely long** (*better do not even try in this case*).\n\nSo to make the example work faster for you, redefine\n\n```\nsage: zeta22 = L(zeta22)\n```\nand then define\n\n```\nalpha = a^8 + (zeta22^9 - zeta22^6 + 2*zeta22^4 + 33)*a^7 + (31*zeta22^9 + 5*zeta22^8 + 3*zeta22^7 - 31*zeta22^6 - 7*zeta22^5 - 107*zeta22^4 - 7*zeta22^3 + 3*zeta22 + 1059)*a^6 + (3718477411250739866475244208396740244825243240462255398354618777962943033036197614/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 3598993609760370116641649296594108177793336273748205490894264408969198182996064521/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 395515835682657053939335812620537182933299146301044684946734967822987328729996770/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 5699790756786591231234352859639368530535500068686650515294130239974834139089497358/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 + 17297425796252247996017656901940747274345176460026298001221868953832184120342480943/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 17363940052556552019695963211248247355519164620582388569507136704698531302369871157/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 9055968516979184171371181551238371584025794515050844857388673892514573091513003290/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 - 15040340959361706541983637521956854375291195448848214782596844503078269125044340553/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 13494420365662811437124466100462970251959171531481521859055299974063740995251772104/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 6244717344446638271677235756972000388998153179319783794204333931828857707898855052/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^5 + (24774162552917688991082130433488385130328970002935037716015871420013133094788422714/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 79701067568676386611303145273440634808611524849495231394520039468820732638249105800/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 26568513472358696621594478167874503122978010463520328704511609604190048290318514603/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 28568346637705610185287947280980997136503568011444674263014607088110550373126222488/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 39660083727109323104443457044447414454536437867616101135848188026853956400960143227/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 288506345895399617687343175266113244576300715440934060776626556355537479220650636513/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 38450957705712699986746557845614915958961186767731353680661029680265167338816527393/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 38161688129027694214992610734600208295189825414215200641609022074230122499922603243/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 - 3191864810403360155650302997604973159366655983340669817286554187937615451268927032/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 47268626458303985980800073875915577424848984965812742485263892593814963540801229150/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^4 + (-937447078652953135161383442869885011608291132795403699637090980208045121301540757748/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 272895307598582523796743023683576558488087237572381251733653044903614546805704144822/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 148506657503867941152708044033955240703030804163414655018707004956684533483632072918/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 + 646234624710987986053419640141072406503297749358550789304127974747562199499646227564/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 694272767541738866807839896263173246303852233808156712638352151624760444919113413860/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 1065299910777172022253542660462029758918982943208973495529175167293206823402147443812/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 391247849932185372287013557796317033044190817278386930053256314276905903054599189656/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 270059737316677284054399797548542667378719651731770017638820261901537292210067430748/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 591183517951447041155684848874114741342258899601346549805513412737310300574376961340/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 549234386608334176655451066867005934918413936339648030381729208533527232309970754056/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^3 + (3733235692687094353448458915585909509665568180903028164992065763187227802783744366904/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 4001347101119302151586151100739784824512031744955125627753398604635977129245394082832/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 - 142900644218466289026802027389705486824676154666291235714274875202387049736546165496/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 3140367895112856999469516716889439921902711871458169096781024472877378499868645823464/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 + 1548125833062460723167432489350030748656270798599409078100770397214546377977628099392/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 5555248030204437606615955525547629664582214941617163155200679415001104250314686522904/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 2338634196530591481118837933605692971586210932289146141551391636565007362205462863632/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 241065823923473040670468508360923657066538144858067456312163992742504206316110953872/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 6193407042558447035765092497698058804377114439287850914206888660193032121912761915096/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 1099028159132223312122416248212282152380303533702464885003475741154651056010685127136/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^2 + (-1209474666091626439377287726025063910117768646668537490462602863066374919777158248752/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 18944377470648440226769591793624192288159925134705324925823731276407685992338482780768/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 - 12588022720980067567643175141996157130390089862067396848827764390446478609186744912864/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 + 5846397169289048287227403463558979527530805847195272367028420342204317428915118171264/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 16847241179656718059040202917295887078972805888663869818562994452056221728436316027648/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 + 12240286913403964318669326586717222877251387677609611349774686872857040618201006536992/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 - 10215645290860597645527053926413672307107960240749347167007546911366807686239483447760/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 - 1530790653293321897505424092212210389606218038145729553761965669588546770845494535744/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 - 2187147240620525406889619995238280606256936931802838455843775292305350828383843100392/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 19510253615883608973256727849462398241279239407108793464341426177684581140048029643336/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a + 16154018655709961475718369484349656491553141143207492785674435352956514805968259987664/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 2076605038062774454571095952791235830842349738387639911582630151888232765540495947312/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 4668807939004183895066836782642087347512184354134486123598161763233386792193417033072/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 23695032293352934150131791676770088928820644994522373184920557704305964271233795745200/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 30793593484010229493726633495079211970606615963726974062428759270109321834429025890192/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 15901465043256147712498413364161573071835390049680548208343611460784472680510813931552/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 30488481430481719467683640329190646090432003826988727071840796540695621523220516840016/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 30479060480952146242812422067193694873717833966949171930549636681404792808019569151264/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 28427288188474291222913119784939698904170993004067585847681058620275056131415057040896/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 15841459674454996185174537876570344446791982788066217107011655814278705184784915491008/2781215150144642133290297862665034354958449250072837417478217578695339824339427\n```\nNow try to invert alpha:\n\n```\nbeta = ~alpha\n```\nI get a crash after a few seconds.\n\nYes, I know, this example is somewhat huge and it probably shows that the modular forms should somehow reduce the coefficients of the polynomials of possible first etc. but anyway... I still think this should be mentioned.",
    "created_at": "2016-06-02T18:37:08Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300830",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:9

@pjbruin: I don't think this is really related to this issue but now I think I also know where the crashes in #20693 come from. Should I open a new issue for this?

You can get such a crash by taking the example extension from above and then do the following: First, before I come to the crash, I observed that the new fast coercion seems not to be used when doing arithmetic between elements of K and L (which should also be changed, I guess; create a new issue for this one as well?):

sage: a*zeta22

takes extremely long (better do not even try in this case).

So to make the example work faster for you, redefine

sage: zeta22 = L(zeta22)

and then define

alpha = a^8 + (zeta22^9 - zeta22^6 + 2*zeta22^4 + 33)*a^7 + (31*zeta22^9 + 5*zeta22^8 + 3*zeta22^7 - 31*zeta22^6 - 7*zeta22^5 - 107*zeta22^4 - 7*zeta22^3 + 3*zeta22 + 1059)*a^6 + (3718477411250739866475244208396740244825243240462255398354618777962943033036197614/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 3598993609760370116641649296594108177793336273748205490894264408969198182996064521/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 395515835682657053939335812620537182933299146301044684946734967822987328729996770/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 5699790756786591231234352859639368530535500068686650515294130239974834139089497358/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 + 17297425796252247996017656901940747274345176460026298001221868953832184120342480943/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 17363940052556552019695963211248247355519164620582388569507136704698531302369871157/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 9055968516979184171371181551238371584025794515050844857388673892514573091513003290/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 - 15040340959361706541983637521956854375291195448848214782596844503078269125044340553/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 13494420365662811437124466100462970251959171531481521859055299974063740995251772104/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 6244717344446638271677235756972000388998153179319783794204333931828857707898855052/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^5 + (24774162552917688991082130433488385130328970002935037716015871420013133094788422714/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 79701067568676386611303145273440634808611524849495231394520039468820732638249105800/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 26568513472358696621594478167874503122978010463520328704511609604190048290318514603/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 28568346637705610185287947280980997136503568011444674263014607088110550373126222488/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 39660083727109323104443457044447414454536437867616101135848188026853956400960143227/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 288506345895399617687343175266113244576300715440934060776626556355537479220650636513/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 38450957705712699986746557845614915958961186767731353680661029680265167338816527393/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 38161688129027694214992610734600208295189825414215200641609022074230122499922603243/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 - 3191864810403360155650302997604973159366655983340669817286554187937615451268927032/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 47268626458303985980800073875915577424848984965812742485263892593814963540801229150/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^4 + (-937447078652953135161383442869885011608291132795403699637090980208045121301540757748/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 272895307598582523796743023683576558488087237572381251733653044903614546805704144822/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 148506657503867941152708044033955240703030804163414655018707004956684533483632072918/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 + 646234624710987986053419640141072406503297749358550789304127974747562199499646227564/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 694272767541738866807839896263173246303852233808156712638352151624760444919113413860/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 1065299910777172022253542660462029758918982943208973495529175167293206823402147443812/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 391247849932185372287013557796317033044190817278386930053256314276905903054599189656/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 270059737316677284054399797548542667378719651731770017638820261901537292210067430748/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 591183517951447041155684848874114741342258899601346549805513412737310300574376961340/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 549234386608334176655451066867005934918413936339648030381729208533527232309970754056/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^3 + (3733235692687094353448458915585909509665568180903028164992065763187227802783744366904/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 4001347101119302151586151100739784824512031744955125627753398604635977129245394082832/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 - 142900644218466289026802027389705486824676154666291235714274875202387049736546165496/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 3140367895112856999469516716889439921902711871458169096781024472877378499868645823464/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 + 1548125833062460723167432489350030748656270798599409078100770397214546377977628099392/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 5555248030204437606615955525547629664582214941617163155200679415001104250314686522904/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 2338634196530591481118837933605692971586210932289146141551391636565007362205462863632/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 241065823923473040670468508360923657066538144858067456312163992742504206316110953872/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 6193407042558447035765092497698058804377114439287850914206888660193032121912761915096/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 1099028159132223312122416248212282152380303533702464885003475741154651056010685127136/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a^2 + (-1209474666091626439377287726025063910117768646668537490462602863066374919777158248752/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 18944377470648440226769591793624192288159925134705324925823731276407685992338482780768/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 - 12588022720980067567643175141996157130390089862067396848827764390446478609186744912864/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 + 5846397169289048287227403463558979527530805847195272367028420342204317428915118171264/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 16847241179656718059040202917295887078972805888663869818562994452056221728436316027648/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 + 12240286913403964318669326586717222877251387677609611349774686872857040618201006536992/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 - 10215645290860597645527053926413672307107960240749347167007546911366807686239483447760/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 - 1530790653293321897505424092212210389606218038145729553761965669588546770845494535744/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 - 2187147240620525406889619995238280606256936931802838455843775292305350828383843100392/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 + 19510253615883608973256727849462398241279239407108793464341426177684581140048029643336/2781215150144642133290297862665034354958449250072837417478217578695339824339427)*a + 16154018655709961475718369484349656491553141143207492785674435352956514805968259987664/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^9 + 2076605038062774454571095952791235830842349738387639911582630151888232765540495947312/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^8 + 4668807939004183895066836782642087347512184354134486123598161763233386792193417033072/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^7 - 23695032293352934150131791676770088928820644994522373184920557704305964271233795745200/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^6 - 30793593484010229493726633495079211970606615963726974062428759270109321834429025890192/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^5 - 15901465043256147712498413364161573071835390049680548208343611460784472680510813931552/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^4 + 30488481430481719467683640329190646090432003826988727071840796540695621523220516840016/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^3 + 30479060480952146242812422067193694873717833966949171930549636681404792808019569151264/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22^2 + 28427288188474291222913119784939698904170993004067585847681058620275056131415057040896/2781215150144642133290297862665034354958449250072837417478217578695339824339427*zeta22 - 15841459674454996185174537876570344446791982788066217107011655814278705184784915491008/2781215150144642133290297862665034354958449250072837417478217578695339824339427

Now try to invert alpha:

beta = ~alpha

I get a crash after a few seconds.

Yes, I know, this example is somewhat huge and it probably shows that the modular forms should somehow reduce the coefficients of the polynomials of possible first etc. but anyway... I still think this should be mentioned.

archive/issue_comments_300831.json:

{
    "body": "<div id=\"comment:10\" align=\"right\">comment:10</div>\n\nReplying to [@sagetrac-ehlen](#comment%3A8):\n> Replying to [@pjbruin](#comment%3A7):\n> > See #20759; we can postpone the call to `_nf_nfzk`, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.\n> \n> \n> OK, #20759 is a good idea and I really think that your changes are great. However, the time spend in `nf_nfzk` is really a lot of time when the degree of the extension increases (and maybe it depends on the absolute degree in fact?).\n\nHmm, I agree that this is a lot of time.  What `_nf_nfzk` does is computing the images of a **Q**-basis of the base field *K* under the inclusion map into the relative field (so mapping any element is reduced to linear algebra).  This means that `_nf_nfzk` should roughly perform [*K*:**Q**] \"slow\" applications of this inclusion map; it is currently much more.  I am now trying to profile the computation directly in PARI.",
    "created_at": "2016-06-03T11:21:22Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300831",
    "user": "https://github.com/pjbruin"
}
comment:10

Replying to @sagetrac-ehlen:

Replying to @pjbruin:

See #20759; we can postpone the call to _nf_nfzk, but we should do it at the latest when first mapping an element of the base field into the relative field, since there is no way to predict how often this is going to be done.

OK, #20759 is a good idea and I really think that your changes are great. However, the time spend in nf_nfzk is really a lot of time when the degree of the extension increases (and maybe it depends on the absolute degree in fact?).

Hmm, I agree that this is a lot of time. What _nf_nfzk does is computing the images of a Q-basis of the base field K under the inclusion map into the relative field (so mapping any element is reduced to linear algebra). This means that _nf_nfzk should roughly perform [K:Q] "slow" applications of this inclusion map; it is currently much more. I am now trying to profile the computation directly in PARI.

archive/issue_comments_300832.json:

{
    "body": "<div id=\"comment:11\" align=\"right\">comment:11</div>\n\nReplying to [@pjbruin](#comment%3A10):\n> What `_nf_nfzk` does is computing the images of a **Q**-basis of the base field *K* under the inclusion map into the relative field (so mapping any element is reduced to linear algebra).  This means that `_nf_nfzk` should roughly perform [*K*:**Q**] \"slow\" applications of this inclusion map; it is currently much more.  I am now trying to profile the computation directly in PARI.\n\nIndeed, it turns out that the PARI function `nf_nfzk` performs too much work.  I will report this to the PARI developers together with a proposed solution.",
    "created_at": "2016-06-04T18:55:02Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300832",
    "user": "https://github.com/pjbruin"
}
comment:11

Replying to @pjbruin:

What _nf_nfzk does is computing the images of a Q-basis of the base field K under the inclusion map into the relative field (so mapping any element is reduced to linear algebra). This means that _nf_nfzk should roughly perform [K:Q] "slow" applications of this inclusion map; it is currently much more. I am now trying to profile the computation directly in PARI.

Indeed, it turns out that the PARI function nf_nfzk performs too much work. I will report this to the PARI developers together with a proposed solution.

archive/issue_comments_300833.json:

{
    "body": "<div id=\"comment:12\" align=\"right\">comment:12</div>\n\nReplying to [@pjbruin](#comment%3A11):\n> Indeed, it turns out that the PARI function `nf_nfzk` performs too much work.  I will report this to the PARI developers together with a proposed solution.\n\nThis has meanwhile been fixed in PARI; see the [upstream bug report](http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=1822) and upstream commit 6db8fba.",
    "created_at": "2016-06-07T16:09:48Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300833",
    "user": "https://github.com/pjbruin"
}
comment:12

Replying to @pjbruin:

Indeed, it turns out that the PARI function nf_nfzk performs too much work. I will report this to the PARI developers together with a proposed solution.

This has meanwhile been fixed in PARI; see the upstream bug report and upstream commit 6db8fba.

archive/issue_comments_300834.json:

{
    "body": "<div id=\"comment:13\" align=\"right\">comment:13</div>\n\nThe only remaining problem (after applying #20759 [non-essential], this branch and the above PARI patch) seems to be that the following is still too slow:\n\n```\nsage: K.<zeta22> = CyclotomicField(22)\nsage: x = polygen(K)\nsage: f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096\nsage: L.<a> = K.extension(f)\nsage: %prun a*zeta22\n```\nApparently several push-outs of number fields are constructed, which are apparently different from `L` (most of the time is spent in two calls to the PARI function `nf_rnfeq`).  This is probably a separate issue from this ticket.",
    "created_at": "2016-06-08T15:38:55Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300834",
    "user": "https://github.com/pjbruin"
}
comment:13

The only remaining problem (after applying #20759 [non-essential], this branch and the above PARI patch) seems to be that the following is still too slow:

sage: K.<zeta22> = CyclotomicField(22)
sage: x = polygen(K)
sage: f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096
sage: L.<a> = K.extension(f)
sage: %prun a*zeta22

Apparently several push-outs of number fields are constructed, which are apparently different from L (most of the time is spent in two calls to the PARI function nf_rnfeq). This is probably a separate issue from this ticket.

archive/issue_comments_300835.json:

{
    "body": "<div id=\"comment:14\" align=\"right\">comment:14</div>\n\nThe problem in [comment:13](#comment%3A13) should be solved by #20791.",
    "created_at": "2016-06-09T07:04:32Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300835",
    "user": "https://github.com/pjbruin"
}
comment:14

The problem in comment:13 should be solved by #20791.

archive/issue_comments_300836.json:

{
    "body": "<div id=\"comment:15\"></div>\n\nBranch pushed to git repo; I updated commit sha1. New commits:\n<table><tr><td><a href=\"https://github.com/sagemath/sagetrac-mirror/commit/2cb5c94937b32696f607d6cc901b34dabd1e33a8\"><code>2cb5c94</code></a></td><td><code>Trac 20749: add PARI patch to speed up nf_nfzk</code></td></tr></table>\n",
    "created_at": "2016-06-09T07:39:58Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300836",
    "user": "https://github.com/sagetrac-git"
}

Branch pushed to git repo; I updated commit sha1. New commits:

2cb5c94Trac 20749: add PARI patch to speed up nf_nfzk

archive/issue_comments_300837.json:

{
    "body": "Changed commit from **[`9f1d90b`](https://github.com/sagemath/sagetrac-mirror/commit/9f1d90be8d3f05b6d5de8ee75e36e6d17ad52095)** to **[`2cb5c94`](https://github.com/sagemath/sagetrac-mirror/commit/2cb5c94937b32696f607d6cc901b34dabd1e33a8)**",
    "created_at": "2016-06-09T07:39:58Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300837",
    "user": "https://github.com/sagetrac-git"
}

Changed commit from 9f1d90b to 2cb5c94

archive/issue_comments_300838.json:

{
    "body": "<div id=\"comment:16\" align=\"right\">comment:16</div>\n\nAfter applying this ticket together with #20759 and #20791, I get (on a not so very fast system):\n\n```\nsage: K.<zeta22> = CyclotomicField(22)\nsage: x = polygen(K)\nsage: f = f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096\nsage: %time L.<a> = K.extension(f)\nCPU times: user 6.51 s, sys: 4 ms, total: 6.52 s\nWall time: 6.52 s\nsage: %time a*zeta22\nCPU times: user 2.79 s, sys: 32 ms, total: 2.82 s\nWall time: 2.82 s\nzeta22*a\nsage: %time a*zeta22\nCPU times: user 36 ms, sys: 0 ns, total: 36 ms\nWall time: 33.8 ms\nzeta22*a\n```\nPractically all the time for creating the extension is spent in the PARI function `nf_rnfeq`.  For the first multiplication, practically all the time is spent in the PARI function `nf_nfzk`; subsequent computations are much faster.  Note also that *printing* the result of `a*zeta22` takes a long time; this is due to the conversion from absolute to relative representation (the PARI function `eltabstorel_lift`).",
    "created_at": "2016-06-09T07:59:43Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300838",
    "user": "https://github.com/pjbruin"
}
comment:16

After applying this ticket together with #20759 and #20791, I get (on a not so very fast system):

sage: K.<zeta22> = CyclotomicField(22)
sage: x = polygen(K)
sage: f = f = x^9 + (zeta22^9 - zeta22^6 + zeta22^4 + 1)*x^8 + (2*zeta22^8 + 4*zeta22^7 - 6*zeta22^5 - 205*zeta22^4 - 6*zeta22^3 + 4*zeta22 + 2)*x^7 + (181*zeta22^9 - 354*zeta22^8 + 145*zeta22^7 - 253*zeta22^6 + 145*zeta22^5 - 354*zeta22^4 + 181*zeta22^3 + 189*zeta22 - 189)*x^6 + (902*zeta22^9 + 13116*zeta22^8 + 902*zeta22^7 - 500*zeta22^5 - 322*zeta22^4 - 176*zeta22^3 + 176*zeta22^2 + 322*zeta22 + 500)*x^5 + (13196*zeta22^9 + 548*zeta22^8 + 9176*zeta22^7 - 17964*zeta22^6 + 8512*zeta22^5 - 8512*zeta22^4 + 17964*zeta22^3 - 9176*zeta22^2 - 548*zeta22 - 13196)*x^4 + (17104*zeta22^9 + 23456*zeta22^8 + 8496*zeta22^7 - 8496*zeta22^6 - 23456*zeta22^5 - 17104*zeta22^4 + 39680*zeta22^2 + 283184*zeta22 + 39680)*x^3 + (118736*zeta22^9 - 118736*zeta22^8 - 93520*zeta22^6 + 225600*zeta22^5 + 66496*zeta22^4 + 373744*zeta22^3 + 66496*zeta22^2 + 225600*zeta22 - 93520)*x^2 + (342176*zeta22^9 + 388928*zeta22^8 + 4800*zeta22^7 - 234464*zeta22^6 - 1601152*zeta22^5 - 234464*zeta22^4 + 4800*zeta22^3 + 388928*zeta22^2 + 342176*zeta22)*x + 431552*zeta22^9 - 1830400*zeta22^8 - 1196800*zeta22^7 - 1830400*zeta22^6 + 431552*zeta22^5 + 1196096*zeta22^3 - 12672*zeta22^2 + 12672*zeta22 - 1196096
sage: %time L.<a> = K.extension(f)
CPU times: user 6.51 s, sys: 4 ms, total: 6.52 s
Wall time: 6.52 s
sage: %time a*zeta22
CPU times: user 2.79 s, sys: 32 ms, total: 2.82 s
Wall time: 2.82 s
zeta22*a
sage: %time a*zeta22
CPU times: user 36 ms, sys: 0 ns, total: 36 ms
Wall time: 33.8 ms
zeta22*a

Practically all the time for creating the extension is spent in the PARI function nf_rnfeq. For the first multiplication, practically all the time is spent in the PARI function nf_nfzk; subsequent computations are much faster. Note also that printing the result of a*zeta22 takes a long time; this is due to the conversion from absolute to relative representation (the PARI function eltabstorel_lift).

archive/issue_comments_300839.json:

{
    "body": "<div id=\"comment:17\" align=\"right\">comment:17</div>\n\nI think this should be merged now. I tested the latest version with the patch and it works like a charm.\nThe crash observed in [comment:9](#comment%3A9) is the same as in #20693, so we don't need a new ticket for now.",
    "created_at": "2016-06-10T18:38:41Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300839",
    "user": "https://github.com/sagetrac-ehlen"
}
comment:17

I think this should be merged now. I tested the latest version with the patch and it works like a charm. The crash observed in comment:9 is the same as in #20693, so we don't need a new ticket for now.

archive/issue_events_289580.json:

{
    "actor": "https://github.com/sagetrac-ehlen",
    "created_at": "2016-06-10T18:38:41Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/needs%20review",
    "label_color": "7fff00",
    "label_name": "needs review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289580"
}

archive/issue_events_289581.json:

{
    "actor": "https://github.com/sagetrac-ehlen",
    "created_at": "2016-06-10T18:38:41Z",
    "event": "labeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/positive%20review",
    "label_color": "dfffc0",
    "label_name": "positive review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289581"
}

archive/issue_comments_300840.json:

{
    "body": "Changed branch from **[u/pbruin/20749-pari_nfeltup](https://github.com/sagemath/sagetrac-mirror/tree/u/pbruin/20749-pari_nfeltup)** to **[`2cb5c94`](https://github.com/sagemath/sagetrac-mirror/commit/2cb5c94937b32696f607d6cc901b34dabd1e33a8)**",
    "created_at": "2016-06-11T22:28:19Z",
    "formatter": "markdown",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_comment",
    "url": "https://github.com/sagemath/sage/issues/20749#issuecomment-300840",
    "user": "https://github.com/vbraun"
}

Changed branch from u/pbruin/20749-pari_nfeltup to 2cb5c94

archive/issue_events_289582.json:

{
    "actor": "https://github.com/vbraun",
    "created_at": "2016-06-11T22:28:19Z",
    "event": "unlabeled",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "label": "https://github.com/sagemath/sage/labels/positive%20review",
    "label_color": "dfffc0",
    "label_name": "positive review",
    "label_text_color": "ffffff",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289582"
}

archive/issue_events_289583.json:

{
    "actor": "https://github.com/vbraun",
    "commit_id": "8cd2d98b7ab559ab8b16c21c7eb59722754aa1cb",
    "commit_repository": "https://github.com/sagemath/sage",
    "created_at": "2016-06-11T22:28:19Z",
    "event": "closed",
    "issue": "https://github.com/sagemath/sage/issues/20749",
    "type": "issue_event",
    "url": "https://github.com/sagemath/sage/issues/20749#event-289583"
}