On Feb 8, 2008 3:47 PM, David R. Kohel <> wrote:
> Hi Andrew,
>
> I'll CC this to William Stein and David Joyner.
>
> On Fri, Feb 08, 2008 at 09:05:11AM -0800, Andrew Mathas wrote:
> > Hi David,
> >
> > A long (short?!) time ago we spoke a little about *sage*. Somehow I came
> > across it today and perhaps because I am more python literate I looked
> > at it more closely. It looks quite impressive and, more importantly, it
> > seems to do that things that I would want it to do. As your name seems
> > to be on many of manual pages I wondered whether you would answer some
> > questions about it for me. If you're too busy just say so as I can ask
> > William Stein instead.
>
> Indeed, since I was initially involved, sage has really taken off.
>
> > The backdrop to this is that I have a lot of gap3 code (including my
> > share package), and I have been thinking for a long time that I should
> > migrate to another system but, until now nothing has appealed to me (I
> > don't like gap4 and magma may have a limited lifetime). The "issue" is
> > becoming more pressing because I keep running into memory constraints
> > (gap3 is capped at 2G) and gap3 is very slow, especially for some of the
> > large calculations that I have been doing recently.
>
> I think your Specht package may have come up in the sage-devel list,
> perhaps with Chevie, as desired packages in GAP3 but not GAP4.
Yes it did more than once I think.
> > *Sage* appears to provides everything that I need. Initially I was very
> > impressed as some of the more specialized combinatorial functions that I
> > use are already implemented. Looking through the source, however, I
> > discovered that a significant number of functions fork a call to gap, or
> > pari, or... (some of the ones that do this are quite strange as the
> > thing required calculations are easy to code) On the plus side the
> > CombinatorialAlgebra class fits my needs perfectly.
>
> The idea is not to reinvent the wheel, when existing open source code
> does the job. But there are many instances where native arithmetic
> would be trivial and faster to provide, and eventually native code is
> or can be developed. In the context of group theory, for example,
> permutations needed to be reimplemented to remove the high overhead of
> calls to GAP for basic arithmetic.
Permutation group elements have already been reimplemented (by Robert
Bradshaw) in highly optimized compiled code for Sage. They are reasonably
fast now in Sage.
sage: G = SymmetricGroup(10)
sage: a = G('(1,2,3)(5,7)(8,9)'); a
(1,2,3)(5,7)(8,9)
sage: time for _ in xrange(10^6): b = a*a
CPU times: user 0.65 s, sys: 0.00 s, total: 0.65 s
Wall time: 0.68
> > Anyways, do you have any thoughts on, or answers to, the following list
> > of questions?
> > 1. How fast is *sage* compared with, say magma and gap4. For me the most
> > important operations are integer and polynomial arithmetic and
> > array/list management routines.
Sage uses GMP with all good extra GPL-only patches, etc., and some not
available in other GMP installs, so is very fast at basic integer arithmetic.
Sage has the fastest arithmetic in ZZ[x] in the world -- it uniformly
beats Magma
(and all other systems) by a factor of 2-5, at least. This is *not*
enabled by default
right now -- you have to explicitly use the FLINT library from Sage:
http://www.flintlib.org/
Example of using this in Sage:
sage: from sage.libs.flint.fmpz_poly import Fmpz_poly
sage: f = Fmpz_poly([ZZ.random_element(x=0,y=2^32) for _ in xrange(1000)])
sage: g = Fmpz_poly([ZZ.random_element(x=0,y=2^32) for _ in xrange(1000)])
sage: time h = f*g
sage: h
1999 6684584840446047824 23942650631229367434 34624803467740693611
... many pages
sage: time for _ in xrange(10^3): h = f*g
CPU times: user 1.84 s, sys: 0.07 s, total: 1.91 s
Wall time: 1.94
In the future one will just work in ZZ['x'] directly in Sage and FLINT
(instead of NTL) will
be used behind the scenes. That's not done yet though.
Sage also has an asymptotically faster charpoly algorithm than Magma,
though tuning
and other issues make it unclear when it will be faster (work remains
to be done here).
Sage's system solver over QQ, i.e., solving A*x = b over QQ, is vastly
faster in Sage than
in Magma, except when A has tiny coefficients. Sage's Hermite Normal
Form was very
slow compared to Magma, but soon that will change:
http://sagemath.blogspot.com/2008/02/benchmarketing-modular-hermite-normal.html
Generally speaking the goal in Sage is that all the fundamental exact
arithmetic algorithms
be better than Magma, and hence better than anything else in the
world. Sometimes this
is the case i Sage now, but in many cases work remains.
> This depends, but the idea is that the fastest algorithms and code should
> be developed. Allan Steel (down the hall from you) has so optimised the
> basic arithmetic in Magma that it is often hard to beat.
Every time we put really serious effort into trying, we do beat it so far.
Sometimes this is quite hard -- the work on FLINT took quite a while
and is very subtle.
> However, he
> optimises his code for his examples or interests. For various things
> like linear algebra of medium sized sparse matrices, Magma's performance
> was holding up the sort of algorithms in which William and I were
> interested. Of course Allan is down the hall from you, so you could just
> walk down the hall and get a fix or implementation (if you could interest
> him in the problem or convince him that some feature is a bug).
And there are several dozen very active Sage developers, which is a better
resource overall than one person. There were 27 different people that
contributed to the last Sage release (i.e., that contributed new things to Sage
during the last two weeks).
> > 2. Are there any memory limitations on *sage* (under macosx)-- since
> > it's python based I assume not but I am asking just to be sure.
>
> I don't think this should be a problem, except possibly for legacy code
> which might be wrapped (like GAP3?).
Sage on Mac OS X is currently 32-bit only, which means that it *does*
have memory limitations, certainly < 4GB. We are actively working
on making it so Sage builds in 64-bit mode on Mac OS X, but haven't
finished this yet. On 64-bit Linux, Sage builds fine in 64-bit mode and
has no artificial memory limits; people regularly run huge calculations
that use a lot of RAM, and Python 2.5 has good support for lists
with > 2^32 elements. You can also usually do almost anything
you need by dropping to the compiled level using Cython (http://cython.org).
> > 3. Am I right in thinking that one option for pre-compiled code is to
> > simply write it in cython, which is not drastically different from python?
>
> Yes, if you need performance in code that is called a lot.
Yes, that is the canonical option. About 1/3 of the core Sage
library, which is about 250,000 lines
of code, is written in Cython (so Sage is by far the largest Cython
project in existence).
> > 4. Do you know roughly what proportion of functions fork a call to
> > magma/magma/pari etc?
Essentially none of Sage depends on Magma (certainly not by default).
Sage does not "fork a call". It sets up a once and for all psuedo-tty interface
and uses that to communicate with persistently running subtasks. Only
a small proportion of Sage functions are implemented using this, except
in group theory where this is used a lot.
> Is there much overhead in calling these functions regularly?
Yes, there is some if the computation time is trivial. Otherwise the
overhead is irrelevant.
> Obviously this depends on the application. Pari is a C library, so
> directly wrapping the C should be efficient.
The Sage wrapper of the PARI C library is extremely efficient.
> Calling Pari or GAP by
> passing strings has been a limitation in the past. If critical speed is
> missing, a post to sage-devel or submission to sage-trac can put it on
> the adgenda for improvement (even better if you submit a patch :-)).
True.
> > 5. What is the more dominant paradigm amongst *sage* users/developers:
> > write python code directly or fork whenever possible to
> > magma/gap/mathematica/maple/... ?
>
> Note that Magma/Mathematica/Maple are not open source.
Yep. We never ever use Magma/Mathematica/Maple to implement anything.
The whole point of Sage is to "provide a viable open source free *alternative*
to Magma, Maple, Mathematica, and Matlab", and calling those systems to
implement basic functionality would completely defeat that purpose.
The paradigm among use Sage developers is to write code that WORKS as
soon as possible, is fast, and is robust. We do this using whatever free
open source tools are available.
> Interfaces to
> them exist as service to the community, since many people have code, and
> licenses, to these programs that they was to use in their computational
> environment.
exactly.
> But sage is an open source project and code which depends
> on closed packages should never be shipped or intrinsic to the system.
> GAP and Pari on the other hand are open source and important components
> of the system.
Yep.
> I presume that the priorities are:
>
> 1) The best and fastest open source code should be used (not
> reinventing the wheel); and
> 2) If a better algorithm or native code can do better, then
> the faster algorithm should be implemented.
Exactly.
> There are also many standard open source C libraries (gmp, NTL, etc)
> which provide core arithmetic without rewriting.
>
> Much of the impressive rate of development of sage has been made possible
> by priority 1), which in turn has built a large user base and enthusiastic
> developer base, which makes 2) feasible.
>
> Again William or David might have comments.
>
My only comment is that you're 100% right.
> Cheers,
>
> David
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
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://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
