Opened 8 years ago
Last modified 4 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 )
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
- Milestone set to sage-4.6.2
- Type changed from PLEASE CHANGE to enhancement
comment:2 Changed 8 years ago by
- Description modified (diff)
comment:3 Changed 8 years ago by
- Component changed from PLEASE CHANGE to basic arithmetic
- Description modified (diff)
- Owner changed from tbd to AlexGhitza
comment:4 Changed 6 years ago by
- Milestone changed from sage-5.11 to sage-5.12
comment:5 Changed 5 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:6 Changed 5 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:7 Changed 5 years ago by
- Milestone changed from sage-6.3 to sage-6.4
comment:8 Changed 4 years ago by
- Cc wbhart mmarco added
Note: See
TracTickets for help on using
tickets.
Flint should have suppport for this through Antic, right?