Opened 4 years ago
Last modified 3 years ago
#26015 new task
Accelerate expansion for padics in mixed extensions
Reported by: | Xavier Caruso | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-8.4 |
Component: | padics | Keywords: | padicBordeaux |
Cc: | David Roe, Julian Rüth | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #23218 | Stopgaps: |
Description
Currently the method expansion
is very slow for mixed extensions with a large absolute index of ramification.
sage: K.<a> = Qq(3^3,10) sage: S.<x> = K[] sage: Z = (1+x)^27 sage: L.<pi> = K.extension(Z^2 + Z + 1) sage: elt = L.random_element() sage: %time _ = list(elt.expansion()) CPU times: user 2.86 s, sys: 4 ms, total: 2.87 s Wall time: 2.87 s
I had a look at the code and it turns out that the current implementation performs prec
(the relative precision) shifts by -1
. I think that it would be possible to shift only prec/e
times by -e
(where e
is the absolute index of ramification) and then roughly save a factor e
in the complexity.
Change History (4)
comment:1 Changed 4 years ago by
comment:2 Changed 3 years ago by
Keywords: | padicBordeaux added |
---|
comment:3 Changed 3 years ago by
Branch: | → u/roed/26105_base_hom |
---|
Note: See
TracTickets for help on using
tickets.
In order to illustrate my point, I post a code (written in pure python) which is a little bit faster than the current implementation: