---------- Forwarded message ----------
From: William Stein <[EMAIL PROTECTED]>
Date: Mar 19, 2007 1:57 PM
Subject: Re: some ramblings about the relationship between sage and MAGMA
To: Research mathematician
On 3/19/07, a Research Matheamtician wrote:
> I think the reason that xxx found it [sage] slow was that he wasn't actually
> _using_ any number-theoretic functions! He was writing his own custom
> "foundational" code to compute automorphic forms on U(3). I think Lassina
> also did this at around the same time (but their implementations have
> trivial intersection! For example I think Lassina always wants class
> number 1 but David always works with some fixed G which has class number 2).
> If you've ever computed automorphic forms for a definite quaternion
> algebra then you'll know that it is in essence just combinatorics; for
> example most of the work with Hecke operators is, for a given prime p,
> finding p+1 matrices in O, the "integers" of your definite quaternion
> algebra, with norm p and satisfying some funny congruence conditions so
> for example given D of discriminant 2 you spend most of your life finding
> all solutions to a^2+b^2+c^2+d^2=p or 4p and then sorting them into
> equivalence classes. I think that sage was arguably built to do things
> other than this. For U(3) it's even worse; you spend your entire life
> finding matrices X in M_3(Z[i]) such that X times X^{conjugate transpose}
> is diag(p p p) and I think David just looped in some semi-naive way.
>
> In fact let me tell you what David's implementation looks like for auto
> forms over a group that one might call "the U(3) associated to Q(i)":
>
> 1) Input level N.
>
> 2) Loop through small primes p that split in Q(i) (this is the way hecke
> ops work)
>
> 3) For each such prime find all matrices in a certain "normal form" in
> M_3(Z[i]) satisfying X.X^{conj transpose}=p
>
> 4) For each such matrix, apply some awful explicit algebraic
> transformation to X, the analogue of "compute Symm^g of a 2x2 matrix" but
> with 3x3 matrices and computing some explicit quotient of Symm^g tensor
> Symm^h(transpose).
>
> 5) Add up what you have: there's your Hecke operator.
>
> 6) Make sure you've looped over suff many prime to break your space up
> into 1-d eigenspaces and you're done.
>
> As you can see you're barely using anything here other than integer
> addition and multiplication, and some basic matrix manipulation. He should
> have written it in assembler!
:-) Maybe he should have written it in SageX (the compiled variant of
Python) probably
directly against the gmp C library. The parts that would benefit from
assembler are already written in assembler in GMP. The speed situation
for this sort of thing will be roughly like this, with the ones listed lower
being faster.
Python ("Interpreted SAGE")
Magma
SageX ("compiled Python" used right)
C
SageX just generates C code, so if you do things right it is the same speed
as C. But it is often much easier and tempting to do things in an easier
way first (which looks almost exactly like pure python), and then it's slower
than C.
Implementing low level arithmetic manipulation like your discussing in
the Magma interpreter can be frustrating too. I did it with my modular
symbols code, and no matter what tricks I used it was
slower than what I could do in C. With Magma the only option at
that point is to (visit Sydney and) get them to code what I wanted as part
of the Magma kernel. With SAGE, you put the relevant code in a .pyx or
.spyx file, compile, and use the result from the interpreter. I like this
better.
-- William
--
William Stein
Associate Professor of Mathematics
University of Washington
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
