Robert Pollack's profile - activity

I run the following code:

DB = CremonaDatabase()
for N in range(1,10000):
        Cs = DB.isogeny_classes(N)
        for C in Cs:
                E=EllipticCurve(C[0][0])
                phi=E.modular_symbol()

and the memory used keeps going up and up and up.

This must be related to the fact that the modular symbol data is cached. Is there a way I can clear out this memory usage? I want to be doing a computation with each such modular symbol and then just get rid of the modular symbol.

I'm looking at a cyclotomic field ${\bf Q}(\mu_{p(p-1)})$ for $p$ a prime around 50 and so this field has fairly large degree. In this field, $p$ has ramification index $p$ and has $p-1$ primes sitting above it.

I'm trying to compute the valuation of an element in this field at any of these primes above $p$. Using commands like "primes_above" won't seem to work as the computer just hangs presumably because this extensions degree is just too big.

Questions:

1) Is there another way to compute $p$-adic valuations in this field?

2) Locally, this is only a $p$-th degree extension of ${\bf Q}_p$. So I created a p-adic field by using pAdicField(p).ext(1+(x+1)+(x+1)^2+...+(x+1)^(p-1)) to create this local p-th degree extension of Q_p. However, I can't find any way to map my global elements in ${\bf Q}(\mu_{p(p-1)})$ to this local field. Any ideas on how to proceed along these lines?

I'm trying to do some operations with polynomials over $Z/p^nZ$ and I'm stuck on some basic things:

1) Is it possible in SAGE to long divide two polynomials in $Z/p^nZ[x]$?

2) Is it possible in SAGE to factor a polynomial in $Z/p^nZ[x]$?

Am I missing something about the basic functionality of (1)? Is this really something that I need to program myself??

But I want to be working in Z/9Z -- not over a finite field! I really want characteristic 9 not 3.

Has any kind of row reduction been implemented modulo prime powers? Right now I'm simply trying to write a particular element of (Z/9Z)^d as a linear combination of a handful of other elements in this space. (I happen to know for other reasons that the original element is in the span of these handful of elements.)

I tried to do this by working with matrices over pAdicField(3,2), but this didn't work. (I guess some division by 3 messes things up.)

Is there anyway to do this without writing my own row reduction code??

Robert -- this could be fixed so it works exactly like you want, but it requires writing some code in Cython, and pretty advanced knowledge of Sage internals. One potential workaround is to simply multiply over ZZ, then reduce the answer, e.g., do something like this:

sage: M = random_matrix(ZZ,100)
sage: v = random_matrix(ZZ,100,1)
sage: timeit('(M*v) % 11^3')
625 loops, best of 3: 631 µs per loop

which beats all the following by a lot:

sage: M = random_matrix(ZZ,100)
sage: v = random_vector(Integers(11^3),100)
sage: timeit('M*v')
125 loops, best of 3: 2.55 ms per loop

sage: M = random_matrix(ZZ,100)
sage: v = random_matrix(Integers(11^3),100,1)
sage: timeit('M*v')
125 loops, best of 3: 4.83 ms per loop

sage: M = random_matrix(ZZ,100)
sage: v = random_vector(ZZ,100)
sage: timeit('(M*v) % 11^3')
125 loops, best of 3: 4.42 ms per loop

Incidentally, "write code to compute with overconvergent modular symbols" is something Ben Lundell and I at UW have been wanting to do in the near future to. Maybe we can coordinate? Email us.

I'll give it a try! Thanks.

Thanks parzan. Unfortunately I need an exact computation. More precisely, I'm working modulo p^N where p^N is around 10^100. I'll edit my question accordingly. About supplying code, the computation really boils down to the one line M*v applied again and again where M is the large matrix, and v the vector.

I'm currently trying write code to compute with overconvergent modular symbols. In iterating a Hecke operator, the key (i.e. most time consuming) operation that is performed tons of times is simply taking the product of a large dense matrix say $M$ with a vector $v$, both with integral entries.

More precisely, let $p$ be a (relatively small) prime (think $p=11$) and $N$ some integer (think 100). I have an $N$ by $N$ matrix and am interested in quickly computing the product $M \cdot v$ modulo $p^N$.

I am simply using the intrinsic SAGE command of multiplying a matrix by a vector, and I was surprised to see that working with matrices over ${\bf Z}/p^n{\bf Z}$ was much (i.e. 10 times) slower than working with matrices over ${\bf Z}$.

My question: is there a faster way to do this computation than using SAGE's intrinsic matrix times a vector command over ${\bf Z}$?