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:

Status badges


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 Xavier Caruso

In order to illustrate my point, I post a code (written in pure python) which is a little bit faster than the current implementation:

def my_expansion(elt):
    if elt.valuation() != 0:
        raise NotImplementedError
    parent = elt.parent()
    e = parent.absolute_e()
    prec = elt.precision_absolute()
    curprec = 0
    pie = parent.uniformizer_pow(e)
    expansion = [ ]
    while curprec < prec:
        poly = elt._poly_rep()
        expansion += [ poly[i].residue() for i in range(min(e,prec-curprec)) ]
        elt //= pie
        curprec += e
    return expansion

comment:2 Changed 3 years ago by David Roe

Keywords: padicBordeaux added

comment:3 Changed 3 years ago by David Roe

Branch: u/roed/26105_base_hom

comment:4 Changed 3 years ago by David Roe

Branch: u/roed/26105_base_hom

Mistaken push from wrong ticket.

Note: See TracTickets for help on using tickets.