Opened 8 years ago

Last modified 5 years ago

#10591 new enhancement

Implement univariate polynomial rings over absolute number fields

Reported by: lftabera Owned by: AlexGhitza
Priority: major Milestone: sage-6.4
Component: basic arithmetic Keywords: number fields, polynomials, performance
Cc: wbhart, mmarco Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by lftabera)

After some discussion with Sebastian Spancratz it can be interesting to add a specific implementation for univariate polynomials over number fields. This can improve a lot performance, at least for multiplication, addition and gcd.

One approach is to implement Nuberfield(f)[x] more likely QQ[x][y].quotient(f(y))

Note, with patch #10255

sage: K=QQ[x]['y']
sage: y=K.gen()
sage: L=K.quotient(y^16+y^5+y^4+y^3+y^2+y+1)
sage: f=L(K.random_element(16,1500))
sage: g=L(K.random_element(16,1500))
sage: P=NumberField(x^16+x^5+x^4+x^3+x^2+x+1,'a')[x]
sage: f1 = P.random_element(1500)
sage: g1 = P.random_element(1500)
sage: def nfpol_to_pari(f):
    return pari([c._pari_('a') for c in f.list()]).Polrev()
....: 
sage: fpari = nfpol_to_pari(f1)
sage: gpari = nfpol_to_pari(g1)
sage: %time _ = f*g
CPU times: user 1.92 s, sys: 0.00 s, total: 1.92 s
Wall time: 1.94 s
sage: %time _ = f1*g1
CPU times: user 20.29 s, sys: 0.04 s, total: 20.32 s
Wall time: 20.34 s
sage: %time _ = fpari*gpari
CPU times: user 66.50 s, sys: 0.02 s, total: 66.52 s
Wall time: 66.58 s
sage: %time _=f+g
CPU times: user 0.00 s, sys: 0.00 s, total: 0.00 s
Wall time: 0.01 s
sage: %time _=f1+g1
CPU times: user 0.02 s, sys: 0.00 s, total: 0.02 s
Wall time: 0.02 s
sage: %time _=fpari+gpari
CPU times: user 0.01 s, sys: 0.00 s, total: 0.01 s
Wall time: 0.01 s

Related tickets: #8558, #10255

Things to do (to be completed):

  • Faster multiplication
  • Fast modular gcd #8558
  • Avoid PARI nfinit to compute factorization
  • Try Newton-based quo_rem

Change History (8)

comment:1 Changed 8 years ago by lftabera

  • Milestone set to sage-4.6.2
  • Type changed from PLEASE CHANGE to enhancement

comment:2 Changed 8 years ago by lftabera

  • Description modified (diff)

comment:3 Changed 8 years ago by lftabera

  • Component changed from PLEASE CHANGE to basic arithmetic
  • Description modified (diff)
  • Owner changed from tbd to AlexGhitza

comment:4 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:8 Changed 5 years ago by mmarco

  • Cc wbhart mmarco added

Flint should have suppport for this through Antic, right?

Note: See TracTickets for help on using tickets.