zn_poly -- request for testing

[David Harvey]

Hi folks,

I've started working on a new C library called "zn_poly", which does
polynomial arithmetic in (Z/nZ)[x], where n fits into an unsigned
long. Similar to NTL's zz_pX class. This might eventually be part of
FLINT, but for now it's a separate project.

I am maintaining a website for zn_poly at

http://math.harvard.edu/~dmharvey/zn_poly/

I have made an spkg for sage-2.9, you can get it from

http://math.harvard.edu/~dmharvey/zn_poly/releases/zn_poly-0.4.1.spkg

I don't know if this will build on all sage-supported systems yet. So
far I have successfully built on:

* sage.math (AMD opteron, debian linux)
* bsd (a xeon I think?)
* my laptop: core 2 duo, mac OS 10.4.10
* my desktop: ppc G5, mac OS 10.4.10
* my very old laptop: ppc G3, mac OS 10.3.9 (zn_poly, but not the spkg)

I'd really appreciate people trying this out on various systems and
reporting back what happens.

As an application, I rewrote my "frobenius" program, which is
currently included in Sage via
sage.schemes.hyperelliptic_curves.frobenius.frobenius. This program
computes the characteristic polynomial of frobenius (i.e. the zeta
function) for a hyperelliptic curve over GF(p), where p is relatively
large.

Here is a patch which upgrades to the new version:

http://sage.math.washington.edu/home/dmharvey/patches/hypellfrob.hg

The algorithm depends heavily on polynomial arithmetic, often for a
small (word-sized) modulus. The old version used NTL for the
polynomial arithmetic (either ZZ_pX or zz_pX). The new version
attempts to use zn_poly arithmetic where possible. Below are some
example timings for the new version (on sage.math). It incorporates
some algorithmic improvements too, but a lot of the speedup is due to
zn_poly vs NTL.

genus 2
(compute charpoly mod p)

p = 2^16 + 1: old = 0.068s, new = 0.008s
p = 2^20 + 7: old = 0.288s, new = 0.044s
p = 2^24 + 43: old = 1.244s, new = 0.324s
p = 2^28 + 3: old = 5.63s, new = 2.952s
p = 2^32 + 15: old = 29.0s, new = 21.6s

genus 3
(compute charpoly mod p)

p = 2^16 + 1: old = 0.136s, new = 0.020s
p = 2^20 + 7: old = 0.580s, new = 0.092s
p = 2^24 + 43: old = 2.548s, new = 0.648s
p = 2^28 + 3: old = 11.4s, new = 5.9s
p = 2^32 + 15: old = 58.2s, new = 43.3s

genus 4
(compute charpoly mod p^2)

p = 2^16 + 1: old = 0.61s, new = 0.16s
p = 2^20 + 7: old = 5.23s, new = 0.92s
p = 2^24 + 43: old = 25.7s, new = 20.3s
p = 2^28 + 3: old = 233s, new = 111s
p = 2^32 + 15: old = 1246s, new = 1313s

Hmmmm.... that last one ain't so great. That's because zn_poly excels
at small-to-medium polynomials, but isn't so good for large
polynomials (yet!).

david

[mabshoff]

After some discussion in IRC I have added zn_poly-0.4.1.spkg to the
experimental spkg repo. You should be able to install it via

./sage -i zn_poly-0.4.1

now.

Cheers,

Michael

[mabshoff]

And a build report from Solaris/Sparc with Sage 2.8.14:

gcc -fPIC -O3 -o tune tune_main.o mul_ks-tune.o mul_ks-profile.o
profiler.o support.o zn_mod.o misc.o mul_ks.o pack.o mul.o tuning.o -
L"/tmp/Work-mabshoff/sage-2.8.14/local//lib" -L"/tmp/Work-mabshoff/
sage-2.8.14/local//lib" -lgmp -lm
./tune > tuning.c

Warning: no cycle counting code available on this system,
using default tuning values.

Wrote tuning data to tuning.c. Run make to rebuild library
gcc -fPIC -O3 -I"/tmp/Work-mabshoff/sage-2.8.14/local//include" -I"/
tmp/Work-mabshoff/sage-2.8.14/local//include" -DNDEBUG -o tuning.o -c
tuning.c
gcc -shared -o libzn_poly.so zn_mod.o misc.o mul_ks.o pack.o mul.o
tuning.o -L"/tmp/Work-mabshoff/sage-2.8.14/local//lib" -L"/tmp/Work-
mabshoff/sage-2.8.14/local//lib" -lgmp -lm

real 0m4.186s
user 0m3.300s
sys 0m0.720s
Successfully installed zn_poly-0.4.1
Now cleaning up tmp files.
rm: cannot remove directory `/tmp/Work-mabshoff/sage-2.8.14/spkg/build/
zn_poly-0.4.1': Invalid argument
Making SAGE/Python scripts relocatable...
Making script relocatable

Cheers,

Michael