Re: dokchitser port
William Stein
On Thu, Nov 6, 2008 at 6:48 PM, Jennifer S. Balakrishnan
<j...@math.mit.edu> wrote:
> Hey William,
>
> Is there anything I could be doing for this?
I'm not sure *yet*.
> One theoretical question that we could work on: for evaluating
> functions at large numbers, Dokchitser writes an asymptotic
> approximation and converts the power series to a continued fraction.
> Mike Rubinstein seemed to suggest that getting error bounds would be
> very difficult with continued fractions. Do you know of other methods?
I think we should:
(1) Get a fast robust implementation in sage of Dokchitser's
algorithm, basically as is in GP. Make it faster than in GP,
and make it very well documented and tested. Make it be
nicely tied in with modular forms, Dirichlet characters, symmetric
powers, etc., like you partly did already. Code up applications
to computing things like Petersson norms. Compare this
to Dokchiter's 2000-line Magma implementation and make
ours solidly better than Magma and Pari:
* better documented
* more examples
* faster
* more flexible
(2) Dokchitser's paper basically sketches an algorithm for
provable computation of L-functions, where he says to just
use expansion about 0 in all cases, since it is easier to
bound the error. Obviously it's potentially a lot slower, but it
will be provably right. Work out the details and implement
this. Note that for all of *my* applications (to special values),
I'm interested in L(s) for *small* s -- Mike is in contrast interested
in large s probably.
(3) Worry about tricks to make (2) fast.
My impression is that neither (1) nor (2) is done, but that you
put a lot of work into (1).
By the way, Karim (Pari developer) is currently planning to
incorporate a "translated to C (via gp2c?)" version of Dokchitser
into
pari itself. But that could take months (or more).
William
> Jen
>
> On 10/27/08, William Stein <wst...@gmail.com> wrote:
>> Hi Robert B.,
>>
>> This is about Jennifer's Dokchitser code. Maybe it's time
>> to take the next step!
>>
>>
>>
>> ---------- Forwarded message ----------
>> From: Jennifer S. Balakrishnan <j...@math.mit.edu>
>> Date: Mon, Oct 27, 2008 at 4:18 PM
>> Subject: Re: dokchitser port
>> To: William Stein <wst...@gmail.com>
>> Cc: Sourav Sen Gupta <sg.s...@gmail.com>
>>
>>
>> Hi William and Sourav,
>>
>> Here's the version (closest to Dokchitser's original pari code) that
>> still uses continued fraction approximation:
>>
>> http://sage.math.washington.edu/home/jen/sage-3.0.5-x86_64-Linux/l4.py
>>
>> (needs gamma_series.py to run:
>> http://sage.math.washington.edu/home/jen/sage-3.0.5-x86_64-Linux/gamma_series.py)
>>
>> The version with Pade approximation (l5.py) has a negligible speedup
>> but only really works for low precision. I'm not sure if Pade gives us
>> a means of computing bounds (I think Mike Rubinstein said that
>> continued fractions won't). Also, l4.py doesn't work for imaginary
>> inputs yet - some coercion with SymbolicRing that I didn't try.
>>
>> Let me know if you have any ideas you'd like me to try.
>>
>> Best,
>> Jen
>>
>>
>>
>>
>> --
>> William Stein
>> Associate Professor of Mathematics
>> University of Washington
>> http://wstein.org
>>
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
William Stein
> Hi William ...
>
> I can definitely take a look at Problems (1) and (2) as you have mentioned
> ... Just to add, we must make Jen's code compatible with the complex numbers
> as well, removing the coercion problems ...
Making code that works is definitely part of (1). I'm glad you'll
also help out with this. I've posted a directory with all relevant
code here:
http://sage.math.washington.edu/home/was/tmp/dokchitser.tar.bz2
> Two more problems of interest to me at this point are as follows:
>
> (4) Running the code for Prof Greenberg (Tom helped me in getting a lot
> faster algorithm for that one) ... But we need to run it parallel ...
Cool. Too bad you're about to miss out on the parallel
tutorial in a few minutes, but people will help you tomorrow.
>
> (5) Look for a good comprehensive database for
> class_number(QuadraticField(\sqrt(d))) for large positive and negative d ...
> If there exists one, it will immensely help the code in (4) ... If not, we
> can consider creating one (Sloane has one, but limited ... Cohen had one,
> but limited as well) ... This one should be trivially parallelizable ...
> Approx range of d is of the order of 10^15 or more ...
>
> I am not sure if anyone else is interested in the database creation ... That
> might be a good project as Austin ...
Definitely. In fact, you could compute several things
about every quadratic imaginary field up to some bound
(e.g., class group structure too, etc.?)
> Will see you tonight / tomorrow ...
>
> Sourav
See you.
William
P.S. Try to keep the discussion on the sage-days11 mailing list.