Opened 6 years ago

Closed 6 years ago

#20749 closed enhancement (fixed)

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

Reported by: Peter Bruin Owned by:
Priority: major Milestone: sage-7.3
Component: number fields Keywords: relative number field pari
Cc: Stephan Ehlen, Jeroen Demeyer Merged in:
Authors: Peter Bruin Reviewers: Stephan Ehlen
Report Upstream: N/A Work issues:
Branch: 2cb5c94 (Commits, GitHub, GitLab) Commit: 2cb5c94937b32696f607d6cc901b34dabd1e33a8
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (18)

comment:1 Changed 6 years ago by Peter Bruin

Branch: u/pbruin/20749-pari_nfeltup
Cc: Stephan Ehlen Jeroen Demeyer added
Commit: 9f1d90be8d3f05b6d5de8ee75e36e6d17ad52095
Keywords: relative number field added

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...

comment:2 Changed 6 years ago by Stephan Ehlen

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!

Last edited 6 years ago by Stephan Ehlen (previous) (diff)

comment:3 Changed 6 years ago by Peter Bruin

Status: newneeds_review

All doctests passed.

comment:4 Changed 6 years ago by Stephan Ehlen

Reviewers: Stephan Ehlen

comment:5 Changed 6 years ago by Stephan 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.

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. @pbruin: 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.

comment:6 Changed 6 years ago by Stephan Ehlen

@pbruin I can confirm the speedup mentioned in http://trac.sagemath.org/ticket/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 http://trac.sagemath.org/ticket/20693#comment:15)

comment:7 in reply to:  5 ; Changed 6 years ago by Peter Bruin

Replying to 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. @pbruin: 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.

comment:8 in reply to:  7 ; Changed 6 years ago by Stephan Ehlen

Replying to pbruin:

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?

comment:9 Changed 6 years ago by Stephan Ehlen

@pbruin: 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.

comment:10 in reply to:  8 ; Changed 6 years ago by Peter Bruin

Replying to ehlen:

Replying to pbruin:

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.

comment:11 in reply to:  10 ; Changed 6 years ago by Peter Bruin

Replying to pbruin:

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.

comment:12 in reply to:  11 Changed 6 years ago by Peter Bruin

Replying to pbruin:

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.

comment:13 Changed 6 years ago by Peter Bruin

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.

comment:14 Changed 6 years ago by Peter Bruin

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

comment:15 Changed 6 years ago by git

Commit: 9f1d90be8d3f05b6d5de8ee75e36e6d17ad520952cb5c94937b32696f607d6cc901b34dabd1e33a8

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

2cb5c94Trac 20749: add PARI patch to speed up nf_nfzk

comment:16 Changed 6 years ago by Peter Bruin

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).

comment:17 Changed 6 years ago by Stephan Ehlen

Status: needs_reviewpositive_review

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.

comment:18 Changed 6 years ago by Volker Braun

Branch: u/pbruin/20749-pari_nfeltup2cb5c94937b32696f607d6cc901b34dabd1e33a8
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.