#10591: Implement univariate polynomial rings over absolute number fields
--------------------------------+-------------------------------------------
Reporter: lftabera | Owner: AlexGhitza
Type: enhancement | Status: new
Priority: major | Milestone: sage-4.6.2
Component: basic arithmetic | Keywords: number fields, polynomials,
performance
Author: | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
--------------------------------+-------------------------------------------
Changes (by lftabera):
* owner: tbd => AlexGhitza
* component: PLEASE CHANGE => basic arithmetic
Old description:
> 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
New description:
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
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10591#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
