Sage: Open Source Mathematics Software

Mathematical Software and Me: A Very Personal Recollection

2009-12-07T11:32:00.000-08:00

[You can also read a pdf version of this blog post.]

I find it difficult for me to write a history of Sage without writing
a history of my personal involvement with mathematical software. I
loved using calculators since my earliest memories. My father somehow
got a mechanical electric adding machine for me when I was quite
young, back in the 1970s, and I spent a great deal of time filling
ribbons of paper with it. Then he got me an old TI scientific
calculator from a yard sale, with a LED readout. At age 11, when I
moved from Oregon to Texas, I bought a sliderule, which was pretty
exciting for a while. Then in junior high I finally got a real
scientific calculator, a little Casio, whose instruction manual I
devoured. This was my first inroduction to trigonometry, statistics,
and many other bits of computational mathematics. I was prepared
though, since I had done elementary school on an unusual
work-at-your-pace alternative curriculum, and had already worked
through 10th grade level mathematics.

The first mathematical computer software I ever used was Mathematica,
back in 1992 on a Windows 3.1 PC, when I was a 17-year old
undergraduate at Northern Arizona University in Flagstaff, Arizona.

Naturally, my copy of Mathematica was pirated, since like many
students I was extremely poor at the time. The only thing I found it
useful for at the time was drawing 3d plots (just for fun), and even
then it was frustrating, since there was no way to interactively
change the viewpoint. I also obtained a copy of MATHCAD somehow,
which I found much more useful than Mathematica. This is perhaps not
surprising, because at the time I was a computer engineering
undergraduate, so taking courses in Physics, Electrical Engineering,
Programming, etc.. I was definitely not a mathematics major: I
remember once finishing a multivariable calculus class and thinking
``this is the last mathematics class I'll ever take"! I also used
Maple for about an hour or two in a computer lab for a mathematics
course I took, but found it very cumbersome; this was a token 1-hour
introduction to math software that professors gave their students,
perhaps to justify the grant that paid for the computer lab. At the
time, I viewed Maple, Mathematica, and MATHCAD as software that didn't
really go beyond scientific calculators in any exciting way.

My next encounter with mathematics software was in early 1994 when I
became a mathematics major, after accidentally encountering an
abstract algebra book misfiled under computer science in a used
bookstore, and being instantly mesmerized by ideas such as groups,
rings, and fields. I was in another small computer lab and stumbled
on printouts of the documentation (Northern Arizona University
professor) Mike Falk had for Cayley, which was the predecessor to
Magma. I was amazed and excited, since the capabilities and ideas in
Cayley went so far beyond anything I had thought was even possible in
mathematical software before. I'm pretty sure I never got to actually
use Cayley though, since like now, the software was very expensive
and hard to get. Instead, I just spent a lot of time reading the
reference manual full of its beautiful examples of computing with
groups, rings, and fields, which were the very objects that had
enticed me into mathematics in the first place.

In fact, after that brief encounter with Cayley, I didn't touch
mathematics software again, or even do any nontrivial computer
programming for 3 years. This was because in 1994 I became intensely
interested in theoretical mathematics, and spent most of my time
during the next 3 years systematically doing exercises in mathematics
books, ranging from basic books on linear algebra and combinatorics
(which was big in Arizona) to Hartshorne's Algebraic Geometry.

In 1997, I was a graduate student at Berkeley, and didn't want to
teach so much, so I landed a job (funded by the NSF VIGRE program) in
the department for one year doing programming of curriculum materials
for an undergraduate linear algebra course, along with fellow graduate
student Tom Insel. Though I had been using Linux for years, I had
never thought about free software, or that actual people could
contribute to it. I thought of Linux as ``Unix that I can install on
my own computer", and back then one still paid for Linux by buying a
CD, since downloading over a modem was way too slow. Tom and I spent
a lot of time working on our project together, and he told me how he
had written some software included in Slackware (a Linux
distribution), so got free copies of the CD when new versions came
out. Hey, anybody can contribute to Linux!

I also remember Tom complaining frequently about how we were forced to
program in MATLAB for our project, and he mentioned many other
alternatives that would have been better for what we were doing,
including Java. We were doing GUI programming, with a tiny, tiny bit
of actual mathematics thrown in, and MATLAB's handle-based system for
writing graphical users interfaces was really painful. I had a lot of
experience with C/C++/Windows 3.1 GUI programming from my computer
science undergraduate days, and agreed that MATLAB was pretty awkward
for what we were doing at the time. In retrospect, what we did was
probably pointless, and perhaps never got used. However, the
experience was extremely valuable for both of us, and I'm glad NSF
funded it.

In the meantime, my Ph.D. thesis was going nowhere, despite nearly 3
years of graduate school. One day, I heard about a problem Ken Ribet
was asking all the graduate students: ``Is there a prime number p such
that the Hecke algebra at level p is ramified at p?" It's the first
research problem I can ever remember hearing that was almost certainly
impossible to solve without using a computer. Fellow grad students
Janos Csirik (now at D.E. Shaw), Matt Baker (now at Georgia Tech), and
I searched and found one paper by Hijikata (?), I think from the mid
1970s, which gave an algorithm that might allow one to answer the
above question for specific p's. But to implement the algorithm, it
was necessary to compute class numbers of a huge number of quadratic
fields, and none of the mathematics software I had ever heard of until
then could do this. Janos and Matt mentioned PARI, and I installed it
on my computer. And indeed, it could quickly and easily compute class
groups! PARI was also the first free mathematical software I
encountered.

So I started coding up the algorithm (the Eichler-Selberg trace
formula) in PARI. I had a lot of experience with C++, which is a real
programming language with user defined data types, exception handling,
templates, etc. I rememember in 1992 carefully reading several C++
book cover-to-cover, and I wrote a large amount of code (video games!)
in C++ long, long ago. In contrast, PARI was an immediate shock.
This was a language with no local variables, no real scoping, only a
couple of builtin types, and for a while I thought (incorrectly) that
entire function definitions always had to be on one line, since that
was the case in example code I found. But the algebraic
number theory algorithms implemented in the internal library were
amazing, deep, and very fast. So I implemented the trace formula, and
ran it to try to answer Ribet's question. The program did not
work---basic consistency checks failed. It turned out that there was
a major bug in the algorithm for computing class groups. In
particular, the function qfbclassno, silently returned wrong
answers.

You would think that qfbclassno would be fixed by now. But no. It's
only frickin' 12 years later!! I just checked right now, and the
documentation for PARI still says ``Important warning. For $D < 0$,
this function may give incorrect results when the class group has a
low exponent (has many cyclic factors), because implementing Shanks's
method in full generality slows it down immensely.'' This is buried
in the documentation. The only change is that I think in 1997 the
documentation said that the authors were ``too lazy'' to implement the
full algorithm. Note: In the 1990s the function was classno instead at that
time. I found in tutorial.tex from
pari-1.39a.tar.gz:


    Type {\tt classno($-$10007)}. GP tells us that the result is
    77. However, you may have noticed in the explanation above that
    the result is only usually correct.  This is because the
    implementers of the algorithm have been lazy and have not put the
    complete Shanks algorithm in PARI, causing it to fail in certain
    very rare cases. In practice, it is almost always correct, and the
    much more powerful {\tt buchimag} program, which {\it is}
    complete, can give confirmation.

So I worked around that problem, and was able to run the algorithm for
all primes up to about 300, but didn't find any primes as in Ribet's
question. A few weeks later, at the Arizona Winter School in March
1998 in Tucson, Arizona
(AWS), I mentioned
this to Joe Wetherell (who was another Berkeley grad student), while
we were walking to lunch, and he told me he had written a program---also
in PARI---for computing with modular symbols (following John Cremona's
book), with which I might be able to push the computation a little
further. He gave me a copy later, and I started playing around with
it, and computed the discriminants of all of the Hecke algebras of
prime level up to about 500. NOTE: That program lives on here, in case
you're interested: tables.
And it still works (here with GP 2.4.3)!!!


? M37 = modsym(37,+1);\\
1. Generating M-symbols                 (0 ms)\\
2. Hashing M-symbols                    (2 ms)\\
3. Quotienting out by relations         (3 ms)\\
4. Computing the kernel of delta        (0 ms)\\
Total time.......................       (5 ms)\\
? factor(charpoly(T(2,M37)))\\
\%27 =\\
%[x 1]\\
%[x + 2 1]\\

Again, I didn't find any examples, and I wrote to Ken Ribet to tell
him. Then I hopped on a plane and flew to Cambridge, England, to
visit Kevin Buzzard.

Once I got settled in Cambridge, I rechecked my calculations for some
reason... and found an example for the prime $p=389$! Somehow, I had
just missed the example in my previous check. I was extremely excited
as I wrote to Ken Ribet, with my first ever genuine contribution to research
mathematics, which appears in a big paper Ken published on the
Manin-Mumford conjecture---I had shown that his new theorem definitely
did not prove that conjecture for all modular curves. I was also hooked
on computing modular forms, and started making tables. It was also
the height of the mad cow disease scare in England, so I became a
vegetarian.

I tried to push the PARI program that Joe Wetherell had given me to
make bigger tables, but it very quickly ran out of steam. The main
algorithms that the modular symbols algorithm relies on are all manner
of linear algebra over the rational numbers, including computation of
characteristic polynomials, and kernels of sparse and dense matrices,
and also factorization of polynomials over the integers. Despite its
first rate algebraic number theory capabilities, PARI was (and still
is) terrible at linear algebra with really big matrices over the rational
numbers. Also, I found the PARI programming language unbearably
naive.

So I spent the summer of 1998 writing a much more general C++ program
for computing with modular forms called HECKE. Here it is:
hecke. If you grab the file
hecke-july99.gz from that web page, and drop it on just about any Linux
box, it should just work: NOTE
Here is Hecke which I just tried on a Core 2:


% ./hecke-july99
HECKE Version 0.4, Copyright (C) 1999 William A. Stein
HECKE comes with ABSOLUTELY NO WARRANTY.
This is free software, and you are welcome to redistribute it
under certain conditions; read the included COPYING file for details.


         HECKE:  Modular Forms Calculator   Version 0.4 (July 9, 1999)

                       William Stein
Send bug reports and suggestions to was@math.berkeley.edu.
Type ? for help.

Anyway, I spent all my time for many months
writing HECKE. This program built on several other C++ math
libraries, including LiDIA and NTL. It doesn't use PARI, because
using PARI from C is... really weird, and LiDIA/NTL had equivalent
functionality at the time. Much of the time I spent on HECKE involved
(1) designing algorithms, generalizing work in Cremona's book, etc.,
and (2) implementing and optimizing algorithms for linear algebra over
the rational numbers. For (2), Kevin Buzzard hooked me up with the
same code Cremona used, which Cremona had got from some South American
student at Cambridge named Luis (?). I then spent a large amount of
time optimizing that code for my computations. The actual linear
algebra algorithms in that code were very naive compared to the
algorithms in Sage now, but they were better than anything available
in any other software I was aware of, or in research papers at the
time.

I was able to compute many fairly sophisticated tables using HECKE,
and it soon became the canonical software for computing with modular
forms, since it was the only software generally available for such
computations. This is perhaps similar to how NAUTY was for a very
long time the canonical software for computing graph automorphism
groups. Naturally, I made HECKE freely available on my webpage. I
remember once getting an email from Ken Ono, who has probably written
over 100 papers on modular forms, many inspired by concrete examples.
He had run across HECKE on my web page, installed it, and was totally
blown away by the capabilities of HECKE, and how useful it would be
for his research. A whole new world had opened up to him, and he told
me he was promptly ordering a new fast computer specifically to run
HECKE on. I was happy to help. Also, my thesis work was starting to
go well, because the computations I was doing was suggesting
interesting new (and do-able) mathematics, left and right.

Then, in 1999, David Kohel---who had been a Berkeley grad student with
me until December 1996---was visiting Berkeley from Sydney, Australia,
and told me about implementing algorithms related to his thesis in
Magma. I think this was the first I had ever heard of Magma, despite
Magma having been around for several years. Magma was expensive and
nearly impossible to get unless you knew the right person, since it
was sold via informal channels. I think there was an install on the
computers in Berkeley, but those computers were ancient vintage
1990-ish Sun workstations, so nobody would seriously try to use them.
Anyway, David had implemented code for computing with rational
quaternion algebras, and this was the only implementation of that
algorithm in the world. Coincidentally, I had extended an old idea of
Ribet to come up with a new algorithm for computing Tamagawa numbers
of modular abelian varieties (see ants and
compgrp). I really, really wanted to
implement my algorithm, because it would allow me to compute all of
the invariants in the Birch and Swinnerton-Dyer conjecture (except
Sha) for most rank 0 modular abelian varieties, which would be a huge
step forward. But my algorithm fundamentally relied on exactly the
computations in rational quaternion algebras that David Kohel had
implemented in Magma. And that was no small undertaking---it's a
complicated algorithm, it takes somebody familiar with the relevant
theory months to implement and optimize, and it builds on many other
basic capabilities. I had a thesis to finish. David---who was then
officially a Magma developer, was able to give me a copy of Magma for
my own computer, which had his code in it. Combining all this with
HECKE, and copying and pasting, I was the first person ever to systematically
compute Tamagawa numbers of general modular abelian varieties (at primes
of multiplicative reduction).

So in 1999 David Kohel put me in a situation where I was fundamentally
dependent on a closed source non-free program in order to continue my
own research. Ironically, during the same afternoon in my apartment
in Berkeley, he mentioned the GNU Public License (GPL), and suggested
I released HECKE under the GPL. Before that moment, I had never even
heard of the GPL. I did as he suggested, but had no idea what it
meant really. That was perhaps fortunate, since the dependencies of
HECKE are NTL and LIDIA, and the NTL license is GPL, but the LIDIA
license is GPL incompatible, so technically I guess HECKE can't be
distributed. Incidentally, LIDIA is still licensed under a
GPL-incompatible license, despite many emails I've received suggesting
the license would change to GPL---licenses don't change easily, due
to having to get agreement from all copyright owners.

I obviously had to actually use Magma at some level in order to do
these computations. Despite having a lot of experience with
programming, I initially found the Magma language and system extremely
hard to learn or do anything with. It was certainly much harder to
use initially than PARI. On the one hand, Magma is a massive system, with
thousands of commands and thousands of pages of reference manual documenation, but
on the other hand there is very little in the way of ``introspection",
i.e., given an object A, it is hard to get context sensitive help
about A. However, one thing was clear: Magma was dramatically better
at dense linear algebra over the rational numbers than HECKE. It was
a whole different world. We're talking jaw dropping speed. In fact,
Magma in the late 1990s on an old computer, was far faster at large
linear algebra over the rationals than Maple or Mathematica is today
on the latest hardware. I would soon find out the reason.

Allan Steel is an enthusiastic Australian, who was an undergraduate at
University of Sydney in the early 1990s and fell in love with the
Magma project. I guess David Kohel told John Cannon about me in 1999,
and Allan happen to be visiting Berkeley for a conference, so Allan
and I met. We ended up talking a huge amount over 3 days. Allan
answered my every question about the language and the system---usually
with an answer about how he had implemented it that way for a
certain reason. So within a few days I knew Magma well enough to be
quite productive in it. Also, Allan gave me some hints about why
linear algebra was so fast: together with polynomial and integer
arithmetic, asymptotically fast linear algebra was one of his main
interests. He explained an exciting array of algorithms, many of
which he had developed or---more importantly---made practical.
There were dozens of tricks that I had never heard of, such as
rational reconstruction, multimodular algorithms, p-adic algorithms,
etc., which were far beyond what I had done with HECKE, or seen in any
other software. And they meant that it would be possible to push my
modular forms computations much farther. All I had to do was rewrite
HECKE in Magma.

It was my last year of graduate school at Berkeley, and I probably
should have been writing my thesis, but instead John Cannon flew me
down to Sydney, Australia, to work with the Magma group for a month
and do a complete new implementation of all the algorithms in HECKE on
top of Magma. I shared an office with Claus Fieker, a German who has
implemented a large amount of the algebraic number theory in Magma,
among other things. As I started doing this, I had some serious
concerns, including: Magma did not allow users to define their own
types (or classes), there is no exception handling, there is no ``eval
statement", no way for users to write compiled code, Magma is closed
source, and Magma is not free. I raised all of these concerns with
Cannon and others, and was assured at the time that they would all be
addressed really soon, except the free part. Regarding free, they
said that I could give copies of Magma to whoever I wanted, so long as
I checked with John Cannon first.

I don't remember why exactly, but I remember once during that month in
1999 going on a walk through the park near the U Sydney campus near a
pond of ducks, sitting on a bench, and realizing that I was making a
huge sacrifice of my freedom as a researcher by going down this path.
Magma was not open source---John Cannon had absolute control over the
system. Magma was not free. And as a language, Magma was
significantly behind C++. It didn't even have a sensible notion of
scope, and one added new data types by entering entries in big tables,
then recompiling the kernel. I asked Cannon why it was so far behind,
and he explained that the grants he was able to secure simply wouldn't
pay for language design. The people who supported Magma with funding
(mainly granting agencies) would only support implementing and
optimizing mathematical algorithms, and the license fees only paid
enough to support ``maintenance", which mainly meant the person who
collected the license fees and distributed Magma via ftp. Ten years
later the Magma language has hardly improved at all. They finally
have exception handling, but still no user defined types, etc., etc.
The library of functionality implemented in Magma is huge though; the
issues with the language didn't stop people from implementing many
exciting algorithms, which have supported huge amounts of research in
number theory and other areas.

I sat down on that park bench, and realized what a dangerous path I
was taking in giving up so much freedom so early in my career. I
resolved at that moment not to do it. At that moment I started
designing what would eventually become Sage. I started thinking about
the language I would implement (I had taken a course in writing
interpreters when I was a student), about implementing all the linear
algebra algorithms Allan had hinted at (but given no details), etc.
I then realized that if I did this, I would have to do it by myself,
since almost everybody I knew used Magma, and would consider my plan
too difficult and pointless. I wouldn't get to do number theory for
years. My spirit broke. And Cannon told me that many of my issues
with Magma would be addressed within a year.

I spent the next 5 years writing and using Magma. I gave dozens and
dozens of talks all over, and convinced anybody who wanted to do
computations with modular forms that Magma was the way to go. I gave
away free copies of Magma (with John Cannon's official blessing),
taught undergraduate courses using Magma, and was generally very
productive. Also in 2003, I had a real job and money, so I started
forming this philosophy of software, where I would judge what software
I used purely based on capability and functionality, and not on price
or openness. I started using Microsoft Windows fulltime, since it
best supported my PDA and had the widest range of software. I bought
some $500 (with educational discount) suite of Adobe software for
video editing, photos, vector graphics, etc. And of course I used
Magma. I was a well paid academic at a well-endowed university
(Harvard), and wanted the best that money could buy.

In 2002, William Randolph Hearst III also donated money to Harvard to
buy me a cluster computers, and by 2003, I wanted to easily script
running lots of computations in parallel. Since Magma didn't have any
parallel capabilities, I stumbled on some language called ``Python"
(Version 2.3), which looked a lot like Magma, but was designed for
general purpose scripting. I started using it to run many
computations in parallel on that cluster. It was the best tool I
could find for the job.

I also started working much harder on making the number theory data I
was computing with Magma available online, and naturally I turned to
Python. Dimitar Jetchev (a Harvard undergrad) and I wrote Python code
to make the data easily queryable via a web interface, and also wrote
code that made it so one could do computations in Magma (and PARI in
some cases) over the web. One incarnation of this is hosted on the
Magma website: calc

As I learned about Python, a funny thing happened. I had by this
point developed a large list of issues with Magma. For example, the
documentation and examples in the Magma reference manual aren't
automatically tested to ensure they give the claimed output, and they
often get out of sync with the actual code. Python is in many ways
similar to Magma -- the language itself feels somewhat similar, and it
has the same ``batteries included" philosophy. The surprising thing
was that Python had solved the dozens of major problems I had with
Magma! I was excited about this in 2003, and so during my next (and
last) trip to work with the Magma group in Sydney, and started trying
to incorporate these solutions into my new Magma code, and to explain
what I had learned to John and others. Right after I returned from
Sydney, I recall excitedly explaining all of this to David Goldschmidt
at a reception at an AMS meeting.

I was quite surprised when a month or two later, in early 2004, John
Cannon really soundly rejected my ideas and even had one of his
employees rewrite my new modular abelian varieties code to get rid of
them. In retrospect, now that I run a large software development
project, I can understand why he didn't get what I was doing. But I
was really suprised then. Second, I went to a big Magma conference at
IHP in Paris, where Manjul Bharghava (a young professor at Princeton),
me, and many other people gave some series of talks. I recall
listening to Manjul's talk as he described a research problem he was
working on, and during his talk he explained that the whole thrust of
his research was seriously stymmied because Magma is closed source.
He needed to adapt some relatively minor part of the some algorithm in
Magma related to quadratic forms, and simply couldn't due to it not
being in the interpreter level of Magma. This just didn't seem right.

I also had lunch with John Cannon during that workshop, where he
explained some big plans he had to edit a huge sequence of volumes
about the mathematics behind algorithms implemented in Magma. I
suggested that it would be nice if these were freely available, and he
did not think that would be possible. He made good on his idea, and I
actually published a paper in the first such volume:
bsdmagma. I wrote that paper in Windows
using Microsoft Word (and converted to LaTeX using WinEdt, a non-free
LaTeX frontend, only at the very end)!

Finally, at that IHP workshop I learned two other things. First, I
learned that a workshop is an incredibly efficient way to develop
mathematical software, far more efficient than the Magma model of
hiring people for months at a time and flying them to Sydney, and
certainly vastly more efficient than what Maple, Mathematica, and
Matlab do, which costs literally costs hundreds of millions of dollars
per year. Second, I recall overhearing conversations about the Magma
language during tea breaks by some locals who were interested in the
workshop, but had not drank the Magma koolaid, and in these
conversations it became clear that I wasn't the only person that found
the Magma language to be deficient.

I started reading slashdot in early 2004, mainly for the interesting
tech news, and the comments kept mentioning ``open source", which was
honestly something I had paid almost no attention to until then.
Intrigued I decided to look around and see how open source mathematics
software had done since I had abandoned it in 1999. NTL was no longer
being actively developed, the LiDIA project was nearly dead, PARI
hadn't changed much (except to break all my old code), but with some
more algorithms for relative number fields. So in five years, the
situation with the open source number theory software environment had
got worse. I realized that I was probably partly to blame, having
tried to convince every number theorist I knew to use Magma, and often
given them free access to ensure they could. I had helped hook a
generation.

About this time I was also writing an elementary number theory book
(which eventually became this book: ent). I had
planned to have a chapter about number theory using each of
Mathematica, PARI, Magma, and Maple. I had the first three programs,
but didn't have access to Maple. Somebody suggested that being a
faculty member and writing a book should be a good argument for Maple
to send me a free copy, so I contacted them. A person from Maplesoft
called me back, and explained that though I was writing a book with a
chapter on Maple, they could not give me a free copy. However, they
could give me the special academic discount of 500 dollars. I asked
if he could do better, and he called me back the next day and said:
``If you can get 4 of your colleagues to also buy Maple at 250
dollars/each then I can sell you Maple for 250 dollars." I was
offended, so I ``obtained'' a ``trial'' copy, and started writing my
chapter anyways. I started trying all the same things as I had easily
done in PARI and Magma, e.g., checking primality of numbers, etc. I
was totally surprised to find that Maple was terrible, being massively
slower than Pari, Magma or Mathematica for most elementary number
theory computations relevant to my book. (Maplesoft was bought by
some Japanese company a few months ago, by the way.)

I also installed Linux in a virtual machine (under Windows), to see
what all the fuss was about, and found I started using Linux all the
time instead of Windows, because the software was better (even Magma
runs much better under Linux than Windows). I deleted Windows and
installed Linux. I was also starting to definitively realize that my
huge list of problems with Magma would never, ever get resolved, and
was getting increasingly frustrated by these problems because Python
didn't have them.

I started talking a lot with Thomas Barnet-Lamb about a crazy idea to
create a new open source math software system with readable
implementations of algorithms, and nothing hidden in some stupid
proprietary layer. Thomas was then a first year Harvard grad student
who had won some international computer programming competition, so
I figured he would enjoy talking about software. I also talked a lot
with Dylan Thurston about this crazy idea; Dylan had started grad
school at the same time as me at Berkeley, graduated the same time,
and had the same first two jobs as me, was also an Assistant
Professor. Both Thomas and Dylan gave me many ideas for programming
languages to consider, including OCaml (which Thomas liked), Haskell
(which Dylan was a huge fan of), etc. After having used Magma for
years, with its highly optimized algorithms, I desperately needed a
fast language. But I also wanted a language that was easy to read,
and that mathematicians could pick up without too much trouble, since
I wanted people like Manjul to someday use this system and not have
their research cut off. And I knew from experience that unreadable
source code is no better than closed source.

I'm not going to go into negatives of any languages. Though I used
Python a lot, for a long time I didn't consider it seriously at all
for this crazy project, since I tried implementing some basic
arithmetic algorithms in Python and found that they were vastly too
slow to compete with Magma (or C). I had also tried quite hard to use
SWIG to make C++ available in Python, but SWIG is extremely frustring,
and has horrible performance (due to multiple layers of wrapping), at
least compared to what Magma could do.

In October 2004, I was flying back from Europe (the Paris Magma
conference) and started reading the Python/C API reference manual
straight through. I realized that Python is far, far more than just
an interpreter. It is a C library that implements everything you
need, and has a well defined and well documented API. I did some
sample benchmarks on the plane, and found not surprisingly that I
could write code as extensions to Python that was just as fast as
anything one could write for Magma by modifying the Magma kernel,
since under the hood, both were written in C. Also, on the flight, I
realized that because the Python/C interface uses reference counting,
it would be vastly easier to write the C extensions I would need using
some sort of language I would design. I got home and somehow stumbled
onto Pyrex, which was exactly what I was planning to write. I tried
it out, did benchmarks, and realized that I had a winner.

With Pyrex and Python, I could implement algorithms and make them as
fast as anything in Magma, assuming I could figure out the right
algorithm. Moreover, the dozens of issues I had with Magma, many of
which were simply a function of them not having the resources to do
language development, were already solved in Python. And Python would
continue to move forward with no work from me. It was mid-2004 and
because of Python, the overall software ecosystem was much better than
in 1999, despite open source number theory software having not moved
forward much.

I started going to (and sometimes hosting) the Boston Python user
group meetings, which was quite large, and gave me much useful
feedback. And I decided it was time to move past my test and
prototype stage and get to work. My plan, as I had explained it to
Thomas, was to create a complete new system from the ground up using
Python + Pyrex. All the code would have an easy to read Python
implementation that was well documented, in some cases there would be
a much faster Pyrex implementation of the same code, etc. With my
naive plan in hand, I sat down with the main elliptic curves file of
the PARI source code, and started to translate.

I think I made it through one function. Where some might have
doggedly persisted for years with such an approach, I quickly ran out
of patience. In fact, when it comes to software and programming I can
be extremely impatient. I realized that my entire plan was insane,
and would take too long. I had discussions with Thomas, Dylan, and
others, and everybody I knew who was seriously into number theory
computation was using Magma, so I realized that I was going to have to
do this entire project myself. So I realized translating was doomed.
Somehow, even with all my experience, I had massively underestimated
the complexity of the algorithmic edifice that is any serious
mathematical software system.

I read the PARI C API reference, and used Pyrex to write a wrapper so
that I could call some basic PARI functions from Python. I implemented
basic rational and integer types using Pyrex and GMP, and the
performance was reasonable. One day, I was using Matplotlib (a Python
library) to draw some plots for Barry Mazur that involved explicit
computation with the incomplete Gamma function, and was frustrated
because neither PARI nor Magma had an implementation of this special
function at the time. Harvard had a Mathematica site license, so I
had a copy of Mathematica, and I wrote code using the pexpect Python
library to hold open a single Mathematica session and use it to
compute the incomplete Gamma function. Problem solved. This was when
the interfaces between Sage and other mathematics software systems was
born.

In January 2005, I was at the AMS meeting in Atlanta, Georgia, hacking
on my code, and David Joyner walked up to me and asked what I was
doing. Until then, I had not shown my Python/Pyrex math software
project to people. There were a few reasons, including feeling sure
that it was massively too difficult to pull off, that working on
something like this would seriously piss off John Cannon, etc. But
feeling brave, I showed David what I was doing and I was surprised
that he found it interesting. I promised to post a copy online, which
he could download.

David Joyner is the first to admit that it's a good idea to make
software easy for him! So I had to make it easy for him to download
and install my program, which I called Manin at the time (after one of
my favorite mathematicians). My target audience wasn't ``Debian"; it
wasn't ``Python programmers"; it wasn't elite hackers---it was David
Joyner. I had to make this program trivial for him to install, work
with, develop, etc. I thought about how it had literally taken me
huge amounts of time just to build Python, GMP, PARI, etc. all from
source in a directory for development, and realized that there was no
way in hell David would get anywhere on Manin if I told him that his
first step was to figure out how to build all those programs, then get
back to me. So I setup something that would do it all automatically
in a self contained way. He tried it, it ``just worked", and he got
really excited and started writing code for Manin. David is a coding
theorist, and wanted group theory and coding theory functionality in
Manin, but didn't want to write it all himself from scratch, so he
asked in email about making Manin and GAP talk to each other somehow.
I showed him my pexpect code for controlling Mathematica, and he
adapted it to create a GAP interface.

David also works at the US Naval Academy where he evidently teaches a
lot of Calculus and Differential Equations courses. He was having so
much fun with Manin, he asked about adding something to do symbolic
calculus to Manin. This was 2005, and I personally had never used any
symbolic calculus software aside from Mathematica and Maple 12 years
earlier, since I viewed computational symbolic calculus as pretty much
irrelevant for most computational number theory, and the Calculus I
had taught never required a computer since computers weren't allowed
on exams. (I now think no computational technique should be a priori
viewed as irrelevant to research in number theory!) So I asked David
about the available open source options, and he said they were Axiom
and Maxima, neither of which I had ever heard of. I can't remember
how we chose Maxima instead of Axiom, but it was some combination of
Maxima being easier to build, easier to understand, and having about
1000 times as many users. In any case, like with PARI, GMP, and
Python, I added Maxima and GAP to the Manin distribution. I also
changed the name from Manin to SAGE = Software for Algebra and
Geometry Experimentation.

David also convinced me Sage needed commutative algebra. At first, he
talked to people and tried to implement everything from scratch, but
even the resulting arithmetic was dreadfully slow. Groebner basis
would be a nightmare waiting on the horizon. We were both impatient,
so we decided to try to find an open source program already out here,
and just use it. There were two choices: Macaulay 2 and Singular,
which had a lot of overlap in functionality. For what we wanted---basic
commutative algebra---they both did all we needed. Singular
built from source easily in a few minutes on every computer I cared
about. Macaulay 2 was ridiculously hard to build and took a long
time. I think based mostly on that, we chose Singular. Also, it was
encouraging that Singular had a relatively large development team, and
did better in some benchmarks I tried.

At the same time as all this, I was traveling a lot and interviewing
for tons of tenure/tenure track jobs all over the place. I got some
job offers with tenure, and suddenly had the crazy idea that if I
worked fulltime on SAGE for a year two, my career could not be
destroyed. This really encouraged me. My number theory research
slowed a lot, and I spent all my extra time on SAGE for a while.

Remember David Kohel, who six years ago in 1999 first introduced me to
Magma? It turns out that like me he spent years and years writing a
large library of software on top of Magma for number theory and
cryptography research. However, at some point he had a fairly serious
falling out with the Magma group, whose details I will omit. Suffice
to say, like me he was motivated to at least look for other options.
He started building and using Sage, and started doing huge amounts of
work on Sage as well, e.g., introducing morphisms and categories
systematically into Sage, and implementing tons of code related to
elliptic curves, algebraic varieties, etc. David Kohel was a
Biologist as an undergraduate and has an amazing eye for general
structure. He also had many technical issues with Magma, which were
mostly different than mine. For example, he felt that the Magma
developers had made a mistake with the design of morphisms, and he
didn't want Sage to make the same mistakes. And he was right to
worry, since for things I didn't care too much about, I would usually
just copy Magma... or as David would say, ``copy Magma's mistakes".

I moved to San Diego and Joe Wetherell who first introduced me to
modular symbols in 1997 also got involved in Sage development, though
mostly from the conversation point of view. Joe had long ago quit
grad school to start a software company in the early 1990s, then
retired from that and went back to grad school, so he had a fairly
mature perspective on software development, and he knew a huge amount
about number theory and optimized algorithms. So 2005 was a long,
long year in which David Kohel in Australia, David Joyner in Maryland,
and me in San Diego, wrote code.

At the end of 2005, the three of us had written a ton of code,
integrated numerous components togethers, and finally had something.
On December 6, Jaap Spies mentioned Sage on the sci.math.symbolic
newsgroup, in response to which some guy named Richard Fateman
declared Sage a curiosity and made some unencouraging assertions about
the way the world works (regarding users, funding, etc.):

mathforum

I was certain deep down inside that Sage would fail anyways, that what
we wanted to do with Sage was totally impossible, so Fateman's
comments couldn't discourage me further. I just didn't care that Sage
was doomed. I couldn't help pushing further.

John Cannon found out about Sage, maybe as a result of the postings on
sci.math.symbolic, and right before Christmas in 2005 he sent me this
email:

---------------------------------------------------------------
Date: Mon, 19 Dec 2005 16:54:09 -0800
From: "John Cannon" 
Subject: Magma calculator
William,

This is to formally advise you that your permission to run a
general-purpose calculator based on Magma ends on Dec 31, 
2005. This was originally set up at your request so students 
in your courses at Harvard could have easy access to Magma.

Please confirm receipt of this letter.
Wishing you a happy Christmas,
John
---------------------------------------------------------------

This single email seriously scared me. Though I was working on Sage
very hard for nearly a year at this point, I honestly didn't then
expect Sage to really be able to replace Magma for me. Magma was the
commercially funded result of fulltime work over decades (really
starting in 1973 with the first version of Cayley). The amount of
work to get from what I had with Sage in December 2005 to what I had
with Magma in December 2000, was still absolutely momentous. I didn't
even know if it could be done by a single human being. Moreover, as
far as I could tell many of the critical linear algebras algorithms I
needed (to make the difference between a calculation taking a minute
or a year) existed only in the secret kernel of Magma and Allan
Steel's head, and they were going to stay locked there forever as far
as I could tell. For example, in June 2004 (before Sage existed),
Allan and I were together at the ANTS VI conference. I started asking
Allan to explain some of the algorithms, and he would explain things
to a point, but not nearly enough to do an actual implementation. And
he gave me this look, like he knew I was trying to get something out
of him.

Isn't it weird that mathematics can be done that way? In 2004, almost
everybody in the world doing serious computations with elliptic
curves, modular forms, etc., were using Magma. Magma was the industry
standard, Magma had won for the forseable future. David Kohel and I
were a big reason why. And yet what kind of mathematics is it, when
much of my work fundamentally depends on a bunch of secret algorithms?
That's just insane. Moreover, it turns out that these algorithms I'm
alluding to are really beautiful (and they are now standard and in
some cases better than what's in Magma, in my opinion, thanks to great
work of people like Giesbrecht, Perent, Kaltofen, Storjohann,
Saunders, Albrecht, etc.).

Anyway, John Cannon's email above seriously scared me. I wasn't in
any way confident that Sage would ever replace Magma for my work and
teaching, and I had big plans involving interactive mathematical web
pages. These plans were temporarily on hold as I was drawn into
Sage. But there were still there. What John did with that email is
tell me, in no uncertain terms, that if I was going to create those
interactive mathematical web pages, they couldn't depend on
Magma. ``This is to formally advise you that your permission to run a
general-purpose calculator based on Magma ends." I was scared. It
was also the first time I saw just how much power John Cannon had over
my life and over my dreams. That email was sent on a whim. I hadn't
got any official permission to run that Magma calculator for a
specific amount of time (just open ended permission). What John made
crystal clear to me was that he could destroy my entire longterm plans
on a whim. I looked around for other options, and there just weren't
any. Sage had to succeed. But still I was certain that it just
wasn't humanly possible, given that I had to do almost all the work,
with limited funding and time.

At this time I had an NSF grant, and also startup money at UCSD, hence
I could rebudget some of my NSF grant. David Joyner suggested that we
run a ``Sage Days", which I guess was named after the East Coast
Computer Algebra Days (ECCAD). David and I organized the first one,
and David did an amazing job inviting a great cast of speakers,
including Steve Linton (of GAP), Sebastian Pauli (of KANT), etc., and
Joe Buhler who also lives in San Diego made sure we scheduled the
workshop so that a lot of people would show up. We had Sage Days in
early February, and I released Sage version 1.0 during my talk, which
started the workshop. The talks went well, people were extremely
enthusiastic about Sage, the coding sprints were intense: the first
version of Sagetex was written, and the current sophisticated GAP
interface was written then by Steven Linton, Kiran Kedlaya and David
Roe wrote that Macaulay 2 interface, and I had the first spark of
insight about how to create the Sage Notebook, after watching a talk
by Robert Kern about some failed attempt to give IPython a notebook
interface. That was the first time I realized a notebook style
interface had some value. And Gonzalo Tornaria got us to finally
start using revision control for our source (!), which meant way more
people could easily contribute. (I had used revision control before
with Magma, but with Sage I had been just taking snapshots regularly.)

As a direct result of Sage Days 1, development picked up. Then I
moved to University of Washington (Seattle) two months later.
Somehow, during the summer of 2006 I was invited by MSRI to run a
2-week summer workshop on modular forms for about 40 graduate
students. I invited David Kohel and a few other speakers. At this
point, honestly some aspects of Sage sucked. I had written a massive
amount of code, for really wide range of things. Power series,
fraction fields, number fields, modular symbols, linear algebra, etc.
I probably should have just used Magma for the workshop, and indeed at
least one speaker entirely did. But I didn't... and this was a
turning point. Some of the students, such as David Harvey (grad
student at Harvard), Robert Bradshaw (Seattle), Craig Citro, and many
others, became highly interested in fixing the numerous flaws they ran
into with Sage. After the talks, we had huge all night coding sprints
in the dorm lobby. Students constantly asked me questions about how
to do things in Sage, and my answer was usually: ``It's easy. Implement
it and send me a patch!" They made a t-shirt for the conference with
this quote on it.

Next we started planning Sage Days 2 in Seattle in late 2006. This
second Sage Days was also well attended and resulted in major
fundamental development directions. For example, David Harvey led a
charge to redesign the coercion model and David Roe got obsessed with
implementing every model imaginable of the p-adics (this still isn't
really done over 3 years later). Sebastian Pauli gave a talk in which
he explained what anybody who takes an algebraic number theory course
knows (or pays attention to Weil), which is that there is a number
field and function field analogy and that all the algorithms carry
over. Guess what---Magma has a sophisticated implementation of all
the relevant algorithms in the function field case, due to work of
Florian Hess that built on work of the KANT group and others, and PARI
has absolutely nothing for algebraic number theory over functions
fields. Sebastian explained that in fact Magma is the only program in
the world that provides both sides of this analogy, I think hoping
that we would do something about this problem. (Now it is 2009, and
still nothing at all has happened---Magma is the only program in the
world for the function field half of algebraic number theory. Gees.)

We had about 13 talks on the first day of Sage Days 2. At the end of
the day, David Savitt (at student of Richard Taylor, and now a
professor in Arizona) looked at me and declared me insane.

After Sage Days 2, I spent over 2 very, very painful months
implementing David Harvey's proposed coercion model. I learned (or
rather, remembered) how difficult certain types of changes to a large
interrelated library can be. Also, a student from San Diego---Alex
Clemesha---followed me to Seattle, and I paid him fulltime to work on
Sage using my startup money. He implemented 2d graphics for
mathematicians (instead of scientists, which is what matplotlib
provides), and he also helped a lot with the first version of the Sage
Notebook. In fact, he was a big Mathematica user before he started
using Sage, and he really missed the Mathematica Notebook, so he
wanted something similar in Sage. When he used Mathematica, he had a
job programming webpages using webMathematica, so really wanted
something that combined the notebook idea with a webpage. We came up
with various ideas. Then I hired an undergraduate, Tom Boothby, who
had just quit a 6-year career in web programming to go back to
college. Together, the three of us figured out how to write AJAX
applications, and the first version of the notebook was born.

It was a controversial decision at the time to write a webapp
instead of a traditional local GUI application. There were many
reasons we made this choice, but for me it was mainly because (1) I
had written some serious local GUI applications before and knew that
they are not easy to write, not portable, and hard to build from
source, and (2) I had tried out wxMaxima (the local GUI maxima
interface) and was just totally shocked to see how bad it was, due to
having to reinvent the wheel---they would have to implement font
dialogs, tabs, everything from scratch; in contrast, with a web
application much of that comes for free. So my motivation was
entirely to create a desktop application quickly. That it happen to
later make it possible for people to collaborate easily, use a Sage
notebook over the web, etc., is a nice bonus. And, it's clear by now
that web applications (like Facebook, Gmail, etc.) are extremely
popular now, and will only get way more popular in the future.

In 2007, the Sage project started really picking up steam. Bobby
Moretti, another UW undergraduate, got obsessed with making it
possible to actually do symbolic calculus in Sage itself. Until
Bobby's code was added to Sage in mid 2007, absolutely all symbolic
Calculus in Sage had to be done via explicit unnatural calls to
Maxima, and involved embarassing and confusing conversions. Bobby, me
and others spent a lot of work designing Sage's first symbolic
calculus interface, and Bobby wrote a pure Python ``proof of concept"
reference implementation that used Maxima via a pseudotty behind the
scenes for everything. This took him months, and probably had a
negative impact on all other aspects of his life. But he heroically
pulled it off. It went into Sage and changed things
dramatically---suddenly, Sage could actually be used for some
undergraduate courses. This increased interest in Sage dramatically.

A few months later, in November 2007, Sage was nominated for the
Trophees du Libre, and Martin Albrecht presented Sage at the meeting
for finalists. We won first place in the Scientific Software
category. This resulted in a blitz of publicity (e.g., several
slashdot articles, and articles in papers around the world in many
languages), and greatly increased the number of Sage downloads.

Around this time we also have Sage Days 5 at the Clay Mathematics
Institute, and Craig Citro convinces us to switch to a 100% peer
review and 100% doctest policy on all new Sage code. Also, I hire
Michael Abshoff to do release management for one year, which
temporarily frees me up to work more on coding, grant proposals, and
my own research.

There is of course much, much more to this story. But it's too
recent, and sometimes a story shouldn't be told until enough time has
elapsed.

The Sage Notebook

2009-10-11T23:56:00.000-07:00

The Sage Notebook is the graphical user interface to the math software Sage. The notebook is perhaps somewhat unusual in that it is a web application that people also use locally. It's a large program that has been written and rewritten a few times since 2006 by myself, Tom Boothby, Alex Clemesha, and many, many other people.

Supported by an internal grant from University of Washington, I've been working on separating the notebook off from Sage and rewriting many parts of it to improve the robustness and fix subtle issues. My goal is that the notebook be robust, fast, scalable, and work well outside Sage. Also, it would be very nice to port it to run natively on Microsoft Windows.

Nearly two weeks ago I had the Sage notebook stabilized and all known new bugs fixed (after separating it off from sage as a separate program and rewriting the interface stuff). But I realized that it would be a total nightmare to introduce yet another ("Sage object") storage format, which would make refactoring code extremely painful. So, I created an "abstract storage layer" and implemented a storage system for everything in the Sage notebook which doesn't use any special Sage-related pickles. Some data is stored as pickled basic Python objects that can be read from any version of Python with or without Sage installed, but that is it. Rewriting the notebook to use an abstract storage layer is the sort of thing that at first seems like it will take a day, but then takes more than a week. Anyway, I did it (with help from Tim Dumol and Mitesh Patel).

I hope people will test http://standalone.sagenb.org/! Please try it.

William

VirtualBox versus VMware Server

2009-10-07T21:29:00.000-07:00

VMware is a program that allows you to (often safely) run several virtual computers on a single physical computer. I have been using VMware since about 1998, have purchased valid licenses several times with my own money, and have long considered VMware the sort of enterprise level specialized software that was unlikely to be available free and open source anytime in the near future.

All the web infrastructure for http://sagemath.org and many related projects was knocked offline for a full day last week due to problems I had with my VMware server installation. I thus decided to learn the free open source competitor VirtualBox and see how it compares to VMware, and share some of my experiences with you. I'm comparing to VMware server running on a very high end Linux host (Sun X4450) to VirtualBox running on the same Linux host. I vastly prefer VirtualBox now, even though I was a diehard VMware user since 1998.

Ways VirtualBox is better then VMware Server:

Both are free, but VirtualBox is free and open source (GPLv2!), whereas VMware server is "free" and closed source. It's possible to buy VMware server + more features for thousands of dollars / year, and I even considered it, but I *couldn't* figure out what I would get for my money from the confusing VMware site, despite coming back to it several times.
VirtualBox is massively better at supporting OS X than VMware server: it is *impossible* (without running yet another virtual machine on my laptop!) to use the VMware server console to connect to remote virtual machines on OS X, since VMware uses a proprietary browser plugin that is only available for Windows and Linux. In contrast, VirtualBox uses a standard remote desktop protocol, so it is easy to connect to running VirtualBox consoles from any operating system using a range of different remote desktop clients.
VMware server limits me to 2 cores and 8GB RAM per machine. VirtualBox has no such limitations. This is a *huge* factor for me, since the host server has 128GB RAM and 24 cores!
If a virtual machines runs under VMware server and uses 4GB RAM (say), then VMware server will silently (and completely hidden) allocate around 4GB of disk space on the host filesystem. My host server has 128GB RAM, but only a 70GB hard disk. The net result is that I can't use the resources I have -- I have to run far less machines than I could, or give them less RAM. VirtualBox doesn't allocate any "secret" disk space at all.
The web interface to VMware is extremely flaky and frustrating. It randomly fails to work with many of my web browsers, I often have to restart it, and it is clunky. There is no finished web interface to VirtualBox yet, but there is VBoxWeb, which is looks like it will be good when it is finished. Also, the command line interface to VirtualBox is amazing; I think it is vastly superior to VMware Server's. Also, there is a Python API for scripting VirtualBox machines. After spending a day learning VirtualBox, I wrote my own scripts to automatically start from the console all of my virtual machines in the background, and open remote desktop ports for each. I can easily see what is running using another little script, etc. With VMware server, even starting 20 machines was a tedious and painful exercise (probably if I paid it would be easier).
The VirtualBox documentation is better. It doesn't "talk down" to me like I feel VMware's documentation does. It's clear and useful.
VirtualBox is a single program that runs on Solaris, OS X, Linux and Windows. VMware, in contrast, is several different programs -- VMware player, VMware workstation, VMware server (and several versions of that). It can be really confusing and frustrating, with artificial limitations put on every program so as to extract your money.
VMware is blatantly commercial (they went public a few years ago). Sun is also commercial, but they have a strong commitment to open source. Of course, I don't know what will happen with the Oracle acquisition.
VMware completely stopped working on my main virtualization server, and despite upgrades, clean installs, etc., I absolutely could not get it to work again. I had to switch to running it on another computer temporarily.

Technology in Mathematics Education - Panel

2009-04-03T08:04:00.000-07:00

In a few hours I'll be in a panel discussion about technology in mathematics education. I might say something like the following.

Math and technology in general: To me mathematics is about solving problems by understanding them more deeply, finding ways to explore them, finding elegant proofs, looking for ways to visualize and compute with deep structure, etc. Math software is simply another tool or technique that one can use to _massively_ enhance ones ability to solve mathematical problems. Asking whether or not to use computer technology in mathematics is no different than asking whether or not to use "logical reasoning" or "linear algebra" or any other major tool in the mathematician's toolchest.

Math and technology in teaching:

A. Open Source -- I personally feel it is terrible to *train* students mainly to use closed source commercial mathematics software. This is analogous to teaching students some weird version of linear algebra or calculus where they have to pay a license fee each time they use the fundamental theorem of calculus or compute a determinant. Using closed software is also analogous to teaching those enthusiastic students who want to learn the proofs behind theorems that it is illegal to do so (just as it is literally illegal to learn *exactly* how Maple and Mathematica work!). From a purely practical perspective, getting access to commercial math software is very frustrating for many students. It should be clear that I am against teaching mathematics using closed source commercial software.

B. Problem solving -- Many students are interested in mathematical software mostly because it allows them to solve *a lot* of problems that are simply impossible to do by hand. For some (at least me) it transforms math from a tedious, error prone, and frustrating (but addictive) exercise into an exciting exploration of an amazing "virtual" world of interesting problems, ideas, and techniques. For most people, even before computers, anything but fairly trivial algebra or calculus is nearly impossible to do correctly by hand. Gauss (1777-1855) spent years counting the 216816 primes up to 3 million... and wrote in a letter in 1849 that there are 216745 such primes. Any undergrad can type prime_pi(3*10^6) into Sage and get the right answer instantly.

C. Regarding student skills being lost due to the existence of computers -- If you really want students to be able to do something, e.g., compute integrals without using a computer, give them in class exams on that material. By far the main complaint I have and hear from both students and professors is that students have too limited skills at using mathematics software. This situation is ridiculous. Would we give a degree in Software Engineering to a student who has never written a computer program? Why give a degree in techniques of "Mathematical Problem Solving" to a student who can't even use a computer to solve mathematical problems, given that computers are one of the most important basic tools in the mathematician's toolchest.

new hardware!

2008-12-22T15:07:00.000-08:00

I recently received four 24-core Sun X4450 with 128GB RAM, and a Sun X4500 storage box with 8 cores, 32GB RAM, and 24 terabytes of disk space. It took literally less than 2 hours to install Ubuntu 8.0.4 LTS server Linux on all the 4450's (about 15 minute each), but several more days to make some sort of transition over to them.

The machines are fast. Most tests I try run twice as fast on the new machines as on the old sage.math (which was a 1.8Ghz Operton).

The first frustrating transition was that I can no longer run Magma on the new boxes, because they have a different MAC address. I've received one user complaint so far, and expect others, though of course I hope people consider using a viable open source alternative.

I installed about 20 operating systems, including most major Linux distros, FreeBSD, and Solaris under vmware server on one of the boxes, and configured them to all use NFS. Unfortunately, we don't have an NIS/NIS+ or OpenLDAP server setup, so only I can login to those boxes :-(. Setting up NIS or OpenLDAP clients and servers is not for the faint of heart. Anyway, just installing that many Linuxes and configuring them with build tools and NFS took about two days, including time to download installation media. Of all the OS's the only one I gave up on was gentoo, which is a complete disaster (hours of tedious instructions that don't quite work; the live installer crashing; getting the live installer to work, but having vi crash on compilation once it boots up, etc.); that is the worst major operating system I have tried. According to distrowatch, "Gentoo Linux has lost much of its original glory in recent years. Some Gentoo users have come to a realisation that the time-consuming compiling of software packages brings only marginal speed and optimisation benefits. Ever since the resignation of Gentoo's founder and benevolent dictator from the project in 2004, the newly established Gentoo Foundation has been battling with lack of clear directions and frequent developer conflicts..." The failure of Gentoo hopefully helps emphasize the importance of clear direction.

Anyway, it is very nice having about two dozen cleanly installed OS's with a shared filesystem, all running on very fast hardware.

We still haven't installed an operating system on the 24 terabyte disk box, and have a lot of configuration work to do. Fortunately, Tom Boothby is working for me as a sysadmin, so he will do a lot of the hard work.

Sage Patch Review

2008-11-28T19:44:00.000-08:00

I just spent a lot of time during the last few days refereeing Sage patches in the Sage trac server. Basically, we got behind and had something like nearly a 100 patches in there that were marked as "[with patch; needs review]", which means that the patch is done, and is just waiting on review. Some of the patches in this state hadn't been commented on since August! In many cases they had "bit rotted", which means that they are broken, since related parts of Sage had changed after the batches had been posted.

In June 2008 at Sage Days 8.5 we had a long meeting and setup a patch referee editor system, but it turned out to be a total failure. Our system was setup to be like a journal editor system, except with the addition of a weekly meeting. Even in person, our one and only meeting was an inefficient experience, and it never worked over irc or email.

Review is a Generic Problem

Robert Bradshaw recently went to a Google Summer of Code Mentors summit, and told me that the number one problem open source projects have that was discussed a lot at the summit is with patch review, in particular, with patches not getting reviewed in a timely fashion.

Review is also a big problem with mathematics journals, though with journals the turnaround time is expected to be months. Or even years -- I have one paper that's been in the review process at Mathematics of Computation for 3 years now, and I've almost never gotten a first referee report back from that journal in less than a year from submission time! But for some reason math journals tend to work. That said, I had some discussions with a prominent publisher about a journal that had fallen apart because the chief editor had seriously dropped the ball, and said publisher had to spend a massive amount of his own time fixing the situation.

Patch Review and Paper Review

Reviewing a math paper is a much different experience from reviewing a software patch. When one reviews a math paper, you basically get a potentially very interesting paper that is at the cutting edge of research, which you would be crazy to not want to read anyways (or you're just going to easily not recommend it for publication). When you review the paper, you excitedly read it, and if things don't make sense -- or the style is bad, or whatever -- you get to ask the author to explain clearly any point that troubles you, and the author definitely will. It's a lot of work, but it is mathematical research.

Reviewing a patch is different than reviewing a math paper. First, very often a patch fixes a subtle bug in Sage or introduces some new functionality. If the patch fixes a subtle bug, then of course the fix itself could easily introduce a new subtle bug, or maybe not really fix the bug correctly, and the referee has to figure this out. If the patch introduces new functionality, it could easily contain bugs, often bugs that the author of the patch hasn't thought about testing for. Often when refereeing a patch, I bounce it back with a use case that exhibits a bug. Some of the most common and dangerous patches are the ones that speed up existing code. These are often some slight changes in a few places, which seem safe enough, and make some code a bit faster. Last time I looked at one of these, I decided to loop over the first 100 obvious test cases -- about the 90th input crashed the new code (the old code worked fine on that example). I would have never noticed that problem had I just read the patch and tried the tests included with it; it was thus critical for me to creatively think of new tests.

Of course, when refereeing a math paper one also looks for subtle flaws and tests theorems for consistency, but still it has a different feel than refereeing a patch.
And with refereeing patches there is also a time window, which also a huge problem. Patches stop working because the rest of the Sage system evolves past them -- math papers don't just stop working because somebody out there proves more theorems.

What Should We Do?

As I said above, I believe that patch review is a major problem for the Sage project. I think the best solution is that there be one person at any given time who acts as the "patch review manager". This person could vary from month to month. This position would be the analogue of release manager or more directly of the chief editor at a traditional journal. Every few days, this person looks at the list of all patches that need review and goes through every single one, either pinging people about them, or refereeing them if possible. Said person, must be bold enough to be able to understand code anywhere in Sage, and have a good sense of who can look at what. If a person did that, I believe our patch review problem would be solved.

If we don't do this, the Sage project will operate at reduced efficiency and new and experienced developers alike will get needlessly frustrated. (NOTE: We currently do have Michael Abshoff who does pretty much what I describe above, but he has other things he should be doing, since he is release manager.) The Sage project will have a harder time reaching its goal to be a viable alternative to Magma, Maple, Mathematica, and Matlab. We have to work smarter and do a better job, for the sake of all the people out there currently forced to use Magma, Maple, Mathematica, or Matlab, instead of an open source peer reviewed scientifically viable system like Sage aims to be.

Magma and Sage

2008-11-23T19:43:00.000-08:00

I spent the weekend working on making Sage and Magma talk to each other more robustly. Getting different math software systems to talk to each other is a problem that the OpenMath project tried to tackle since the 1990s, but they failed. Sage has out of necessity made real (rather than theoretical) progress toward this problem over the years, and what I did this weekend was a little step in the right direction for Sage.

First, I designed with Michael Abshoff a new feature for our testing framework, so we can test only optional doctests that depend on a certain component or program being present. Without a usable, efficient, and flexible testing system it is impossible to develop good code, so we had to do this. Next, I worked on fixing the numerous issues with the current Sage/Magma interface, as evidenced by many existing doctests failing. It was amusing because some of the doctests had clearly never ever succeeded, e.g., things like


 sage: magma.eval('2')       # optional
 sage: other stuff

was in the tree, where the output was simply missing.

Anyway, in fixing some of the much more interesting issues, for example, things like this that involve nested polynomial rings, I guess I came to understand better some of the subtleties of getting math software to talk with other math software.


sage: R.<x,y> = QQ[]; S.<z,w> = R[]; magma(x+z)
boom

The first important point is that one often thinks that the problem with interfacing between systems is given an object X in system (say Sage), finding a string s such that s evaluates in another system (say Magma) to something that "means the same thing" as X. This is the problem that OpenMath attempt to solve (via XML and content dictionaries), but it is not quite the right problem. Instead, given a particular mathematical software system (e.g., Magma) in a particular state, and a view of that state by another system (e.g, Sage), the problem is to then come up with a string that evaluates to the "twin image" of X in the running Magma system.

To do this right involves careful use of caching. Unless X is an atomic element (e.g., a simple thing like an integer) it's important to cache the version of X in Magma as an attribute of X itself. Let's take an example where this caching is very important and subtle. Consider our example above, which has the following Sage code as setup.


sage: R.<x,y> = QQ[]
sage: S.<z,w> = R[]

This creates the nested polynomial ring (QQ[x,y])[z,w]. The new code in sage-3.2.1 (see #4601) does the following to convert x + z to a particular Magma session. Note that the steps to convert x+z to Magma depend on the state of a particular Magma session! Anyway, Sage first gets the Magma version of S, then askes for the generator names of that object in the given Magma session. These are definitely not z,w:


sage: m = magma(S)
sage: m.gen_names()
('_sage_[4]', '_sage_[5]')

The key point is the strings returned by the gen_names command are strings that are valid in Magma and evaluate to each of the generators we're after. They depend on time -- if you did stuff in the interface earlier you would get back different numbers (not 4 and 5). Note that it's very important that the Python objects in Sage that _sage_[4] and _sage_[5] point to do not get garbage collected, since if they do then _sage_[4] and _sage_[5] also become invalid, which is not good. So it's important that the magma version (m above) of S is cached.

Next Sage gets the magma string version of each of the coefficients of the polynomial x+z (over the base ring R) using a similar process. It all works very well without memory leaks, but only because of careful track of state and caching.
And the resulting string expression involves the _sage_[...]'s.


sage: (x+z)._magma_init_(magma)
'((1/1)*1)*_sage_[4]+((1/1)*_sage_[7])*1'
sage: magma(x+z)
z + x

Notice that _magma_init_ -- the function that produces the string that evaluates to something equal to x+z in magma -- now takes as input a particular Magma session (there can be dozens of these in a given Sage session, with different Magma's running on different computers all over the world). This is a change to _magma_init_ that makes the implementation of what's described above easy. It's an API change that might also be carried over to many of the other interfaces (?).

Sage-3.2 and Mathematica 7.0

2008-11-20T13:49:00.000-08:00

We just released sage-3.2! W00t! See for the tickets closed in this release.

There's been a lot of hyperbole due to Mathematica 7.0's recent release. A colleague of mine got a personal email from Stephen Wolfram himself, asking him to try out Mathematica 7.0, and instead my colleague forwarded the message to me and remarked that it was too late, since he had switched to Sage.

I looked over the Mathematica 7.0 release notes... and noticed that they added support for computing with Dirichlet characters. I implemented the code in Magma and Sage, and wrote a chapter in my modular forms book about computing with Dirichlet characters. So I followed the "what's new" to this Mathematica page about their new functionality for Dirichlet characters. It's sad. They give no way of specifying a character, except to give the "ith character", which is meaningless and random (and they say so) -- that's like giving a matrix over a finite field at random. All they give is a function to evaluate characters at numbers -- they don't give functions for arithmetic with them, or computing invariant such as the conductor, which is where all the real fun comes in. Boggle. Sage is light years ahead of Mathematica here.

The Mathematica release notes also brag about finally having something for finite groups, but again it is very minimal compared to what Sage provides (via GAP). Basically all they have is a bunch of tables of groups, but no real algorithms or functionality. The whole approach seems all backwards -- first one should implement algorithms for computing with groups, then use them to make tables in order to really robustify the algorithms, then compare those tables to existing tables, etc. I wonder whether the group theory data in Mathematica was computed using Gap or Magma?

2008-11-12T17:53:00.001-08:00

I'm back from Sage Days 11 (UT Austin), which was very intense as are all Sage Days. It was a great workshop, and kickstarted many things, I hope. One very obvious big plus that came out of it was Craig Citro and Gonzalo Tornaria's work on massively optimizing the Cython-related dependency checking code in setup.py. The current implementation was some crappy thing I literally did in an hour, which has really bogged down as the Sage core library has gotten massive. Also, there's now a lot of momentum behind implementing Dokchitser's L-functions algorithm natively in Sage, which I'm greatly looking forward to -- Sourav San Gupta did much work on this at Sage Days 11, and has done a lot since too (in addition to his heavy load of grad courses). Mike Rubinstein and Rishi are wrapping Rubinstein's Lcalc using Cython as well, so Sage will soon go from the best system for computing with L-functions to even better!!

Yesterday I thought a bunch about the Sage/Magma interface and wrote several demos and test code. I'm still not 100% sure about how I want to do this -- there are numerous interesting subtleties with Magma. For example, if you create QQ[x,y] in Magma, then create QQ[x,y][z,q], the variables x,y from the first ring will *not* play nicely with the variables x,y in the second ring, which is surprising, since it is different than what happens with Sage. Anyway, this and many other problems are solvable and I'll be working on this again a lot tomorrow.

Sage Days 11 in Austin Texas is tomorrow

2008-11-06T18:06:00.000-08:00

I'm in Seattle, it's 6pm, and Sage Days 11 is in Austin, Texas tomorrow. I'm very excited, and I'm flying there over night. On the one hand, a red eye might make me "totally exhausted" for the conference tomorrow. On the other hand, I slept an average of 2-3 hours per night for a week during Sage Days 8 last time I was in Austin, and I'm reasonably caught up on sleep.

My main goal for the workshop is to continue work of Tim Dokchitser and Jennifer Balakrishnan to create a native implementation of Dokchiter's algorithm for computing L(f,s). Having this is suddenly incredibly important to my number theory research, so I'm finally motivated to want to get it into Sage.

I'll post about the workshop in my blog here.

Why I like Sage

2008-10-01T09:39:00.000-07:00

Today's blog post is really from Jason Grout. It's why he likes Sage. This is from an email he sent out today, which I liked reading:

"It depends on the area, so you'll have to give me an area to get a more specific answer. In general, Sage has somewhat weaker general symbolic capabilities (i.e., integrals, etc.) than mathematica or maple (though usually this does not seem to be a problem in undergraduate-level problems). It has *much* stronger number theory functionality. Things are object-oriented in Sage and Sage understands mathematical structures and how they relate (using category theory). For example, Sage knows what a vector space is, what a finite field is, etc. You can actually create a finite field or an extension of the rationals and ask questions about it. You can create a polynomial ring over a field and then just work with it.

Sage is also generally faster than either Mathematica or Maple, in my experience.

The web interface to Sage is a huge plus to Sage over mathematica and maple. Of course, being free and open-source is something that is unmatched in either Mathematica or Maple; that is a very important point that is sometimes overlooked. You can literally see what is going on inside of Sage, where you have to guess what is happening in Mathematica or Maple.

One reason that Sage was chosen for an AIM workshop on helping undergraduate research was that the participants didn't have a common computational system (i.e., some had access to Mathematica, some had access to Maple, some had access to neither). They could use Sage because it was free, whereas it would have been problematic to insist that every person somehow acquire access to a specific piece of commercial software. Related to this, I had a student complain on my course evaluations about me using Mathematica in class because it is hard for our students here to have access to Mathematica, and they would have to pay in order to use it at home, etc.

If you are teaching future secondary ed teachers, then they most likely will not have access to Maple or Mathematica when they are teaching high school because of the cost. However, they *will* have access to Sage, so using Sage directly benefits their future students because whatever they learn can be used in their high school classes.

Another huge plus to Sage, in my eyes, is that it is based on one of the most prevalent and easiest-to-use computer languages around, Python. Students that learn to use Mathematica and Maple learn a language that they, in most likelyhood, will never use once they graduate. However, Python is used in many, many industries, so their python knowledge from using Sage is directly applicable later on.

Those are a few things that came to my mind right away. After some time thinking about it, I probably will have other things that make Sage more effective for me than other commercial software.

Thanks,

Jason"

Austria, ISSAC, and Hidden Markov Models

2008-07-24T04:40:00.000-07:00

Yesterday, I gave a controversial plenary lecture on Sage at the 2008 ISSAC symbolic computer algebra conference. It was well received by some proportion of the large audience of about 170 people, and will hopefully influence that research community to be more supportive of open source. In particular, I hope professors doing computer algebra research will allow their Ph.D. students to use open source software on research projects instead of forcing them to use Maple or Mathematica like most of them currently do at RISC.

Many people asked me what I thought of the ISSAC conference -- it was very similar to the yearly ANTS (Algorithmic Number Theory Symposium) meetings we number theorists have, but without number theorists. The meeting has a generally positive "vibe" and participants are enthusiastic about doing computation. My only criticism compared to ANTS is that the publication process for the proceedings isn't nearly as professional as what ANTS does -- the ISSAC publisher's website was in my opinion hell to use, working with the publisher to get my abstract in shape was no fun, and the final paper proceedings look like they were done at Kinko's, whereas ANTS proceedings are part of Springer-Verlag's lecture notes in computer science series, hence look very professional *and* are available online.

I also started looking at getting Hidden Markov Model functionality into Sage, since HMM's are very relevant to certain areas of machine learning, language processing, statistics, financial time series, etc., and Sage doesn't do much in that direction yet. I was prepared to have to write something from scratch myself in Cython, but quickly found GHMM.org, which is GPLv2+, actively used and developed, written in C with a Python interface, and with some work could possibly work very well for Sage. I would certainly rather spend a solid week writing high-quality documentation and tests (and reporting bugs) than months learning, implementing, and optimizing algorithms followed by a solid week writing high-quality documentation and tests, followed by months building a community of developers to maintain said code. The GHMM program linked to above only has an svn distribution and depends on xml, and it depends on swig. I've created an spkg that one can build into sage and which doesn't depend on libxml; it does assume you have swig installed, and takes about 30 seconds to install from source. It's installed into the system-wide sage on sage.math.washington.edu:


was@sage:~/patches$ sage
----------------------------------------------------------------------
| SAGE Version 3.0.5, Release Date: 2008-07-11                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------

sage: import ghmm
sage: ghmm.[tab key]
ghmm.Alphabet                          ghmm.AminoAcids

In a few hours Michael Abshoff and I are heading to Vienna to meet with Harald Schilly (who I've never met), who is the new sagemath.org webmaster.

ISSAC

2008-07-20T03:17:00.000-07:00

I arrived in Austria last night totally exhausted after spending some time in Amsterdam with Michael Abshoff, Hendrik Lenstra (who was my Ph.D. thesis adviser), Waldek Habisch (the FriCAS guy), and others.

All the students working on funded projects with me this summer have setup blogs, and I'm encouraging them to blog very frequently about their work on Sage. I will start doing the same. Here are links to their blogs:

The last thing I did on Sage was spent nearly a week working on making a release that has fixes for numerous subtle build (and other) bugs on a very wide range of Linux distributions and hardware, e.g., Itanium2's and 64-bit Pentium 4's.

2008-06-20T11:17:00.000-07:00

Ondrej, Bernard, and Tim have been sort of arguing in response to Rob Dodier's nice post... The discussion is missing some shades of gray. Here's what we actually do in Sage:

1. Identify needed functionality (e.g., compute characteristic polynomials of matrices, or "symbolic calculus").

2. Find the existing best open source free option that implements 1, if there is any (e.g., say the pari C library in the above example, or "maxima" + a very sophisticated Python interface).

3. Fully integrate 2 into Sage. (Bobby Moretti and I did this for Calculus, in the above example.)

4. Somebody comes along and points out that 2 is not optimal and that they can do better. E.g., they have a new algorithm for computing characteristic polynomials, or think they can implement a drop in replacement for symbolic calculus that is in fact much better.

5. Somebody tries very hard to implement 4. Sometimes they succeed, and we *switch* over to it, and sometimes they fail, and the code never goes into Sage. Both happen and that is fine by me.

This is what is happening with symbolics. In 2005 we identified Maxima as the best open source system given our constraints. Bobby Moretti and I spent about 8 months fully integrating Maxima in as the core of our symbolic calculus functionality in Sage. Bill Furnish "popped up" and claimed he could do something much better, and has been working on this for the last 5 months. If (or when) his code turns out to be clearly better than what is currently built on top of Maxima in Sage, then it will go into Sage. If not, it won't.

The *only* reason I can see for not going from 4 to 5 in the above example is that I, or Bobby Moretti, and Maxima authors, or whatever have big egos and can't stand to see their hard work and code get thrown away. Well I swallow my frickin' pride and just deal with it, and have thrown away massive amounts of code I write. I think that's really the core issue in this whole thread -- some people are really disturbed by code get thrown away... Well deal with it. It's much more important to make decisions that are best for the overall quality of a project and "the community goals" than to stroke your ego by keeping your own code alive forever.

GMP forked; Torbjorn Granlund: "blatant falsehoods and sinister insinuations"

2008-05-29T11:52:00.000-07:00

Torbjorn Granlund:
> The other publicly stated reasons are a mixture of
> blatant falsehoods and sinister insinuations.
> This fork exists for some very different reasons than those publicy
> stated.

I know why the fork exists, so I'll state publicly precisely
why the fork exists. The issues below are not
blatant falsehood or sinister insinuations.

1. FACT: (L)GPLv3 cannot be used by some companies. See below where
I discuss this issue at length.

2. FACT: The GMP project is not developer friendly. This is easy to
see by reading the GMP mailing lists.

3. FACT: The GMP project does not have a regular and
predictable release cycle. How many times has the GMP 5.0 release
been moved back -- it used to be "sometime in 2007", but now the
GMP site says "5.0 is planned to come out in a couple of years."

4. FACT: The working code repository of GMP is closed. There is
no public svn, etc. repository so that anybody can look at the latest
version of the GMP code. See 2.

5. FACT: Some extremely capable developers do not want to contribute to
an LGPL'd project, because they don't want their voluntary contributions
to be used by Maple, Mathematica and Magma to make money.

6. FACT: The GMP project is unfriendly toward natively supporting
Microsoft Windows using MSVC. Just see any email you have sent
to Brian Gladdman.

7. FACT: The GMP project has been unfriendly toward supporting OS X.
Just search the gmp list archives for OS X.

Torbjorn Granlund:
> I think the forkers over at SAGE use the purported v3 incompatibility
> issues as an excuse for forking GMP.

I have been approached by numerous people (from industry,
government, etc.) over the last three years about forking GMP.
GPLv3 was one of numerous factors that really pushed things
over the edge, though a fork would have happened anyways.

Torbjorn Granlund wrote:
> Seriously, please don't use this sort of rhetoric. At least not
> before you've explained the actual problem. I suspect the SAGE team's
> problem is mere stubbornness, in particular since they have not been
> able to produce one single reason for their problems with v3. But I
> am all ears, should somebody spell it out.

It is no secret that the Sage project receives some funding from
Microsoft Research to produce free open source
mathematical software for use by their researchers. See
http://sagemath.org/ack.html
for a list of organizations that fund Sage development.
A company-wide requirement at Microsoft is that they do not run any
GPLv3 code, not even binaries. This is not surprising in light
of numerous quotes by Stallman about how GPLv3 was designed
partly to attack Microsoft. For example:

Stallman: "The point of the GPLv3 conditions that apply to the
Novell/Microsoft deal is to give the rest of the community a defense
against Microsoft's patent threats. If these conditions do their job,
the result will be that Microsoft never goes beyond threats, and the
community is safe."
http://www.technewsworld.com/story/must-read/59780.html?welcome=1212081285

This is one straightforward reason why GPLv3+ only code
is a problem for the Sage project. It has nothing to do with
ideological stubborness by Sage developers (instead it is
ideological stubborness by Stallman).

If Microsoft maintains this policy, then they will
also not run new versions of Mathematica, Maple,
Magma, that depend on any LGPLv3+ code.
So the problem Sage has will also be a problem for all
those projects. And I guarantee you that people at Microsoft
know about this issue.

You probably don't like Microsoft, so I doubt we will find any sympathy
from you as a result of the above. But rest assured
that the above issues with GPLv3 are NOT motivated by "mere
stubborness" by the *Sage team*. So you are wrong about that.

Can There be a Viable Free Open Source Alternative to Magma, Maple, Mathematica, and Matlab?

2008-05-01T21:38:00.000-07:00

For over a decade I have primarily done research in number theory that often involves computation, mainly using Magma. In 2004 I realized that it was stupid for me to continue building my work on Magma because Magma is proprietary, the development model is closed, Magma is expensive which is bad for students, and the language itself lacked many features (e.g., user defined classes) that I had requested repeatedly for over 5 years. Thus to continue to use only Magma unacceptably limited my potential in both research and education.

Having used Magma for many years, I simply could not switch to an existing open source system. The only serious free open source software for number theory is PARI, whose capabilities are far behind that of Magma in numerous critical areas of interest to me, including exact linear algebra, commutative algebra, and algebraic curves. And no other free system--GAP, Singular, Axiom, Maxima, Macaulay 2, etc.--even comes close in all these areas. In fact, after a decade of patiently waiting, I doubt they ever will.

Magma is the result of several decades of hard work by extremely talented fulltime mathematicians and programmers such as John Cannon, Allan Steel and Claus Fieker. I've worked with them and they are simply amazing. The situation seemed hopeless. If I had only never used Magma and tasted of the forbidden fruit...

In 2004, sure that there was no possible way to solve this problem, and driven by nothing but pure blind compulsion, I started the Sage project as my little free open source alternative to Magma, and spent an insane amount of time working on it even though I was utterly convinced that there was no hope of Sage ever succeeding. The first version of Sage consisted of the Python interpreter and a few scripts for doing number theory.

After a year, some of my first feedback from the computer algebra research community came from Richard Fateman on December 6, 2005 when he posted his opinion of the Sage project to sci.math.symbolic: ``By avoiding applications (say, to engineering design, finance, education, scientific visualization, etc etc) the activity is essentially doomed. Why? Government funding for people or projects will be a small percentage of the funding for pure mathematics. That's not much. And the future is pretty grim.''

Honestly, I believed he was right, but I just couldn't stop myself from working on Sage. It is now nearly three years later and the Sage project currently has around 100 active developers and 10,000 users. In November 2007, Sage won first place in the scientific category of the Trophees du Libre, which is a major international free software competition. Sage is funded by the US National Science Foundation, the US Department of Defense, the University of Washington, Microsoft Research, Google and private donations. Sage has new releases every two weeks, and typically 30--40 people contribute to each release. All new code contributions to Sage are peer reviewed, and every new function must be documented with tests that illustrate its usage. The docs have over 50,000 lines of input examples.

So what is Sage and what makes it unique? Sage is:

a huge distribution of free open source mathematical software that is surprisingly easy to build from source,

a set of interfaces to most other mathematical software systems, and

a new Python library that fills in huge gaps in other open source math software included in Sage, unifies everything offering a smooth user experience, and provides a modern web-based graphical notebook interface with math typesetting and integrated 2D and 3D graphics.

Sage is the first large general purpose mathematics software system that uses a mainstream programing language (Python) as the end user language. Python--easily one of the world's top 10 programming languages--is a powerful and beautiful modern interpreted programming language with an organized and professional developer base and millions of users. Sage also makes extensive use of a Python-to-C compiler called Cython. Thus Sage has a tremendous advantage over every other general purpose computer algebra system, since Python has thousands of third party libraries, sophisticated support for object serialization, databases, distributed programming, and a major following in scientific computing.

Instead of reinventing the wheel, Sage combines many of the best existing open source systems that have been developed over the last 40 years (about million lines of code) with about 250,000 lines of new code. Every single copy of Sage includes all of the following software (and much much more):

Algebra and calculus: Maxima, SymPy
High precision arithmetic: GMP, MPFR, MPFI, quaddouble, Givaro
Commutative algebra: Singular
Number theory: PARI, NTL, mwrank, ECM, FLINTQS, GMP-ECM
Exact linear algebra: LinBox, IML
Group theory: GAP
Scientific computation: GSL, SciPy, NumPy, cvxopt
Statistical computation: R
Graphics (2d and 3d): Matplotlib, Tachyon3d, Jmol

Sage is thus the first system to combine together such a wide range of libraries and programs in a meaningful way. Instead this huge range of programs is tied together using Python's excellent extensibility via C libraries and using pseudo-tty's. Sage has a highly developed unified collection of pseudo-tty based interfaces that make it is possible to make extensive use of Maple, Mathematica, Magma, Matlab, GAP, Maxima, Singular, PARI, and many other systems from anywhere within a single Sage program.

Curious? If you want a viable open source alternative to Magma, Maple, Mathematica and Matlab, drop everything, try out Sage now and become a Sage developer.

http://www.sagemath.org

Sage-3.0 and Beyond

2008-04-22T09:19:00.000-07:00

Finally, after much hard work, Sage-3.0 has been released! This release has tons of bug fixes plus several new features such as interact mode in the notebook, the R interface, full GCC-4.3 support, much better automated testing, etc.

Most importantly, Sage-3.0 finally has code for computing with modular abelian varieties. You almost certainly have no clue what those are, but suffice to say that I started the Sage project to compute with them, so having this code in Sage is a major milestone for me and the project.

We dramatically increased our automated testing and example suite so that 51.5 % of functions have autotested examples. There are now nearly 60,000 lines of input examples. In February our testing was in the 30% range. This was a huge amount of work by many many Sage developers, and it has the practical impact that when you type foo? it is nearly twice as likely that you'll see a helpful example.

There is now a new interface to R that uses a pseudotty; this is a completely different alternative to rpy, which makes it possible for the web-based Sage notebook to work as an R GUI, and also makes it so any R command can be used from Sage 100% exactly as in R. It is still clunky and has numerous issues, but it is fairly usable, documented, and has a test suite. Here it is drawing a plot in the notebook:

So what is the next step for Sage? We have finished rapidly expanding by incorporating major new components. Now we will work on making Sage more accessible and writing new code to make Sage highly competitive with all other options. I see The main goals for this coming year are as follows:

Port Sage and as many of its components as possible to Microsoft Windows (32 and 64-bit, MSVC) and to Sun's Solaris. For the Windows port the main challenge is writing a native implementation of pexpect for 32 and 64-bit MSVC windows, and porting several math software projects (e.g., R) that until now haven't had the resources to move beyond 32-bit crippled mingw/cygwin. For Solaris, the main issues are simply fixing bugs and improving the quality of the Sage codebase. Michael Abshoff is leading the charge.
Modular forms and L-functions -- greatly improve all linear algebra needed for modular forms computation; implement a much wider range of algorithms; run large computations and record results in a database. Mike Rubinstein and I will lead the charge.
Symbolic calculus -- a native optimized and much more general implementation of symbolic Calculus in Sage. Gary Furnish is leading the charge.
Combinatorics -- migrate the mupad-combinat group to Sage; implementation of a lot more native group theory in Sage. Mike Hansen is leading the charge.
Statistics -- integrate R and scipy.stats much more fully into Sage with the goal of making Sage the best available environment for statistical computation and education. Harald Schilly is leading the charge.
The Sage notebook -- separate the notebook from Sage (like I did with Cython); develop the notebook's interactive and visualization functionality much more, and make the notebook easier to use as a graphical frontend for all math software. I am leading the charge until I can find somebody else to do so.
Magma -- greatly improve the ability of Sage and Magma to work together (many more automatic conversions between Sage and Magma datastructures, etc.); Magma is by far the best in the world and numerous calculations, and much important code been written in Magma, so it's critical that Sage be fully able leverage all that functionality. Also, this will make comparing the capabilities of the two systems much easier. I'm also leading the charge here.

All of the above goals have received new financial support from industry or the NSF. For example, Microsoft is funding the Windows port, Google is funding many of the above projects, and the NSF is strongly funding a big modular forms and L-functions database project. The sage-devel mailing list has 434 members and over 1000 posts/month, and each Sage release has about 30 contributors. The size of the serious core Sage developer community might be nearing that of Mathematica's core developer group. Now is the moment in time when we have a chance to... create a viable free open source alternative to Magma, Maple, Mathematica, and Matlab.

Google Funds Sage!!

2008-04-08T05:05:00.000-07:00

Today Chris DiBona (open source programs manager at Google) fully funded a proposal [pdf] that some students and I put together to carry out four critically important Sage development projects this summer (2008):

Mike Hansen (UCSD): Implement combinatorial species in Sage. This will provide a backend to handle a wide range of new combinatorial objects with minimal eﬀort.
Gary Furnish (Utah): Implement new optimized symbolic manipulation code in Cython. This will greatly speed up symbolic computation in Sage, and reduce Sage's dependence on Maxima.
Robert Miller (UW): Implement fast code for permutation groups and backtracking algorithms. This is needed for general applications to graph and code automorphism groups computations, and can be used to exhaustively generate isomorphism class representatives of a wide class of mathematical objects.
Yi Qiang (UW): Further document, improve the usability of, and provide numerous real world examples of distributed computing with Sage. This will greatly help in applications of Sage to research that involve parallel computation.

This funding is not part of the Google Summer of Code (the projects above do not fit with any of the mentoring organizations), but is instead I hope part of more longterm support by Google for the Sage project and open source mathematical software that provides people with a free alternative to Maple, Mathematica, Matlab, and Magma.

This is what I would like in Sage 3.0

2008-02-29T12:24:00.000-08:00

DOCUMENTATION:
```
cd SAGE_ROOT/devel/sage/sage/; sage -coverage .
```
should output
```
Overall weighted coverage score:  x%  [[where x >= 50]]
```
Moreover there should be at least one hand written paragraph at the beginning of each file; "sage -coverage" can be adapted to flag whether or not this is there. This will improve the overall quality and maintainability of Sage, and make it easier for users to find examples.
MANIPULATE: Usable "manipulate" functionality standard in Sage. This has very wide applicability.
R: A pexpect interface to R (so, e..g, the notebook can act as a full R notebook using 100% native R syntax). This will matter to a lot of Sage users, and make using R from Sage much easier in some cases (just cut and paste anything from any R examples and it will work). It will also provide something in Sage that one doesn't get with Python + rpy + R.
TIMING/BENCHMARKING: Fully integrate in Sage wjp's code that times all doctests, and start publishing the results on all Sage-supported platforms with every Sage release. This will give people a much better sense about which hardware is best for running Sage, and avoid major performance regressions. Likewise, get the Malb/wjp/my generic benchmarking code into Sage (this provides a doctest like plain text format for creating benchmarks, and is already mostly written).

I've only proposed goals for 3.0 that are wide reaching and will be noticed in some way by most users instead of fairly technical optimizations in a specific area (such as FLINT, Libsingular, or optimized integer allocation). I think changing implementations in specific technical areas to speed things up is more appropriate in week-to-week releases, and is also something we should be very careful about until we have good speed regression testing in place (we should have done step 4
above a long long ago).

Mathematics Research, Education, and Sage

2008-02-21T16:29:00.000-08:00

I think there is a brewing tension between education and research amongst developers involved with the Sage project. More on that in a moment.

I cannot speak for all the core Sage developers, but I think I have some idea what some of them think and care about. My impression is that many of them are involved in Sage because they want to create software that they can use for attacking cutting edge research problems in their research area. This is true of me: I started Sage -- original called "Software for Arithmetic
Geometry Experimentation" -- to have a very powerful open software environment for computing with modular forms, abelian varieties,
elliptic curves, and L-functions.

I am quite happy that Sage has become much more general, addressing a huge range of mathematics, since this expands the range of good developers and also increasing the range of tools math researchers can bring to bare on attacking a problem results in better research. For example, the solutions
to many problems in number theory involve an incredible range of techniques in different areas of mathematics. I'm fairly certain that many of the people who have put in insane hours during the last few years making Sage what is it now (e.g., Mike Hansen, David Roed, Robert Bradshaw, David Harvey, Robert Miller, Emily Kirkman, Martin Albrecht, Michael Abshoff, etc.) have a similar perspective.

On the other hand, I teach high school students for a while every summer (in SIMUW), as do other people like David Roe, and of course I teach undergraduate classes... This is why I put so much effort into co-authoring things like the Sage notebook, which exist mainly to make the functionality of Sage more accessible to a wider range of people.

So, I think there is a brewing tension between education and research amongst developers involved with the Sage project (and in my case in my own mind). Some observations:

1. The research part of the Sage project is thriving and getting sufficient funding independent of any connection with educational applications of Sage. It very very healthy right now.

2. There is a lot of potential benefit to education in having a tool like Sage, since Mathematica is quite expensive, closed, etc. It's good for humanity
for Sage to be genuinely useful in an educational context.

3. People working on Sage for research have very limited time, and it can be frustrating being regularly asked to do things by the education community that not only have nothing to do with research, but are even sometimes at odds with it.

4. It is vitally important for the Sage project to be both well organized and have a clear sense of direction, purpose and goals.

It might be a good idea if the people who are really interested in Sage being a great tool for *education*, would consider doing the
following:

(a) setting up a mailing list called sage-edu for development discussions related to Sage in education. I realize that we just got rid of sage-newbie, but that was for a different reason -- because people were posting sage-support questions there and not getting responses.

(b) Gather together the best education-related tools in some sort
of organized package. This could start with Geogebra. I don't know. The key
thing is that there is no expectation at all that the people into Sage mainly for research do much of anything related to this project. I hope one outcome of this project would be an spkg that when installed would make available lots of cool extra stuff, and of course I would be very supportive about server space, posting of spkg's etc. And when this gets some momentum and
quality behind it this spkg would be included standard in Sage.

Basically I'm suggesting that everyone interested in making Sage the ultimate educational tool get organized, figure out who really wants to put
in an insane amount of effort on this sort of thing, and put together a bunch of cool tools. Stop thinking you have to convince a bunch of us research-focused people to do the work or that your ideas are good -- you
don't -- your ideas are good; it's just that if we put a lot of time into them we won't have time for our research.

Make an spkg that will be trivial to install into Sage and extend its functionality. There is definitely sufficient interest in something like this
for education, there is great potential for funding, and potential for having a major positive impact on society. Thus I think people will emerge who will
want to take up this challenge. I just thing it's better if it can happen for a while unconstrained by the rules or prejudices of the "Sage Research" side
of this project.

In summary, please put a huge amount of effort into getting organized and putting together something polished and great, so I can later effortless assimilate it :-).

Benchmarketing: Modular Hermite Normal Form

2008-02-09T13:54:00.002-08:00

Two days ago there was no fast freely available open source implementation of computation of the Hermite Normal Form of a (square nonsingular) matrix. In fact the fastest implementations I know of -- in Gap, Pari, and NTL, are all massively slower (millions of times) than Magma. See Allan Steel's page on this algorithm.

I just spent the last few days with help from Clement Pernet and Burcin Erocal implementing a fast modular/p-adic Hermite Normal Form algorithm. As soon as the coefficients of the input matrix get at all large our implementation is now the fastest in the world available anywhere (e.g., faster than Magma, etc.). This is incredibly important for my research work on modular forms.

The following plot compares Sage (blue) to Magma (red) for computing the Hermite Normal Form of an nxn matrix with coefficients that have b bits. The x-axis is n, the y-axis is b, and the blue dots show where Sage is much better, whereas the red dots are where Magma is much better. The timings are on a 2.6Ghz core 2 duo laptop running OS X, and both Sage and Magma were built as 32-bit native executables:

(Note: When doing timings under Linux, Magma doing slightly better than it does above, though Sage is still much better as soon as the coefficients are at all large.)

This plot shows the timings of Magma (red) versus Sage (blue) for computing the Hermite Forms of matrices with entries between -2¹² and 2¹². Sage is much faster than Magma, since the blue line is lower (=faster).

For even bigger coefficients Sage has a much bigger advantage. E.g., for a 200 x 200 256-bit matrix, Magma takes 232 seconds whereas Sage takes only 55 seconds.

In order to make this happen we read some old papers, read notes from a talk that Allan Steel (who implemented HNF in Magma) gave, and had to think quite hard to come up with three tricks (2 of which are probably similar to tricks alluded to in Steel's talk notes, but with no explanation about how they work), coded for 3 days at Sage Days 7, discovered that we weren't right about some of our tricks, doing lots of fine tuning, and finally fixed all the problems and got everything to work. We will be writing this up, and of course all the code is open source.

Acknowledgement: Many many thanks to Allan Steel for implementing an HNF in Magma that blows away everything else, which gave us a much better sense of what is possible in practice. Thanks also to the authors of IML whose beautiful GPL'd implementation of balanced p-adic is critical to our fast HNF implementation.

Josh Kantor's Lorenz attractor example

2008-01-30T04:43:00.001-08:00

Josh posted a nice example of plotting a Lorenz attractor in Sage:

Put this in a notebook cell (be careful about newlines):


Integer = int
RealNumber = float

def lorenz(t,y,params):
    return [params[0]*(y[1]-y[0]),y[0]*(params[1]-y[2])- y[1],y[0]*y[1]-params[2]*y[2]]

def lorenz_jac(t,y,params):
    return [ [-params[0],params[0],0],[(params[1]-y[2]),-1,-y[0]],[y[1],y[0],-params[2]],[0,0,0]]

T=ode_solver()
T.algorithm="bsimp"
T.function=lorenz
T.jacobian=lorenz_jac
T.ode_solve(y_0=[.5,.5,.5],t_span=[0,155],params=[10,40.5,3],num_points=10000)
l=[T.solution[i][1] for i in range(len(T.solution))]

line3d(l,thickness=0.3, viewer='tachyon', figsize=8)

and this is what you get (click to zoom):

I'm glad I chose Python for Sage -- some cool scientific computing Python projects

2008-01-11T17:18:00.000-08:00

When brainstorming for talk ideas for a workshop, Fernando Perez came up with a bunch of random off-the-top of his head very high quality/impact scientific computing projects that involve Python. Here they are (the following was written by Fernando Perez, the author of IPython):

- I can obviously talk about ipython and related projects, but I can also give a math/technical talk off this type of work (the whole implementation is python, and uses quite a few tricks):

http://dx.doi.org/10.1016/j.acha.2007.08.001

- Brian Granger (from Tech-X http://txcorp.org) has a NASA grant to develop distributed arrays for Python, using IPython and numpy. That would make for an excellent talk, I think (matlab, interactivesupercomputing.com, and all the 'big boys' are after distributed arrays).

- Trilinos (http://trilinos.sandia.gov), a large set of parallel solvers developed at Sandia National Lab, has a great set of Python bindings (even usable interactively via ipython).

- MPI4Py is an excellent set of MPI bindings for Python, and its author Lisandro Dalcin is also the developer of Petsc4py:
* http://mpi4py.scipy.org/
* http://code.google.com/p/petsc4py/
If Lisandro can't come, I can contact one of the Petsc guys who's a great python developer and see if he's coming or can make it, he's an excellent speaker (Matt Knepley from Argonne Nat. Lab http://www-unix.mcs.anl.gov/~knepley/).

- The Hubble space telescope people are all pyhton based, and have done enormous amounts of work on both their internal image processing pipeline and contrbuting to Matplotlib (they have currently a developer working full time on matplotlib).

- The NetworkX (Sage uses this) guys from Los Alamos will probably be coming: https://networkx.lanl.gov/wiki.

- The Scripps institute has an extremely strong Python team doing molecular visualization and visual programming. Their work is very impressive, and they're already in San Diego, so it's a no brainer to attend. Their presentations are always of very high quality: http://mgltools.scripps.edu.

- JPL uses python extensively (they've contracted out work for matplotlib to be extended to suit their specific needs).

- My new job at UC Berkeley is on neuroscience, and we could present the work that's being developed there for fMRI analysis (all Python based, fully open source, NIH funded).

- Andrew Straw's work (http://www.its.caltech.edu/~astraw/) on real-time 3d tracking of fruit flies is very, very impressive. All python based, hardware control, real-time parallel computing.

- The CACR group at Caltech has the contract for DANSE (http://wiki.cacr.caltech.edu/danse/index.php/Main_Page), the Spallation Neutron Source's data analysis framework, all python. This is currently the largest experiment being funded in the USA.

AMS Meeting Day 2: The Competition

2008-01-07T20:42:00.000-08:00

Today I violated the Mathematica license agreement in front of Eric Weisstein (a famous Mathematica developer), I talked with the developers of Wiris (rhymes with virus) which is a commercial competitor to the Sage notebook, discussed Mupad with a longtime Mupad developer, and gave away $1000 of tutorials, DVD's, and other goodies at the Sage AMS exhibit booth.

There is a project called "Wiris", which I had never heard of until today. So Tom Boothby and I had a very interesting talk with the people at the Wiris Booth (http://www.wiris.com/). Wiris is a closed-source commercial math software company in Barcelona that makes a web-based interface to their own custom mathematical software (interestingly, one of their main developers took Calculus from Jordi Quer, who wrote a lot of modular-forms related code for Sage recently). Their primary audience and market right now is European Government Agencies who use their software for high school and beginning college education. Their software is much different than the Sage notebook, since it is written entirely in Java instead of being an AJAX javascript application. They knew about Sage and asked if it used OpenMath or MathML, and I explained that it didn't use either, that it shouldn't and that for our purposes (i.e., interfacing math software) those technologies do not solve the problems we have -- in fact, they are worse than useless. They said that us not taking the OpenMath route was disappointing. They ended the discussion by telling us that their web-based interface is much better than ours :-). I guess they were trying to intimidate us.

Eric Weisstein -- who told us that he is now an official Mathematica developer (doing graph theory among other things) in addition to his "Math World" came over to the Sage booth and asked a lot of pointed questions about Sage, mostly "how does this get funded?" We ended up talking for about an hour. There are numerous people at Mathematica who are well aware of Sage, and he claims he doesn't see Sage as a threat to Mathematica as a company. He said Mathematica has had a recent explosion in hiring as a result of greatly increased sales because of the new "Demonstrations" feature in Mathematica 6. We also talked a lot about graph theory and how Sage has a complete implementation of graph isomorphism testing, etc., which greatly impressed him (thanks Robert Miller!). Jason Grout asked about the Mathematica end use license agreement and Eric pleaded IANAL and I demonstrated using Mathematica via the Sage notebook -- all locally over localhost on a machine with a valid Mathematica license -- that this violates the Mathematica license. He got annoyed when I did a Mathematica graph through the Sage notebook... Later Eric talked about how he "hoped" Sage would continue to have momentum and not just die like other free projects. He gave Maxima as an example of a dead project, and seemed quite shocked when I mentioned that they are very much alive and have regular releases, etc. He then said that there is no such thing as free.

I met somebody from MuPad who has worked on that closed source project for a decade. They used to be a German national government funded project, then had an academic research branch until one year ago, and now are 100% commercial and private. I asked about their vision for the next 5 years, and he said "MuPad will survive", and said they were mainly happy to be stable. They also mentioned wanting to do more numerical and applied functionality.

I talked with a Unix guy who works on some Scientific Workplace. There is only a Windows version, and he is working on doing an OS X/Linux port, which they will finish "in the future"!

And that's just a little of what happened today...

AMS Meeting Part 1

2008-01-06T01:27:00.000-08:00

I am completely exhausted right now, having put in a huge amount of time with little sleep during the last few days writing 3d graphics code for Sage (with Robert Bradshaw), making the Sage-2.9.2 release (with Michael Abshoff), printing fliers, tutorials, and preparing DVDs (with my brother) for the massive joint AMS meeting where there will be a Sage exhibit booth.

Our booth with have a huge banner that says "Creating a viable free open source alternative to Magma, Maple, Mathematica, and Matlab."
An Austrian named Harald Schilly did most of the work creating this poster.

I have no clue what to expect during the next few days. I've never run an exhibit booth before; I'm a mathematician not a "vendor", and my product is free. This should be very interesting. I've been to numerous AMS meetings before, and every booth I remember is commercial... TI, book publishers, math games, Maple, Mathematica, etc.