Sage: Open Source Mathematics Software

BDFL?

noreply@blogger.com (William Stein) — Mon, 17 Dec 2012 17:00:00 +0000

I just read this blog post about the direction of numpy development, which might be of interest to Sage Developers. TL;DR -- Travis Oliphant explains that he is stepping down as head steward of Numpy, and then explains the awesome new things he's working on instead.

This made me think about my current relationship with the Sage project, where I'm similarly considered "head steward". I have not been super-active in the last few months in day-to-day Sage development, and haven't posted a lot on the lists. However, in my case, this is because I'm doing some hard work to build a company (Salvus) that may be able to provide more sustainable funding for core Sage development later. For example, yesterday, Drew Sutherland and I worked at an approach to implementing computation of q-expansions of higher weight modular forms (using modular symbols) which would be much, much faster than what's in Sage (or Magma) now. I'm not implementing it today, because I'm working on Salvus instead, so that hopefully in a year I will have all the time I need to implement exactly that algorithm and more in Sage, as a result of what I'm doing now. (Drew will implement a special case he needs for his research.)

Sage and Python 3?

noreply@blogger.com (William Stein) — Sat, 10 Mar 2012 15:57:00 +0000

Have you ever wondered how difficult it might be to switch Sage from Python 2.7 to Python 3.x? Some students in my Sage course made a webpage that summarizes the Python 3 support status of the Python packages on which Sage depends.

Interesting examples:

Matplotlib doesn't support Python 3.x at all yet.
Mercurial doesn't support Python 3.x, and they don't have any plans to do so. (Which is another point in favor switching Sage to GIT.)

How to get access to Magma

noreply@blogger.com (William Stein) — Thu, 08 Mar 2012 22:57:00 +0000

Despite Sage doing a lot, people still write to me asking about how to get access to Magma. Here is my advice:

You can buy a copy of Magma here for only $1180.
If your calculation will take less than 20 seconds (?), you can do it over the web for free. (Historical note: I wrote the first version of that website.)
In Sage, use the command magma_free('some string'), though I just checked and the Magma calculator has changed in a way that breaks this command again. I'll be posting a patch to fix this in Sage.
Most people I know who have Magma do not buy it, but get it in exchange for contributing to Magma (I used to get it free for that reason). Study the list of
past and current contributors to Magma and ask the one you know the best. This is a list of people who definitely have a copy of Magma and know how to use it.

How big is the core Sage library?

noreply@blogger.com (William Stein) — Thu, 15 Dec 2011 22:42:00 +0000

I just did the following with Sage-4.8.alpha5:

"sudo apt-get install sloccount".
"cp -rv SAGE_ROOT/devel/sage-main /tmp/x"
Use a script [1] to rename all .pyx and .pxi files to .py.
Ran "sloccount *" in the /tmp/x directory, which ignores autogenerated .c/.cpp files coming from Cython.

Here's the result for the full Sage library, which does not distinguish between Python and Cython. Note that sloccount really only counts lines of code -- comments are blank lines are ignored.

Totals grouped by language (dominant language first):
python:      530370 (96.41%)
ansic:        14538 (2.64%)
cpp:           5188 (0.94%)

This suggests that the core Sage library is just over a "half million lines of Python and Cython source code, not counting comments and whitespace".

Here's the breakdown by module:

SLOC    Directory       SLOC-by-Language (Sorted)
88903   rings           python=87720,cpp=1183
72913   combinat        python=71629,cpp=1284
47747   schemes         python=46255,cpp=1492
39815   graphs          python=28377,ansic=11438
31540   matrix          python=31540
31019   modular         python=31012,ansic=7
24475   libs            python=21171,ansic=2845,cpp=459
20517   misc            python=20383,ansic=134
18006   interfaces      python=18006
17577   geometry        python=16936,cpp=641
12775   categories      python=12775
12093   server          python=12093
11971   groups          python=11971
11961   plot            python=11961
10686   crypto          python=10686
9920    modules         python=9920
8389    symbolic        python=8260,cpp=129
8150    algebras        python=8150
7260    ext             python=7198,ansic=62
7093    structure       python=7093
6364    coding          python=6364
5670    functions       python=5670
5249    homology        python=5249
4798    numerical       python=4798
4323    quadratic_forms python=4323
3919    gsl             python=3919
3911    calculus        python=3911
3879    sandpiles       python=3879
3003    sets            python=3003
2647    databases       python=2647
2074    logic           python=2074
1736    finance         python=1736
1608    games           python=1608
1465    monoids         python=1465
1435    tests           python=1383,ansic=52
1370    stats           python=1370
971     interacts       python=971
959     tensor          python=959
906     lfunctions      python=906
308     parallel        python=308
275     probability     python=275
219     media           python=219
197     top_dir         python=197

Here is the script [1]:

#!/usr/bin/env python

import os, shutil

for dirpath, dirnames, filenames in os.walk('.'):
    for f in filenames:
        if f.endswith('.pyx') or f.endswith('.pxi'):
            print f
            shutil.move(os.path.join(dirpath, f),
                        os.path.join(dirpath, os.path.splitext(f)[0] + '.py'))

Using Sage to Support Research Mathematics

noreply@blogger.com (William Stein) — Tue, 13 Dec 2011 22:06:00 +0000

When using Sage to support research mathematics, the most important point to make is to strongly encourage people to do the extra work to turn their "scruffy research code" into a patch that can be peer reviewed and included in Sage. They will have to 100% doctest it, and the quality of their code may improve dramatically as a result. Including code in Sage means that the code will continue to work as Sage is updated. Also, the code is peer reviewed and has to have examples and documentation for every function. That's a much higher bar than just "reproducible research".

Moreover, getting code up to snuff to include in Sage will often also reveal mistakes that will avoid embarrassment later. I'm fixing some issues related to a soon-to-be-done paper right now that I found when doing just this for trac 11975.

This final step of turning snippets of research code into a peer-reviewed contribution to Sage is: (1) a surprisingly huge amount of very important useful work, (2) something that is emphasized as an option for Sage more than with Magma or Mathematica or Pari (say), (3) something whose value people have to be sold on, since they get no real extra academic credit for it, at present, usually, and journal referees often don't care either way (I do, but I'm probably in the minority there), and (4) something that a *lot* of research mathematicians do not do. As an example of (4), in the last two months I've seen a ton of (separate!) bodies of code which is all sort of secret research code in various Dropbox repos, and which isn't currently squarely aimed at going into Sage. I've also seen a bunch of code related to Edixhoven et al.'s algorithm for computing Galois representation with a similar property (there is now trac 12132, due to my
urging).

I did *not* do this step yet with this recently accepted paper. Instead I used "scrappy research code" in psage to do the fast L-series computations. The referee for Math Comp didn't care either way, actually... I hope this doesn't come back to haunt me, though there are many double checks here (e.g., BSD) so I'm not too worried. I will do this get-it-in-Sage step at some point though.

This will be better for the community in the long run, and better for individual researcher's credibility too. And there is a lot of value in having a stable refereed snapshot of code on which a published (=very stable) paper is based.

Is the time ripe for http://sagenb.com?

noreply@blogger.com (William Stein) — Sat, 12 Nov 2011 19:47:00 +0000

On a Sage mailing list, Karl Crisman wrote: "Regarding the downtime issue [of http://sagenb.org], there have occasionally been rumors of someone or some organization starting a service which would guarantee uptime and provide support."

I might do this. It might be at http://sagenb.com (right now sagenb.com points to sagenb.org). Here's the "business plan". Probably, sagenb.com would appear almost the same as sagenb.org, except there would be Google (?) ads on the side of your worksheets, and the revenue would go toward paying for:

Commercial server hosting: Some Amazon EC2 instances
An employee (or later, employees) to maintain the servers: at the beginning, this would be me in my free time, since I have a lot of experience with this.
Advertising that sagenb.com exists and we want users!: Unlike sagenb.org, we would very strongly encourage as many people as possible to use sagenb.com. The advertising and landing page would explain that though sagenb.com generates money, all that money is all given back to the Sage development community (see below).
Hire employees to improve the notebook: Fix bugs, implement features, etc. There would be a public commitment that all such work would be open sourced and get included with Sage. This would include adding support for a for-pay "pro" subscription version, adding nicer "offline support" (via a Sage install on the user's computer), integrated spreadsheets and better data visualization and manipulation tools for Science and business applications, and enabling development of Sage's core library and patches submission entirely through the notebook, etc.

At some point, there could be a $X/year subscription version that would remove all ads, and increase disk space available to that user. There would also be a $Y/year university site license version with customized authentication (e.g., LDAP?) for each university. The university site license version might also include Maple/Mathematica/Matlab/Magma pre-installed in their notebook server, assuming appropriate site licenses are honored, so sagenb.com could be something that goes beyond just a platform for "sage as math software". We can of course also tap into the R market, given that Sage includes R.

I imagine the above being done as a not-for-profit effort, so if it brought in a lot of revenue (e.g., more than needed for hosting and employees), excess money would go to the Sage Foundation to support other Sage development activities. Regarding numbers, according to Google Analytics, right now on average well over 1000 people use sagenb.org every day. Standard commercial hosting costs for EC2 to support this load would be roughly $100/month. If each visitor generates on average of 1 penny of ad revenue per day (is this a reasonable estimate -- I have no clue?), then we would expect to make $3,650 in one year, which would be enough to fund the EC2 service (at about $2000/year), with a profit of $1,650.

Now let's dream big! There might be 1,000,000 potential daily users out there for a service like this, if it worked sufficiently well, since there are many college students (and people that use math and stats programs like R in the sciences, and R is part of Sage) in the world. Scaling up by a factor of 1,000 would yield over $1 million/year, after paying for hosting fees. This would be enough to fund substantial work to improve Sage, the notebook, and have a paid Patch Editor position (imagine buying out a top Sage developer professor, e.g., John Palmierri, from 50% of his teaching obligations in exchange for him spending the time he would spend teaching instead organizing that the patches to Sage get properly refereed). Maybe we could even hire back some of the (many!) people who were Sage developers when they were mathematics grad student or postdocs, but who then went to work at a top web technology company and acquired useful experience there (and are now way too busy to work on Sage).

This has the potential to make Sage a more longterm self-sustaining project. It's probably not possible to get traditional venture capital for a not-for-profit plan like the one above, but fortunately that is not needed due to (1) the generous support the National Science Foundation is currently providing toward development on the Sage notebook, and (2) private donations to the Sage Foundation. In particular, (2) provides enough money to bootstrap a sagenb.com for a while.

I think the main potential downside is competition. If somebody else does the same thing right now for profit without giving back their changes, and captures the market it's hard to imagine how the above would work. Since we don't use the Affero GPL for the Sage notebook, it is legal for somebody to do a lot of customization work to Sage and notebook, create a web-app using this customized version, and give back nothing to the community, so long as they don't redistribute their modified versions publicly. This isn't crazy -- not so long ago, I had a major company (I won't say who out of respect) tell me they planed to do something like that. And "random people" suggest it somewhat regularly when I give talks about Sage. I'm surprised it hasn't happened yet, but it definitely hasn't.

So the time to do this is today. The notebook software we have is now finally reasonably scalable, primarily due to work of Mike Hansen and Rado Kirov. Our funding situation is good this year. We have strong good will and interest right now from both the Mathematical Association of America and WebWork developers. If we wait longer, the one chance to truly make Sage financially self-sustaining in a way that fits with my dreams and values will pass.

I hope that by making all plans open, and by having a commitment to put the profits back into Sage development, an enterprise like I describe here will be in a better position to attract users than a purely for profit venture by somebody else.

Sage: Creating a Viable Free Open Source Alternative to Magma, Maple, Mathematica, and MATLAB

noreply@blogger.com (William Stein) — Wed, 31 Aug 2011 17:06:00 +0000

The goal of the Sage project is to create a viable fre open source alternative to Magma, Maple(TM), Mathematica(R), and MATLAB(R), which are the most popular non-free closed source mathematical software systems. (Maple is a trademark of Waterloo Maple Inc. Mathematica is a registered trademark of Wolfram Research Incorporated. MATLAB is a registered trademark of MathWorks. I will refer to the four systems together as ``Ma'' in the rest of this article.) Magma is (by far) the most advanced non-free system for structured abstract algebraic computation, Mathematica and Maple are popular and highly developed systems that shine at symbolic manipulation, and MATLAB is the most popular system for applied numerical mathematics. Together there are over 3,000 employees working at the companies that produce the four Ma's listed above, which take in over a hundred million dollars of revenue annually.

By a viable free alternative to the Ma's, we mean a system that will have the important mathematical features of each Ma, with comparable speed. It will have 2d and 3d graphics, an interactive notebook-based graphical user interface, and documentation, including books, papers, school and college curriculum materials, etc. A single alternative to all of the Ma's is not necessarily a drop-in replacement for any of the Ma's; in particular, it need not run programs written in the custom languages of those systems. Thus it need not be like Octave or R, which (nearly) clone the languages of MATLAB and S, respectively. Development would instead focus on implementing functions that users demand, rather than systematically trying to implement every single function of the Ma's. The culture, architecture, and general look and feel of such a system would be very different than that of the Ma's.

Motivation for Starting Sage

Each of the Ma's cost substantial money, and is hence expensive for me, my collaborators, and students. The Ma's are not owned by the community like Sage is, or Wikipedia is, for that matter.

The Ma's are closed, which means that the implementation of some algorithms are secret, in which case you are not allowed to modify or extend them.

The Mathematica Documentation: "You should realize at the outset that while knowing about the internals of Mathematica may be of intellectual interest, it is usually much less important in practice than you might at first suppose. Indeed, in almost all practical uses of Mathematica, issues about how Mathematica works inside turn out to be largely irrelevant. Particularly in more advanced applications of Mathematica, it may sometimes seem worthwhile to try to analyze internal algorithms in order to predict which way of doing a given computation will be the most efficient. [...] But most often the analyses will not be worthwhile. For the internals of Mathematica are quite complicated.."

The philosophy espoused in Sage, and indeed by the vast open source software community, is exactly the opposite. We want you to know about the internals, and when they are quite complicated, we want you to help make them more understandable. Indeed, Sage's growth depends on you analyzing how Sage works, improving it, and contributing your improvements back.

sage: crt(2, 1, 3, 5)  # Chinese Remainder Theorem

    11 

    sage: crt?        # ? = documentation and examples

    Returns a solution to a Chinese Remainder Theorem...

    ...

    sage: crt??       # ?? = source code

    def crt(...):

    ...

        g, alpha, beta = XGCD(m, n)

        q, r = (b - a).quo_rem(g)

        if r != 0:

            raise ValueError("No solution ...")

        return (a + q*alpha*m) % lcm(m, n)

Moreover, by browsing the Mercurial repository, you can see exactly who wrote or modified any particular line of code in the Sage library, when they did it, and why. Everything included in Sage is free and open source, and it will foreover remain that way.

Linus Torvalds: "I see open source as Science. If you don't spread your ideas in the open, if you don't allow other people to look at how your ideas work and verify that they work, you are not doing Science, you are doing Witchcraft. Traditional software development models, where you keep things inside a company and hide what you are doing, are basically Witchcraft. Open source is all about the fact that it is open; people can actually look at what you are doing, and they can improve it, and they can build on top of it. [...] One of my favorite quotes from history is Newton: `If I had seen further, it has been by standing on the shoulders of giants.'"

The design decisions of the Ma's are not made openly by the community. In contrast, important decisions about Sage development are made via open public discussions and voting that is archived on public mailing lists with thousands of subscribers.

Every one of the Ma's uses a special mathematics-oriented interpreted programming language, which locks you into their product, makes writing some code outside mathematics unnecessarily difficult, and impacts the number of software engineers that are experts at programming in that language. In contrast, the user language of Sage is primarily the mainstream free open source language Python, which is one of the world's most popular interpreted programming languages. The Sage project neither invented nor maintains the underlying Python language, but gains immediate access to the IPython shell, Python scientific libraries (such as NumPy, SciPy, CVXopt and MatPlotLib), and a large Python community with major support from big companies such as Google. In comparison to Python, the Ma's are small players in terms of language development. Thus for Sage most of the problems of language development are handled by someone else.

The bug tracking done for three of four of the Ma's is currently secret (MATLAB has an open bug tracker, though it requires free registration to view.), which means that there is no published accounting of all known bugs, the status of work on them, and how bugs are resolved. But the Ma's do have many bugs; see the release notes of each new version, which lists bugs that were fixed. Sage also has bugs, which are all publicly tracked at the trac server, and there are numerous ``Bug Days'' workshops devoted entirely to fixing bugs in Sage. Moreover, all discussion about resolving a given bug, including peer review of solutions, is publicly archived. We note that sadly even some prize winning free open source systems, such as GAP, do not have an open bug tracking system, resulting in people reporting the same bugs over and over again.

Each of the Ma's is a combination of secret unchangeable compiled code and less secret interpreted code. Users with experience programming in compiled languages such as Fortran or C++ may find the loss of a compiler to be frustrating. None of the Ma's has an optimizing compiler that converts programs written in their custom interpreted language to a fast executable binary format that is not interpreted at runtime. (MATLAB has a compiler, but ``the source code is still interpreted at run-time, and performance of code should be the same whether run in standalone mode or in MATLAB.'' Mathematica also has a Compile function, but simply compiles expressions to a different internal format that is interpreted, much like Sage's fast_callable function.) In contrast, Sage is tightly integrated with Cython. The Cython project has received extensive contributions from Sage developers, and is very popular in the world of Python-based scientific computing. Cython is a Python-to-C/C++ compiler that speeds up code execution and has support for statically declaring data types (for potentially enormous speedups) and natively calling existing C/C++/Fortran code. For example, enter the following in a cell of the Sage notebook:

def python_sum2(n):

    s = int(0)

    for i in xrange(1, n+1):

        s += i*i

    return s

Then enter the following in another cell:

%cython

def cython_sum2(long n):

    cdef long i, s = 0

    for i in range(1, n+1):

        s += i*i

    return s

The second implementation, despite looking nearly identical, is nearly a hundred times faster than the first one (your timings may vary).

sage: timeit('python_sum2(2*10^6)')

5 loops, best of 3: 154 ms per loop

sage: timeit('cython_sum2(2*10^6)')

125 loops, best of 3: 1.76 ms per loop

sage: 154/1.76

87.5

Of course, it is better to choose a different algorithm. In case you don't remember a closed form expression for the sum of the first $n$ squares, Sage can deduce it:

sage: var('k, n')

sage: factor(sum(k^2, k, 1, n))

1/6*(n + 1)*(2*n + 1)*n

And now our simpler fast implementation is:

def sum2(n):

    return n*(2*n+1)*(n+1)/6

Just as above, we can also use the Cython compiler:

%cython

def c_sum2(long n):

    return n*(2*n+1)*(n+1)/6

Comparing times, we see that Cython is 10 times faster:

sage: n = 2*10^6

sage: timeit('sum2(n)')

625 loops, best of 3: 1.41 microseconds per loop

sage: timeit('c_sum2(n)')

625 loops, best of 3: 0.145 microseconds per loop

sage: 1.41/.145

9.72413793103448

In this case, the enhanced speed comes at a cost, in that the answer is wrong when the input is large enough to cause an overflow:

sage: c_sum2(2*10^6)   # WARNING: overflow

-407788678951258603

Cython is very powerful, but to fully benefit from it, one must understand machine level arithmetic data types, such as long, int, float, etc. With Sage you have that option.

What is Sage?

The goal of Sage is to compete with the Ma's, and the intellectual property at our disposal is the complete range of GPL-compatibly licensed open source software.

Sage is a self-contained free open source distribution of about 100 open source software packages and libraries that aims to address all computational areas of pure and applied mathematics. See the list of packages in Sage, which includes R, Pari, Singular, GAP, Maxima, GSL, Numpy, Scipy, ATLAS, Matplotlib, and many other popular programs. The download of Sage contains all dependencies required for the normal functioning of Sage, including Python itself. Sage includes a substantial amount of code that provides a unified Python-based interface to these other packages. Sage also includes a library of new code written in Python, Cython and C/C++, which implements a huge range of algorithms.

History

I made the first release of Sage in February 2005, and at the time called it "Software for Arithmetic Geometry Experimentation." I was a serious user of, and contributor to, Magma at the time, and was motivated to start Sage for many of the reasons discussed above. In particular, I was personally frustrated with the top-down closed development model of Magma, the fact that several million lines of the source code of Magma are closed source, and the fees that my colleagues had to pay in order to use the substantial amount of code that I contributed to Magma. Despite my early naive hope that Magma would be open sourced, it never was. So I started Sage motivated by the dream that someday the single most important item of software I use on a daily basis would be free and open. David Joyner, David Kohel, Joe Wetherell, and Martin Albrecht were also involved in the development of Sage during the first year.

In February 2006, the National Science Foundation funded a 2-day workshop called ``Sage Days 2006'' at UC San Diego, which had about 40 participants and speakers from several open and closed source mathematical software projects. After doing a year of fulltime mostly solitary work on Sage, I was surprised by the positive reception of Sage by members of the mathematical research community. What Sage promised was something many mathematicians wanted. Whether or not Sage would someday deliver on that promise was (and for many still is) an open question.

I had decided when I started Sage that I would make it powerful enough for my research, with or without the help of anybody else, and was pleasantly surprised at this workshop to find that many other people were interested in helping, and understood the shortcomings of existing open source software, such as GAP and PARI, and the longterm need to move beyond Magma. Six months later, I ran another Sage Days workshop, which resulted in numerous talented young graduate students, including David Harvey, David Roe, Robert Bradshaw, and Robert Miller, getting involved in Sage development. I used startup money from University of Washington to hire Alex Clemesha as a fulltime employee to implement 2d graphics and help create a notebook interface to Sage. I also learned that there was much broader interest in such a system, and stopped referring to Sage as being exclusively for ``arithmetic geometry''; instead, Sage became ``Software for Algebra and Geometry Experimentation.'' Today the acronym is deprecated.

The year 2007 was a major turning point for Sage. Far more people got involved with development, we had four Sage Days workshops, and prompted by Craig Citro, we instituted a requirement that all new code must have tests for 100% of the functions touched by that code, and every modification to Sage must be peer reviewed. Our peer review process is much more open than in mathematical research journals; everything that happens is publicly archived on trac. During 2007, I also secured some funding for Sage development from Microsoft Research, Google, and NSF. Also, a German graduate student studying cryptography, Martin Albrecht presented Sage at the Troph'ees du Libre competition in France, and Sage won first place in ``Scientific Software'', which led to a huge amount of good publicity, including articles in many languages around the world and appearances, for example, this Slashdot article.

In 2008, I organized 7 Sage Days workshops at places such as IPAM (at UCLA) and the Clay Mathematics Institute, and for the first time, several people besides me made releases of Sage. In 2009, we had 8 more Sage Days workshops, and the underlying foundations of Sage improved, including development of a powerful coercion architecture. This coercion model systematically determines what happens when performing operations such as a + b, when a and b are elements of potentially different rings (or groups, or modules, etc.).

sage: R. = PolynomialRing(ZZ)

    sage: f = x + 1/2; f

    x + 1/2

    sage: parent(f)

    Univariate Polynomial Ring in x over Rational Field

We compare this with Magma (V2.17-4), which has a more ad hoc coercion system:

> R := PolynomialRing(IntegerRing());

    > x + 1/2

        ^

    Runtime error in '+': Bad argument types

    Argument types given: RngUPolElt[RngInt], FldRatElt

Robert Bradshaw and I also added support for beautiful browser-based 3D graphics to Sage, which involved writing a 3D graphics library, and adapting the free open source JMOL Java library for rendering molecules to instead plot mathematical objects.

sage: f(x,y) = sin(x - y) * y * cos(x)

    sage: plot3d(f, (x,-3,3), (y,-3,3), color='red')

In 2009, following a huge amount of porting work by Mike Hansen, development of algebraic combinatorics in Sage picked up substantial momentum, with the switch of the entire MuPAD-combinat group to Sage (forming sage-combinat), only months before the formerly free system MuPAD{\textregistered}\footnote{MuPAD is a registered trademark of SciFace Software GmbH \& Co.} was bought out by Mathworks (makers of MATLAB). In addition to work on Lie theory by Dan Bump, this also led to a massive amount of work on a category theoretic framework for Sage by Nicolas Thiery.

In 2010, there were 13 Sage Days workshops in many parts of the world, and grant funding for Sage significantly improved, including new NSF funding for undergraduate curriculum development. I also spent much of my programming time during 2010--2011 developing a number theory library called psage, which is currently not included in Sage, but can be easily installed.

Many aspects of Sage make it an ideal tool for teaching mathematics, so there's a steadily growing group of teachers using it: for example, there have been MAA PREP workshops on Sage for the last two years, and a third is likely to run next summer, there are regular posts on the Sage lists about setting up classroom servers, and there is an NSF-funded project called UTMOST devoted to creating undergraduate curriculum materials for Sage.

The publications page lists 101 accepted publications that use Sage, 47 preprints, 22 theses, and 16 books, and there are surely many more ``in the wild'' that we are not aware of. According to Google Analytics, the main Sage website gets about 2,500 absolute unique visitors per day, and the website http://sagenb.org, which allows anybody to easily use Sage through their web browser, has around 700 absolute unique visitors per day.

For many mathematicians and students, Sage is today the mature, open source, and free foundation on which they can build their research program.

Brief History and Motivation Behind the Sage Coercion Model

noreply@blogger.com (William Stein) — Mon, 15 Nov 2010 17:15:00 +0000

In Sage (like in Magma), most objects are either elements or parents. Think of a "parent" as a set. This Parent/Element idea is a powerful algebraic approach to implementing mathematical objects on a computer, which does not exist in Mathematica, Maple, PARI, Maxima, and many other math software platforms.

I learned about this approach from using Magma:

%magma
R<x> := PolynomialRing(Integers());
print Parent(x);
///
Univariate Polynomial Ring in x over Integer Ring

(In this blog post I'll put %magma above code that gets input to Magma; all other code gets input to Sage. The input and output is separated by ///.)

In Sage:

R.<x> = ZZ[]
parent(x)
///
Univariate Polynomial Ring in x over Integer Ring

x.parent()
///
Univariate Polynomial Ring in x over Integer Ring

isinstance(ZZ, Parent)
///
True

isinstance(2, Parent)
///
False

Automatic Coercions:

"The primary goal of coercion is to be able to transparently do arithmetic, comparisons, etc. between elements of distinct parents."

When I used to try to get people to use Magma, perhaps the number one complaint I heard about Magma was that doing arithmetic with objects having distinct parents was difficult and frustrating.

For the first year, in Sage, there was a very simple coercion system:

If you try to compute a + b or a * b, first somehow put b into the parent of a, then do the arithmetic.

That seriously sucked. E.g.,

Mod(2,7) + 6

was completely different than

6 + Mod(2,7)!

The first was Mod(1,7), and the second was the integer 8. This makes understanding code difficult and unpredictable.

So I rewrote coercion to be a bit better (this was a really painful rewrite that I mostly did myself over several hard months of work):

If you try to compute a + b (or a*b), check for a "canonical coercions" from the parent of a into b, or failing that, from the parent of b into a. If there aren't any raise an error. If there is one, use it. There won't be both unless there is some canonical isomorphism.
There are some axioms about what a canonical coercion is. At least it is homomorphism.

Then we decided that there is a canonical homomorphism Z --> Z/7Z, but there is not one Z/7Z --> Z since there is no ring homomorphism in this direction, hence the above makes sense in either order.

One implication of this new model was that parent objects have to be immutable, i.e., you can't fundamentally change them after you make them. This is why in Sage you must specify the name of the generator of a polynomial ring at creation time, and can't change it. In Magma, it is typical to specify the name only later if you want.

Objects must be immutable because the canonical maps between them depend on the objects themselves, and we don't want them to just change left and right at runtime.

%magma
R := PolynomialRing(RationalField(), 2);
f := R.1^3 + 3*R.2^3 - 4/5;
print f;
///
$.1^3 + 3*$.2^3 - 4/5
[ $.1, $.2 ]

%magma
AssignNames(~R, ["x", "y"]);
print f;
[R.1, R.2]
///
x^3 + 3*y^3 - 4/5
[x, y]

%magma
AssignNames(~R, ["z", "w"]);
print f;
///
z^3 + 3*w^3 - 4/5

Now in Sage:

R = PolynomialRing(QQ)
///
TypeError: You must specify the names of the variables.

R.<x,y> = PolynomialRing(QQ)
f = x^3 + 3*y^3 - 4/5; f
///
x^3 + 3*y^3 - 4/5

Note: In Sage, you can can use a with block to temporarily change the names if you really need to for some reason. This is allowed since at the end of the with block the names are guaranteed to be changed back.

with localvars(R, ['z','w']):
    print f
print "back?", f    
///
z^3 + 3*w^3 - 4/5
back? x^3 + 3*y^3 - 4/5

But this new model had a major problem too, e.g., if x in Z[x] then "x + 1/2" would FAILS! This is because 1/2 does not coerce into Z[x] (the parent of x), and x does not coerce into Q (the parent of 1/2).

Maybe the implementors of Magma have the answers? Evidently not.

%magma
R<x> := PolynomialRing(Integers());
x + 1/2;
///
Runtime error in '+': Bad argument types
Argument types given: RngUPolElt[RngInt], FldRatElt

Robert Bradshaw did though, and now it is in Sage:

R.<x> = ZZ[]
x + 1/2
///
x + 1/2

His new design is (for the most part) what Sage actually uses now.

He launched an effort in 2008 (see the Dev Days 1 Wiki) to implement a rewrite of the coercion model to his new design. This ended up swallowing up half the development effort at the workshop, and was a massive amount of work, since every parent structure and element had to have some modifications made to it.

This meant people changing a lot of code all over Sage that they didn't necessarily understand, and crossing their fingers that the doctest test suite would catch their mistakes. This was SCARY. After much work, none of this went into Sage. It was just way too risky. This failure temporarily (!) burned out some developers.

Robert Bradshaw, on the other hand, persisted and came up with a new approach that involved migrating Sage code gradually. I.e., he made it so that the old coercion model was still fully supported simultaneously with the new one, then he migrated a couple of parent structures, and got the code into Sage. I'm sure not everything is migrated, even today. There are two points to what he did:

He extended the rules so x + 1/2 works, i.e., the result of a+b need not live in the parent of a or the parent of b.
He made implementing coercion much more top down: simply implement various methods in a class that derives from Parent. This meant that instead of coercion being rules and conventions that people have to understand and implement in their own code all over Sage, they just implement a small amount of code and the rules (and benefits) are all enforced automatically.

The Coercion Model

The coercion model is explained here: http://sagemath.org/doc/reference/coercion.html

Getting Started With Cython

noreply@blogger.com (William Stein) — Mon, 08 Nov 2010 18:05:00 +0000

Getting Started With Cython

Quote about Cython:

Andrew Tipton says "I'm honestly never going back to writing C again. Cython gives me all the expressiveness of Python combined with all the performance and close-to-the-metal-godlike-powers of C. I've been using it to implement high-performance graph traversal and routing algorithms and to interface with C/C++ libraries, and it's been an absolute amazing productivity boost." Yep.

Cython has two major use cases

Extending the CPython interpreter with fast compiled modules,
Interfacing Python code with external C/C++ libraries.

Cython supports type declarations

For changing code from having dynamic Python semantics into having static-and-fast (but less generic) C semantics.
Directly manipulating C data types defined in external libraries.

Tutorial: Building Your First Cython Code by Hand

It happens in two stages:

A .pyx file is compiled by Cython to a .c or .cpp file.
The .c or .cpp file is compild by a C compiler (such as GCC) to a .so file.

Let's try it now:
First, create a file sum.pyx that contains the following code (see this directory for original code files):

def sum_cython(long n):
    cdef long i, s = 0
    for i in range(n):
        s += i
    return s

Then use Cython to compile it:

Since we're using Sage, you can do

bash$ sage -cython sum.pyx
bash$ ls
sum.c  sum.pyx

Notice the new file sum.c. Compile it with gcc as follows on OS X:

bash$ sage -sh
bash$ gcc -I$SAGE_ROOT/local/include/python2.6 -bundle -undefined dynamic_lookup sum.c -o sum.so

On Linux, do:

bash$ sage -sh
bash$ gcc -I$SAGE_ROOT/local/include/python2.6 -shared -fPIC sum.c -o sum.so

Finally, try it out.

You must run Sage from the same directory that contains the file sum.so. When you type import sum below, the Python interpreter sees the file sum.so, opens it, and it contains functions and data that define a compiled "Python C-extension module", so Python can load it (like it would like a module like sum.py).

bash$ sage
-------------------------------------------------
| Sage Version 4.6, Release Date: 2010-10-30     
| Type notebook() for the GUI, and license() for
-------------------------------------------------
sage: import sum
sage: sum.sum_cython(101)
5050
sage: timeit('sum.sum_cython(101)')
625 loops, best of 3: 627 ns per loop
sage: timeit('sum.sum_cython(101)', number=10^6)    # better quality timing
1000000 loops, best of 3: 539 ns per loop

Finally, take a look at the (more than 1000 line) autogenerated C file sum.c:

bash$ wc -l sum.c
    1178 sum.c
bash$ less sum.c

...

Notice code like this, which illustrates that Cython generates code that supports both Python2 and Python3:

#if PY_MAJOR_VERSION < 3
  #define __Pyx_BUILTIN_MODULE_NAME "__builtin__"
#else
  #define __Pyx_BUILTIN_MODULE_NAME "builtins"
#endif

#if PY_MAJOR_VERSION >= 3
  #define Py_TPFLAGS_CHECKTYPES 0
  #define Py_TPFLAGS_HAVE_INDEX 0
#endif

The official Python docs say: "If you are writing a new extension module, you might consider Cython. It translates a Python-like language to C. The extension modules it creates are compatible with Python 3.x and 2.x."

If you scroll down further you'll get past the boilerplate and see the actual code:

...
  /* "/Users/wstein/edu/2010-2011/581d/notes/2010-11-08/sum.pyx":2
 * def sum_cython(long n):
 *     cdef long i, s = 0             # <<<<<<<<<<<<<<
 *     for i in range(n):
 *         s += i
 */
  __pyx_v_s = 0;

  /* "/Users/wstein/edu/2010-2011/581d/notes/2010-11-08/sum.pyx":3
 * def sum_cython(long n):
 *     cdef long i, s = 0
 *     for i in range(n):             # <<<<<<<<<<<<<<
 *         s += i
 *     return s
 */
  __pyx_t_1 = __pyx_v_n;
  for (__pyx_t_2 = 0; __pyx_t_2 < __pyx_t_1; __pyx_t_2+=1) {
    __pyx_v_i = __pyx_t_2;

    /* "/Users/wstein/edu/2010-2011/581d/notes/2010-11-08/sum.pyx":4
 *     cdef long i, s = 0
 *     for i in range(n):
 *         s += i             # <<<<<<<<<<<<<<
 *     return s
 */
    __pyx_v_s += __pyx_v_i;
  }
...

There is a big comment that shows the original Cython code with context and a little arrow pointing at the current line (these comment blocks with context were I think the first thing I personally added to Pyrex... before, it just gave that first line with the .pyx filename and line number, but nothing else). Below that big comment, there is the actual C code that Cython generates. For example, the Cython code s += i is turned into the C code __pyx_v_s += __pyx_v_i;.

The Same Extension From Scratch, for Comparison

If you read Extending and Embedding Python you'll see how you could write a C extension module from scratch that does the same thing as sum.so above. Let's see what this is like, for comparison. Given how simple sum.pyx is, this isn't so hard. When creating more complicated Cython code---e.g., new extension classes, more complicated type conversions, and memory management---writing C code directly quickly becomes unwieldy.
First, create a file sum2.c as follows:

#include <Python.h>

static PyObject * 
sum2_sum_c(PyObject *self, PyObject *n_arg)
{
    long i, s=0, n = PyInt_AsLong(n_arg);
    
    for (i=0; i<n; i++)  {
 s += i;
    }
    PyObject* t = PyInt_FromLong(s);
    return t;
}

static PyMethodDef Sum2Methods[] = {
    {"sum_c", sum2_sum_c, METH_O, "Sum the numbers up to n."},
    {NULL, NULL, 0, NULL} /* Sentinel */
};

PyMODINIT_FUNC
initsum2(void)
{
    PyObject *m;
    m = Py_InitModule("sum2", Sum2Methods);
}

Now compile and run it as before:

bash$ sage -sh

bash$ gcc -I$SAGE_ROOT/local/include/python2.6 -bundle -undefined dynamic_lookup sum2.c -o sum2.so 
bash$ sage
...
sage: import sum2
sage: sum2.sum_c(101)
5050
sage: import sum
sage: sum.sum_cython(101)
5050
sage: timeit('sum.sum_cython(1000000r)')
125 loops, best of 3: 2.54 ms per loop
sage: timeit('sum2.sum_c(1000000r)')
125 loops, best of 3: 2.03 ms per loop

Note that this is a little faster than the corresponding Cython code. This is because the Cython code is more careful, checking various error conditions, etc.

Note that the C code is 5 times as long as the Cython code.

Building Extensions using Setuptools Instead

In nontrivial projects, the Cython step of transforming your code from .pyx to .c is typically done by explicitly calling cython somehow (this will change in the newest version of Cython), but the step of running the C compiler is usually done using either distutils or setuptools. To use the tools, one creates a file "setup.py" which defines the extensions in your project, and Python itself then runs a C compiler for you, with the proper options, includes paths, etc.

Let's create a new setuptools project that includes the sum and sum2 extensions that we defined above. First, create the following file and call it setup.py. This should be in the same directory as sum.c and sum2.c.

from setuptools import setup, Extension

ext_modules = [
    Extension("sum", ["sum.c"]),
    Extension("sum2", ["sum2.c"])
    ]

setup(
    name = 'sum',
    version = '0.1',
    ext_modules = ext_modules)

Then type

bash$ rm *.so  # make sure something happens
bash$ sage setup.py develop
...
bash$ ls *.so
sum.so sum2.so

Notice that running

setup.py develop

resulted in Python generating the right gcc commmand lines for your platform. You don't have to do anything differently on Linux, OS X, etc.

If you change sum2.c, and want to rebuild it, just type sage setup.py develop again to rebuild sum2.so If you change sum.pyx, you have to manually run Cython:

sage -cython sum.pyx

then again do sage setup.py develop to rebuild sum.so. Try this now. In sum.pyx, change

for i in range(n):

for i in range(1,n+1):

then rebuild:

bash$ sage -cython sum.pyx
...
bash$ sage setup.py develop
...
bash$ sage
...
sage: import sum
sage: sum.sum_cython(100)
5050

There are ways to make setup.py automatically notice when sum.pyx changes, and run Cython. A nice implementation of this will be in the next Cython release. See the setup.py and build_system.py files of Purple sage for an example of how to write a little build system write now (before the new version of Cython).

An Automated Way to Experiment

Given any single Cython file such as sum.pyx, in Sage you can do

sage: load sum.pyx
Compiling sum.pyx...
sage: sum_cython(100)
5050

Behind the scenes, Sage created a setup.py file, ran Cython, made a new module, compiled it, and imported everything it defines into the global namespace. If you look in the spyx subdirectory of the directory listed below, before you exit Sage (!), then you'll see all this.

sage: SAGE_TMP
'/Users/wstein/.sage//temp/deep.local/14837/'

You can also do

sage: attach sum.pyx

Then every time sum.pyx changes, Sage will notice this and reload it. This can be useful for development of small chunks of Cython code.

You can also use the Sage notebook, and put %cython as the first line of a notebook cell. The rest of the cell will be compiled exactly as if it were written to a .pyx file and loaded as above. In fact, that is almost exactly what happens behind the scenes.

Next Time

Now that we understand at a reasonably deep level what Cython really is and does, it is time to learn about the various constructs of the language:

How to create extension classes using Cython.
How to call external C/C++ library code.

We will rewrite our sum.pyx file first to use a class. Then we'll rewrite it again to make use of the MPIR (or GMP) C library for arithmetic, and again to make use of the C++ NTL library.

Cython, Sage, and the Need for Speed

noreply@blogger.com (William Stein) — Wed, 03 Nov 2010 16:54:00 +0000

Cython seriously rocks, at least for much of what I need. It's still the killer feature of Python/Sage, IMHO. And meetings like EuroScipy last summer really confirmed that, where almost every other talk used Cython.

History

Greg Ewing wrote "Pyrex" in 2002--2004..., which I guess he named
after some cooking ware. It is amazing, but to understand this you
must take a quick tour of Extending and embedding and the Python/C API reference. Pyrex let you write basically Python-ish code that gets magically turned into C extension code.

In 2007 I forked it (discuss why briefly) and named Cython after this punk rock guy.

At that time, Robert Bradshaw and Stefen Behnel spent a lot of time improving Cython, implementing tons of _optimizations_ and new features.

Cython is now very popular in the "Scientific computing using Python" world. It is also heavily used in Sage.

Are You Serious?

If you want to use a computer for math research, and you are serious (not some lazy person who fiddles then gives up), you will likely run into situations where you need code to run fast. Writing such code only in Python (or any other interpreter) is often impossible.

If you want to write fast code on a computer, and don't want to mess with assembler, the only option right now is C, or something with equivalent speed... Cython! By "fast" I mean 100-1000 times what you'll get out of Python on certain tasks. I also mean code that is evil, scary, and dangerous... if you aren't careful with preconditions.

Compiled versus Interpreted Code

Here's how interpreter code usually runs.

    1. Check a bunch of conditions then do one single thing.
    2. Check a bunch of conditions then do one single thing.
    ...
    10^6. Check a bunch of conditions then do one single thing.

Here's how compiled (C, Cython, etc.) can can be written:

    1. Check some conditions (optional, but a good idea);
    2. Do very unsafe stuff with no checks at all (but they 
       in theory should be safe given 1).
    ...
    10^6. Do very unsafe stuff with no checks at all (but they 
       in theory should be safe given 1).

The problem is that all the checks in step 1 (in either case) can easily take over 100 times as long as "do very unsafe stuff".

TYPICAL EXAMPLE:

sage: def sum_sage(n):
...       s = 1
...       for i in range(n):
...           s += i
...       return s
sage: timeit('sum_sage(100000r)')
5 loops, best of 3: 84.6 ms per loop
sage: %python
sage: def sum_python(n):
...       s = 1
...       for i in range(n):
...           s += i
...       return s    
sage: 84.6/5.88
14.3877551020408
sage: timeit('sum_python(100000r)')
125 loops, best of 3: 5.88 ms per loop
sage: %cython
sage: def sum_cython(int n):
...       cdef int i, s = 1
...       for i in range(n):
...           s += i
...       return s
sage: timeit('sum_cython(100000r)')
625 loops, best of 3: 61.6 µs per loop
sage: 5.88 / 0.061
96.3934426229508

Let me explain what's going in the above. How, e.g., in the first one (sum_sage), the program is doing a sort of monologue: "I have to add a Python int to a Sage int. I don't have any code to do that directly (that would get too complicated, and they are so big and complicated and different objects, and they might change, oh my). So I'll convert the Python int to Sage int, because that's the only conversion I know. OK, I do that via (it used to be base 10 string parsing!) some code Gonzalo Tornaria wrote that is scary complicated... and once that is done, I got my new MPIR-based Sage integer, which I think add to s. The addition takes some memory that points to the two MPIR integers, and since Python numbers are supposed to be immutable, I make yet another MPIR number (wrapped in a Python object), which is the result of asking MPIR to add them. MPIR numbers are also very complicated objects, involving stuff like limbs, and C structs, which hardly anybody fully understands. Despite these integers happening to be small, there is still quite some overhead in the addition, but it happens (taking a small fraction of the total runtime). Then we move on to the next step in the loop!"

With sum_python, the loop is similar, but MPIR isn't involved, and there are no conversions. This buys a 14-fold speedup. But it is still not super fast, since many new Python objects get created, the code is for "potentially huge integers", hence a potentially complicated data structure has to be checked for, etc.

With sum_cython, the integers are only C ints, which are a 32 or 64-bit location in memory. Doing "s += i" just modifies in place that position in memory. There's no conversions or type checks done at all at run time. It's really fast... 1386 times faster than the first version!!!

Key point: If you truly understand what is going on, you'll see that this isn't Sage being fundamentally broken. Instead, you'll hopefully be able to look at a block of Sage code and have a clue about how to figure out what it is really doing in order to see whether writing a new implementation of the same algorithm using Cython (which will likely mean directly working with C level data structures) is likely to give you a big speedup. If you look at the innermost statement in a loop, and there's a big monologue about what is really going on, then you might get a 1000-fold speedup by using Cython.

In mathematics, general theorems -- once we have them -- are almost always much better than proofs of special cases. In math, proving a special case can often seem more awkward and unnatural than proving the general case (e.g., how would you proof that ever integer of the form a^2 + 7*a + 5 factors uniquely as a product of primes!?). With general theorems in math, the statements are often simple and clear so applying them is easier than applying theorems that are only about some very special case, which has often more elaborate hypothesis. In mathematics, usually a general theorem is simply all around much better than a theorem about some very special cases (especially if both are available).

In contrast, when writing computer programs, algorithms to solve very general cases of problems often have significant drawbacks in terms of speed (and sometimes complexity) over algorithms for special cases. Since you are mathematicians, you should constantly guard against your instincts from math research which can point you in exactly the wrong direction for writing very fast code. Often implementations of very general algorithms _are_ easier to understand, and are much less buggy than a bunch of implementations of special cases. However, there are also usually very severe performance penalties in implementing only the general case. Watch out.

A huge part of understanding the point of Cython for writing fast math code is that you must accept that you're going to write a lot of "ugly" (from a mathematicians perspective) code that only deals with special cases. But it's beautiful from the perspective of somebody who absolutely needs fast code for a specific research application; your fast code can lead to whole new frontiers of research.

Continuing the example from above:

sage: sum_python(10^8)
4999999950000001
sage: sum_cython(10^8)
887459713

Yep, we just implemented only a special case in Cython!

---------------

Useful things to do if you want Cython enlightenment (all at once, no order):

Definitely read/skim Extending and try all examples. This is critical if you want to understand Cython with any depth at all. Don't think: I don't need to know any of this, because I have Cython. Yes, after you play with this a bit you may never explicitly use it. But you do need to know it.
Oh, definitely learn the C language if you haven't already. This is
the book. There are courses. It's crazy not to learn C, anyways, since it (along with C++) is hugely popular, and a massive amount of code is written in C/C++. (See, e.g., http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html where C and C++ together are the most popular, by a long margin.)
Obviously, read http://docs.cython.org/ until it is burned into your brain.

Look at the code that Cython generates (use "cython -a" for a nice HTML view).

How to Referee Sage Trac Tickets

noreply@blogger.com (William Stein) — Mon, 01 Nov 2010 05:23:00 +0000

The current workflow and tools for peer review in Sage are not perfect, and it's clear they can be improved in many ways. However, the current system is also stable and works well, and though it will surely evolve over time, it is well worth learning. This post is about the current Sage peer review workflow. I will restrict my discussion to tickets that involve the Sage library, not standard or optional packages or other scripts not in the Sage library.

Why Referee a Ticket?

There are a couple of reasons that you might referee a ticket:

You want to contribute to Sage development, but don't know where to start. There's a list right here of about 200 tickets (sorted by component) that need review, and probably some require only background you know something about.
You want a specific chunk of code to get into Sage that somebody else wrote. If you care about this code, you are probably qualified to review it.
Somebody asked you to review a certain ticket, perhaps in exchange for them reviewing one of your tickets.

Refereeing trac tickets is different than refereeing papers for inclusion in a journal in several ways. There is no central editor that assigns tickets to reviewers -- anybody (you, right now!) can just jump in and start refereeing tickets. Also, everything about refereeing is completely open and archived (hopefully) forever.

What To Expect

The code attached to a trac ticket can do all kinds of things, including:

Fix a little (or huge) bug.
Add documentation to a function.
Introduce a new feature to Sage (and possibly new bugs!).
Change the name of an existing function.
Raise (or lower) the "doctest coverage" of Sage.

How to Referee a Ticket

Refereeing a ticket involves several steps. The steps below are mainly aimed at tickets that add new capabilities to Sage, but I've included some remarks about other types of tickets in another section below.

Use Mercurial queues to apply all the patches on the trac ticket to your own (very recent, usually alpha) version of Sage, then type "sage -br" to rebuild the Sage library. You download
each foo.patch, then do "hg qimport foo.patch" followed by "hg qpush" (I personally use this little script). Note: this can be automated; type "sage -merge" to learn how. If you can't apply the patch, then the ticket may "need work", i.e., the author has to rebase the patches; note this and change the Action at the bottom of the ticket page to "needs work".
Test out the code to make sure the doctests work, using "sage -t affected_files" and "make ptest" in the SAGE_ROOT directory. Doing "make ptest" is a good idea, since often a change in one part of Sage breaks something far, far away that was written by somebody else long, long ago. (Again, see "sage -merge" for automating this.) If any tests fail, the ticket probably "needs work"; note this and change the action to "needs work". I often do this testing on sage.math.washington.edu, since it has 24 processors.
Make sure that every function introduced in the code, even ones that start with underscores (!), have examples that fully illustrate how they work. Make sure that all input parameters to these functions are tested in the examples, and ensure that the function is actually being used by the examples. If the patch is large you can do "sage --coverageall" both before and after applying the patches, and make sure the coverage score doesn't go down. Also, make sure the docstrings are laid out according to our standard template, e.g.,
```
"""
Short description... (one sentence usually)

Long description... (optional but sometimes good)

INPUT:
    - param1 -- description of
      the first param
    - param2 -- description of
      the second param
OUTPUT:
    - description of output

AUTHORS: 
    - Sage Developer1
    - Sage Developer2

EXAMPLES::

    sage: 2+2
    4

TESTS::

    sage: further examples nobody should look at.
"""
```
It is essential that there be two colons after "EXAMPLES" and a blank line!! Also, do not omit the INPUT/OUTPUT blocks, since I often get complaints from end users that these are missing.
If you've got this far without marking the ticket "needs work", then every function in the new code should work and have solid docstrings, including INPUT/OUTPUT blocks and examples that illustrate how the function works. Much of what you did in 1-3 is pretty routine (and yes, there are people working on trying to automate some of this). In this step, you finally get to have more fun and be creative: think seriously about whether the code is "probably correct" and sufficiently well documented to read. If not, do not give the code a positive review. The Sage library is already huge, and we don't want new code that is just going to cause a lot of pain to maintain later (there are other places for such code, such as Purple Sage). Basically, at this point, pretend you are a playtester or hacker and try to break the functionality introduced by the trac ticket. Some techniques include:
- Throw random input at the functions and see what happens.
- If you know any theorems or conjectures that leads to consistency checks on the functions, try them out. For example, if a function factors something as a product, try factoring products, then multiplying the factors back together. If the function computes the Ramanujan tau function, try it on large inputs and test the standard congruences.
- If the functions are implemented in other software (e.g., Magma or Mathematica) write a little program to systematically compare the output of Sage and the other system for some range of values. Also, compare timings; if code is 100 times slower in Sage than Magma, there better be a good reason for this.
- Very often when reading code, your "devious mind" will think of ways to potentially break it. Make sure that you have a sage prompt up, so you can try out your ideas for breaking the code. If anything succeeds at breaking the code, put that in your report and set the trac Action to "Needs work". Also, if you think of good doctests to add, note these.

Special Cases

As mentioned above, most of the steps above assume that the code attached to the trac ticket is implementing new features.

If the code fixes a bug, then if at all possible, there should be a new doctest that illustrates that the bug is fixed. This doctest should mention the relevant trac ticket.
If a trac ticket mainly adds new documentation, pay special attention to the English grammar, writing, etc. In my experience, almost nobody (definitely not me!) ever writes a few paragraphs of English without making several mistakes, typos, etc.
If the code changes the name of an existing function, then this must happen in accordance with our deprecation policy. You have to leave the old function name in place and add a deprecation warning. This can be removed after ONE YEAR. The proper way to do this is to put the following at the top of the function:
```
from sage.misc.misc import deprecation
deprecation("function_name is deprecated...")
```
Also, you may want to put in the Sage version number to give people a clue about when to remove the function (see the second argument to the deprecation function).

The core Sage library is meant to be mature, stable and highly polished, and function names, class names, etc., are not allowed to just be changed left and right. There are other places to post code that uses Sage, but which is not yet stable.

Posting Patches as the Referee

Often when going through the above steps, it is easiest to just make changes directly to the source code. E.g., if you see documentation misspelled, or think of examples to add. Just make a new patch that has all these changes and post a "referee patch". If you do this, then you should notify the original patch author(s), so they can referee your referee patch. This can get a little confusing, but usually sorts itself out.

Summary

I hope you can see from the above that refereeing tickets can be really fun. Think of it as a game to break whatever is posted on a trac ticket. It's much better if you find issues now when the author is still interested in the code, rather than some poor user finding bugs a few years later when the author of the code has moved on to other things and forgotten everything about the code. The core Sage library can only someday become high quality with your help as referees. And getting substantial code into Sage itself can only have any hope of attaining a similar status to publishing in a peer reviewed journal if this process of code refereeing itself gets refined, documented, and results in good quality mathematical software.

Remember, the goal is that only high quality code goes into Sage that satisfies the requirements outlined above; this is much more important than worrying about following "bureaucratic protocols".

Sage as a Python Library?

noreply@blogger.com (William Stein) — Wed, 27 Oct 2010 01:44:00 +0000

When I started Sage I viewed it as a distribution of a bunch of math software, and Python as just the interpreter language I happen to use at the time. I didn't even know if using Python as the language would last. However, it's also possible to think of Sage as a Python library.

Anyway, it has occurred to me (a few times, and again recently) that it would be possible to make much of the Sage distribution, without Python of course, into a Python library. What I mean is the following. You would have a big Python library called "sagemath", say, and inside of that would be a huge HG repository. In that repository, one would check in the source code for many of the standard Sage spkg's... e.g., GAP, Pari, etc. When you type

python setup.py install

then GAP, Pari, etc., would all get built, controlled by some Python scripts, then installed as package_data in the sagemath directory of /site-packages/.

From a technical perspective, I don't see any reason why this couldn't be made to work. HG can handle this much data, and "python setup.py install" can do anything. It does lead to a very different way of looking at Sage though, and it could help untangle things in interesting ways.

(1) Have a Python library called "sagecore", which is just the most important standard spkg's (e.g., Singular, PARI, etc.), perhaps eventually built *only* as shared object libraries (no standalone interpreters).

(2) Have a Python library which is the current Sage library (we already have this), and which can be installed assuming sagecore is installed.

(3) Have other Python libraries (like psage: http://code.google.com/p/purplesage/source/browse/), which depend on (2). Maybe a lot of the "sage-combinat" code could also be moved to such a library, so they can escape the "combinat patch queue" madness. Maybe many other research groups in algebraic topology, differential geometry, special functions, etc., will start developing such libraries... on their own, and share them with the community (but without having to deal directly with the sage project until they want to).

To emphasize (3), when people want to write a lot of mathematics code in some area, e.g., differential geometry, they would just make a new library that depends on Sage (the library in (2)). We do the work needed to make it easy for people to write code outside of the Sage library, which depends on Sage. Especially writing Cython code like this can be difficult and confusing, and we don't explain it all in any Sage documentation. It actually took me quite a while to figure out how to do it today (with psage).

The core Sage library (2) above would continue to have a higher and higher level of code review, tough referee process etc. However, the development models for (3) would be up to the authors of those libraries.

The above is already how the ecosystem with Python (http://pypi.python.org/pypi), Perl (http://www.cpan.org/), R, etc., work. Fortunately, Python has reasonably good support already for this.

I think without a shift in this direction, Sage is going to be very frustrating for people writing research oriented code.

Fortunately, it's possible to do everything I'm describing above without disturbing the mainline Sage project itself, at least for now.

Revision Control and Sage

noreply@blogger.com (William Stein) — Mon, 25 Oct 2010 19:25:00 +0000

The main target audience of this blog post is mathematics researchers who are relatively new to revision control in the context of Sage.

Background

In the 1990s when I first started using revision control, it was a major, major pain in the arse. Making a tarball snapshot of the project directory with a date-stamp was better! In 2005 when I started Sage, I didn't know any better, and didn't both with revision control for the first year. In 2006, Gonzalo Tornaria told me that things had improved, and got me to use Darcs. That lasted just over a year, when I switched Sage to use Mercurial. The switch was due to major headaches installing Darcs (a Haskell program), and Darcs hanging when our repo got too big and complicated.

We are fortunate that today many difficult problems and design decisions for revision control have been addressed through lots of work. Revision control is amazingly good now compared to what it was 15 years ago!

Some milestones: RCS, CVS, Subversion, Bitkeeper & Monotone, Darcs, Git/Mercurial/Bazaar

A reference: see the Mercurial guide.

Getting started with Mercurial

In sage we use "hg" = (Mercurial). Why?

- Because I chose it in early 2007, when Darcs started sucking too much
- Distributed is the way to go these days. (Modern)
- Bazaar far too unstable in 2007, to put it mildly. Bazaar is by the people who made Ubuntu, and is much more stable today.
- GIT badly documented, too hard to setup, etc... back in 2007; again, git is much better today.

---> so Mercurial was the only reasonable choice then. It was just "good enough" at the time that we could survive. Hence Mercurial.

Mercurial comes with Sage, and you can use it like so:
  - "sage -hg"
  - sage: install_scripts command
  - sage: hg_sage.[tab]

- Or Install: easy to install standalone on OS X, Linux, and Windows.

- You can do "$ sudo easy_install mercurial" to install systemwide the latest version into your default system wide Python.   It will probably appear in /usr/local/bin/hg

Documentation for hg:
- http://mercurial.selenic.com/
- http://hgbook.red-bean.com/
- http://mercurial.selenic.com/learn/
- http://hginit.com/

Project Hosting

If you create your own HG projects, you can easily host them on Google Code (and also http://bitbucket.org/).

I'm doing this a lot lately with smaller projects, including:
- Purple Sage
- Sage Notebook

- Other systems. Google code only does HG and Subversion.
But there are also similar hosting services for git and bazaar:
- github -- free hosting for git projects
- Bazaar's Launchpad

- Sourceforge: The first major free hosting site I heard of is sourceforge.net, which offers hosting for all sorts of repos, including mercurial. It is more general, but not as "clean and focused" in abilities as the above, e.g., their mailing lists are often plagued by spam, and I seem to recall a lot of banner ads.

These hosting services are a very popular and fairly new thing (but not too new); all but sourceforge became popular well after I started Sage. They provide much, much more than just what the revision control systems do; they are more than just a place to host your code repository. They all provide:

- code hosting (of course)
- bug tracking
- code review
- mailing lists, wiki's, etc.

Sage isn't hosted on one of these probably because they are so new, and Sage is older. This may change. Also, Sage is really, really big (Google code has a 2GB limit).

Main point: if you want to start a small project with a small number of other people -- example, writing a research paper and some corresponding code -- you can in seconds easily get the full suite of hosting, bug tracking, code review, etc., totally for free, backed up, high quality, etc. Obviously, you are trusting your data to either Google, Github, or Canonical, but you can easily backup most of it (e.g., the repos, mailing lists).

They want you to use them: "431,000 people hosting over 1,330,000 git repositories" (from github)

Story: In 2006, when I came to UW, Randy Leveque (a professor in applied math) found out about me running the Sage project, and wanted to know how to get Mercurial, Wiki's, trac, etc., setup, so that he could organize his software development project(s). I explained some basics, and I think he and his students setup various project infrastructure, and ran into assorted troubles. Today, I would just say "http://code.google.com" (or github, etc.) and be done with it! And Randy would be up and running with more tools than before in a matter of minutes.

Command line mercurial

The main point of the rest of this lecture will be about how to use Mercurial. It's very hard to beat the official Mercurial Quickstart, which we'll just go over together in class:

See the Mercurial Quickstart.

- Make a directory in your computer be under revision control
- Setup your .hgrc file, if you haven't already.
- Try cloning a remote repository, e.g., purple sage
- Try committing a change that spans multiple files, so you can see that all the changes are together. Then view the commit via "hg serve -p 8200".

WARNING: on OS X with the sage-included hg, this "hg serve" crashed for me with "Trace/BPT trap" when I visited http://localhost:8200. I opened trac ticket 10171.

So I did "sudo easy_install mercurial" to get a new version systemwide, and now this works for me: "/usr/local/bin/hg serve -p 8200"

A future blog post may cover more advanced HG topics, including branching, cloning, queues, and bundles.

Standalone C/C++ libraries that are included in Sage

noreply@blogger.com (William Stein) — Mon, 04 Oct 2010 23:47:00 +0000

Every copy of Sage includes many free open source C/C++ libraries, which can also be used standalone without Sage. They got into Sage because enough people really cared about using them, and felt it was worth the effort to convince other people that these should be included in Sage. Thus every single library also provides some key functionality to Sage. Thus understanding the main points about these libraries should be of interest to anybody who knows C/C++ who wants to do mathematical computation. Moreover, most of these libraries were written in C/C++ because the authors had already mastered the underlying algorithms, and really wanted an implementation that was extremely fast, often potentially orders of magnitude faster than what they might implement using only an interpreter, such as Python, Maple or Magma.

It's also possible using Cython (or even ctypes) to directly call any of the functionality of the libraries below from Python (hence Sage). Thus it is vital that you know about these libraries if you want to write fast code using the Sage framework.

When you want to look at the source code for any of these libraries, you can download the Sage source code from here or here, unpack it, look in the directory sage-x.y.z/spkg/standard/, and for any "spkg" (=tar, bzip2) file there, unpack it, e.g.,

wstein@sage:$ tar jxvf mpir-1.2.2.p1.spkg
wstein@sage:$ cd mpir-1.2.2.p1/src/
wstein@sage:$ ls
acinclude.m4     doc               missing        
...

Note that you can't unpack the spkg files included in a binary of Sage, since they are actually empty placeholders.

You can also find direct links to all of the standard spkg by going to this page, along with short descriptions of each.

Arithmetic

mpir (written in C and assembler; has a C++ interface): this is a library for doing fast arithmetic with arbitrary precision integers and rationals. It's very fast and cross-platform, and it's used by many other libraries. (NOTE: MPIR was started as an angry fork" of GMP=Gnu Multiprecision Library. GMP is used by Magma, Maple, and Mathematica; I've been told Mathematica doesn't use MPIR because of the overlap of Sage and MPIR developers, and their general suspicion toward the Sage project.)
mpfr (C library with C++ interface): this is a library for doing arithmetic with fixed precision floating point numbers, i.e., decimals with a given fixed choice of precision. "Floating-point numbers are a lot like sandpiles: Every time you move one you lose a little sand and pick up a little dirt." [Kernighan and Plauger]. MPFR is used by Magma (for details, google for "mpfr magma"), and several other libraries and systems out there. The number theory system and library PARI does *NOT* use MPFR; since PARI also does arbitrary precision floating point arithmetic, you see that PARI includes alternative implementations of some of the same algorithms (note: PARI also has its own alternative to MPIR). MPFR is unusual in that the main author -- Paul Zimmerman -- is unusually careful for somebody who works with floating point numbers, and my understanding is that all the algorithms in MPFR are proven to give the claimed precision. Basically, MPFR generalizes IEEE standards (that define what floating point arithmetic means) to arbitrary precision. MPFR also supports numerous "rounding modes". The mpmath Python library is in some cases faster than MPFR, but it has very different standards of rigor.
mpfi (C library): mpfi is built on top of MPFR, and implements arbitrary precision floating point "interval arithmetic". Interval arithmetic is an idea where you do arithmetic on intervals [a,b],
and apply functions to them. Given two intervals, their sum, product, quotient, etc., is another interval. The actual "feel" of using this is that you're working with floating point numbers, and as you lose precision due to rounding errors, the computer keeps track of the loss every step of the way... and in some cases you can quickly discover you have no bits left at all! MPFI is nicely integrated into Sage (by Carl Witty), and is a pretty sophisticated and robust implementation of interval arithmetic, on which some other things in Sage are built, such as the field QQbar of all algebraic numbers.
flint (C library): "Flint" is an abbreviation for "Fast Library for Number Theory". However, I've listed it here under basic arithmetic, since so far in Sage at least we only use FLINT for arithmetic with polynomials over Z[x] and (Z/nZ)[x]. (Sage should use it for Q[x], but still doesn't; see the horendously painful trac ticket, number 4000!) The main initial challenge and reason for existence of flint was to multiply polynomials in Z[x] more quickly than Magma (hence any other software on the planet), and FLINT succeeded. Now FLINT also does many other relevant polynomial algorithms, e.g., GCD, addition, etc. Most new development is going into "FLINT2", which is a total rewrite of FLINT, with an incompatible C interface. Bill Hart's vision is that eventually FLINT2 have capabilities sort of like PARI. Sage users have found at least one serious bug involving f,g in Z[x] where f*g was computed incorrectly.
znpoly (C libary): (by David Harvey) one version of znpoly is included in FLINT, and another is a standalone package in Sage. The point of this library is to do fast arithmetic in (Z/nZ)[x]. ("Monsky-Washnitzer!" we once found a very subtle bug in znpoly-in-FLINT that only appeared when multiplying polynomials of huge degree.)
givaro (C++ library): in Sage we use it entirely for fast arithmetic over small-cardinality finite fields, up to cardinality "2 to the power 16". Givaro makes a log table and does all multiplications as additions of small ints. Givaro actually does a lot more, e.g., arithmetic with algebraic numbers, and a bunch of matrix algorithms, including Block Wiedemann, which we don't even try to make available in Sage.

NOTE: The C library API conventions of mpir (gmp), mpfr, mpfi, flint and zn_poly are all pretty similar. Once you learn one, the others are comfortable to use. Givaro is totally different than the others because it is a C++ library, and hence has operator overloading available. The upshot: in Givaro, you type "c=a+b" to add two numbers, but in the other libaries (when used from C) you type, maybe "mpz_add(c,a,b)".

Number Theory

pari (C library; interpreter): a hugely powerful C library (and interactive interpreter) for number theory. This library is very, very good and fast for doing computations of many functions relevant to number theory, of "class groups of number fields", and for certain computations with elliptic curves. It also has functions for univariate polynomial factorization and arithmetic over number fields and finite fields. PARI has a barbaric stack-based memory scheme, which can be quite annoying. Key Point: PARI is easy to build on my iPhone, which says something. That said, we have Neil Sloane, 2007: ``I would like to thank everyone who responded to my question about installing PARI on an iMAC. The consensus was that it would be simplest to install Sage, which includes PARI and many other things. I tried this and it worked! Thanks! Neil (It is such a shock when things actually work!!)'' PARI is very tightly integrated into Sage.
ntl (C++ library): a C++ library aimed at providing foundations for implementing number theory algorithms. It provides C++ classes for polynomials, vectors, and matrices over ZZ, Z/pZ, GF(q), (Z/pZ)[x], and RR, and algorithms for each. Some algorithms, e.g., for polynomial factorization in ZZ[x], are very sophisticated. Others, e.g., Hermite form of matrices over ZZ, are naive. In fact, most of the matrix algebra in NTL is naive, at least compared to what is in IML, Linbox, Sage and Magma. NTL is very stable and considered "done" by its author.
eclib (C++, standalone program): This is John Cremona's prized collection of C++ code that he wrote for computing elliptic curves, both finding them (using "modular symbols") and computing tricky things about them (via the "mwrank" program). It's a large amount of C++ code that Cremona developed over nearly 2 decades. There is still much functionality in there that could be made more readily available in Sage via Cython, but for which nobody has put in the effort to do so (I'm sure Cremona would be very helpful in providing guidance).
lcalc (C++ library, standalone program): This is Mike Rubinstein's C++ library for computing with "motivic L-functions", which are generalizations of the Riemann zeta function, of great importance in number theory. It's particularly good at computing tons of zeros of such functions in their critical strip, hence getting information about generalizations of the Riemann Hypothesis. It's the best general purpose L-functions program for computing zeros.
sympow (standalone C program): Though technically not a library it could be adapted into one. Sympow is a C program written by Mark Watkins for quickly computing special values of symmetric power L-functions (so related to what lcalc does). It has no dependencies (instead of PARI), because Mark didn't want to have to license sympow under the GPL.
ratpoints (C library): Michael Stoll's highly optimized C program for searching for certain rational points on hyperelliptic curves (i.e. of the form y^2 = f(x)). This library goes back to the early 1990s and work of Elkies. I believe this is in Sage for one reason only: Robert Miller wanted to implement 2-descent, and he needed this. (Unfortunately, Miller's implementation is only done in the case when there is a rational 2-torsion point.) This library could be made more useful in Sage, via making it so functionality in sage.libs.ratpoints is easily available for hyperelliptic curves...
genus2reduction (standalone C program that uses PARI): Not technically a library. This a C program that depends on PARI, and quickly computes "stuff" about genus 2 curves over the rational numbers... which as far as I know is fairly unique in what it does. A. Brumer used it recently for a large scale computation, and pointed out that it has stability issues.
flintqs (C++ program): This is a standalone C++ program that implements the quadratic sieve algorithm for integer factorization (which is good at factoring p*q with p and q of similar size and p*q up to maybe 100 digits). I think that this algorithm is also implemented in PARI, though in some cases flintqs is faster. A silly fact is that a better version of this program is evidently in FLINT itself, but for some reason Sage doesn't use it.
ecm (C library and C program; uses MPFR, MPIR): This implements the elliptic curve integer factorization algorithm, which Hendrik Lenstra invented, and is good at factoring p*n with p a prime with up to 30 (?) or so digits. There is another highly optimized implementation of the same algorithm as part of PARI, but ECM is in some (all?) cases better. It also has a huge number of tunable parameters. The ECM program is also often run standalone by people, sometimes on clusters, to attempt to factor integers. NOTE: Sage has a "factor" command, which just calls PARI. One could imagine it calling ECM and flintqs, etc., but nobody has made it do so... though many have tried.

Linear Algebra

IML (C library): "Integer matrix library". This library solves A*X = B, with A and B matrices over the integers. It does this by solving "A*X = B (mod p^n)" for several prime powers p^n, which involves computing the reduced row echelon form of A mod p (for various p) quickly... which is in turn done via matrix multiplication over matrices with double precision entries. It is the fastest software in the world for solving AX=B in many cases, especially as the entries of A and B get huge.
Linbox (C++ library): asymptotically fast black box linear algebra algorithms. It was just a "research sandbox", but "we" (mainly Clement Pernet) got Linbox whipped into shape enough to be of use in Sage for certain things. It is used at least for: matrix multiplication and computation of characteristic polynomials of matrices over the integers and finite fields, and asymptotically fast echelon form of matrices over finite field. I don't think it is used for much else yet. Implementing fast versions of the above in general is a gargantuan task, and we had done much of it (but no good charpoly!) natively in Sage before using Linbox, so now multiple implementations are available -- Linbox's are usually faster. Until Linbox/Sage, there were no fast open source programs for asymptoically fast exact linear algebra -- Magma was the only game in town (neither Maple or Mathematica are good at this either).
m4ri (C library): "Mary" -- scary fast arithmetic with matrices over the finite field GF(2) with 2 elements. This library uses various tricks (involving so-called "Gray codes") and asymptotically fast divide-and-conquer algorithms to compute reduced row echelon form and do matrix multiplication with matrices over GF(2). It is memory efficient and is the world's fastest at many benchmarks. There is related work (on "m4ri(e)") to do arithmetic over GF(2^n) and also some work by Boothby and Bradshaw on GF(p^n) for small p and n.
libfplll (C++ library): floating point LLL. The whole point of fpLLL is to implement very fast algorithms for computing LLL reduced basis for lattices, possibly with rounding error if you are not careful. LLL gets used as a key algorithm in many other algorithms (e.g., polynomial factorization). Magma also uses some variant of libfplll, and an older rewritten version of fpLLL is in PARI. If you look, e.g., at Mathematica, it does have some sort of limited LLL implementation, but it is nowhere near as sophisticated as what is available overall in Sage... NTL and PARI also have their own interfaces to LLL, which can have various pros and cons over using fpLLL directly. (In Sage, you can make a matrix over the integers and call the LLL or LLL_gram methods on it.) Magma also uses fpLLL.
polybori (C++ library): commutative algebra with boolean rings, which are characteristic 2 rings such that x^2 = x for every element of the ring. Evidently, polybori is important in cryptography and circuit design (?). I have personally never succeeded in really understanding how or seeing for myself polybori do well on benchmarks. Polybori is why the boost-cropped package is in Sage, which provides some C++ datastructure and algorithms.

Combinatorics

symmetrica (C++ library): a C++ library for doing very fast arithmetic with symmetric functions. The combinatorics code in Sage builds on this.
cliquer (C library): for finding cliques (=maximal complete subgraphs) in a graph.

Geometry

gfan (C++ program): "groebner fans" -- for computing a geometric object that parametrizes all Groebner basis for an ideal.
cddlib (C library): for computing with convex polytopes that gfan requires, using the "double description" method (whatever that is). There is code in sage.geometry.polyhedra that also uses cddlib.
glpk (C library): the GNU linear programming toolkit. This is a good free open source program for "linear programming". There are also commercial programs (e.g., CPLEX) for linear programming, and whenever people talk about linear programming software they always point out that some commercial programs are way, way faster than glpk. But glpk is in Sage.
palp (C program): computes stuff about lattice polytopes, like all the integers points in one. There is a big Sage package that builds on top of this. Evidently, this is of substantial interest to some physicists.

Numerical applied math

gsl (C library): implements core algorithms of scientific computing, is very stable and considered "done" by its authors. New relevant code goes into other libraries that use GSL.

Non mathematics

readline: provides command line editing, which is used by IPython, PARI, Singular, etc. Often misbuilt or not available on various platforms, so included in Sage. Readline is perhaps famous for being a key reason that both PARI and clisp are licenced under the GPL.
bzip2: bzip2 compression; easily usable from Sage via "import bz2". NOTE: this is used by the Sage build system so it is in SAGE_ROOT/spkg/base instead of SAGE_ROOT/spkg/standard/.
zlib: gzip-compatible compression; makes it so you can easily "gzip" files, and even work with gzip'd files in memory from Python.

The Sagemath Cluster's Fileserver

noreply@blogger.com (William Stein) — Mon, 27 Sep 2010 03:23:00 +0000

In addition to being involved in programming in Sage, I am also the systems administrator for the "Sagemath cluster" of computers, which are used for Sage development, and also support mathematics research. This is a cluster of 5 machines with 128GB RAM and 24 cores in each machine, along with a 24 terabyte Sun X4540 fileserver.

When we setup this cluster nearly 2 years ago, we installed OpenSolaris and ZFS on the fileserver. It's run very solidly, in that the uptime was over 600 days a few days ago. However, no software would really work well on OpenSolaris for me -- top crashed usually, emacs crashed, stuff just didn't work. I never got Sage to build. Also, USB disks were a major pain on this machine, which complicated backups. Also, I frankly found the performance of ZFS and NFS-from-ZFS to be disappointing. In addition, nobody had a clue how to do maintenance and security updates on this server, meaning it was probable a danger.

Then Sun got bought by Oracle, and Oracle killed OpenSolaris. Also, I started getting really into MongoDB for database work related to the modular forms database project, and it would be nice to be able to run a MongoDB server and other related software and servers directly on my fileserver (yes, MongoDB supports Solaris, but...). Getting anything to work on Solaris costs too much time and confusion. So I decided to delete OpenSolaris and install Linux. Since there's many terabytes of data on the fileserver, and dozens of people using it, this involved many rsync's back and forth.

I eventually succeed in installing Ubuntu 10.04.1 LTS Server on disk.math. I setup a big 20TB software RAID-5 array on disk.math (with 2 spares), and added it to an LVM2 (=logical volume management) volume group.

I created 3 partitions:

   home -- 3.5 terabytes: for people's home directories
   scratch -- 3.5 terabytes; for scratch that is available on all machines on the cluster
   lmfdb -- 3.5 terabytes; for the L-functions and modular forms database project.

Thus over 7.5 terabytes is not allocated at all right now. This could be added to the lmfdb partition as needed.

The RAID-5 array has impressive (to me) performance:

   root@disk:/dev# /sbin/hdparm -t /dev/md0
   /dev/md0:
   Timing buffered disk reads: 1638 MB in 3.00 seconds = 545.88 MB/sec

All the above 3.5TB partitions are NFS exported from disk.math, and (will all be) mounted on the other machines in the cluster.

By using LVM, we will still get snapshotting (like ZFS has), which is important for robust backups over rsync, and is great for users (like me!) who accidentally delete important files.

I chose 3.5TB for the partitions above, since that size is easy to backup using 4TB external USB disks. Now that I'm running linux on disk.math, it will be easy to just plug in a physical disk to the fileserver and make a complete backup, then unplug it and swap in another backup disk, etc.

----

Some general sysadmin comments about, in case people are interested.

   (1) Oracle shutdown access to firmware upgrades, which meant I couldn't upgrade the firmware on disk.math. Maybe it would have been possible via phone calls, etc., but I was so pissed off to see Oracle do something that lame. It's just evil to not give away firmware upgrades for hardware. Give me a break. Oracle sucks. I'm really glad I just happened to upgrade the firmware on all my other Sun boxes recently.

   (2) The remote console -- which is needed to install from a CD image on disk.math -- does not work correctly on 64-bit OS X or 64-bit Linux. It just fails with "not supported on this platform" errors, but with no hint as to why. By installing a 32-bit Linux into a virtual machine, I was able to get this to work.

  (3) Linux NFS + software RAID + Linux LVM2 (=logical volume management) does roughly "the same thing" as ZFS did on the old disk.math machine. I spent about equal time with the documentation for both systems, RAID+LVM2+NFS and ZFS, and the documentation for RAID+LVM2+NFS is definitely less professional, but at the same time vastly more helpful. There's lots of good step-by-step guides, forums, and just generally a *ton* of useful help out there. With the ZFS documentation, there is basically one canonical document, which though professional, is just really frustrating as soon as you have a question not answered in it. I personally greatly prefer the Linux ecosystem.

  (4) RAID+LVM2+NFS is much more modular than ZFS. Each part of the system can be used by itself without the other parts, each has its own documentation, and each can make use of the other in multiple flexible and surprising ways. It's very impressive. One of the reasons I chose ZFS+Solaris instead of Linux+whatever 2 years ago is that I didn't realize that Linux offers similar capabilities.... because it didn't back in 2001 when I was learning tons about Linux. But it does now. Linux on the server has really, really improved over the years. (I've been using Linux since 1993.)

*-Overflow

noreply@blogger.com (William Stein) — Tue, 17 Aug 2010 21:42:00 +0000

I spent some time obsessively browsing http://mathoverflow.net during the last few days (and posting too), and it is a really awesome site. I found out about it last December, when I visited Berkeley to give a talk, and had lunch with one of the guys that runs the site, but didn't pay much attention to it until recently. It's much more suitable for discussion of research-level mathematics than general use and development of Sage.

Mathoverflow is interesting in that their comment system supports jsmath with realtime preview, which is something the TinyMCE editor in the Sage notebook doesn't do. It's also something that http://stackoverflow.com doesn't do, as far as I can tell. The grad students at Berkeley that organize mathoverflow probably somehow hacked jsmath into the comment system.

I was very surprised to learn that Mathoverflow and Stackoverflow (and all the dozens and dozens of stackoverflow-based sites) are closed source. There is a company that runs stackoverflow and hosts related sites, and keeping their code closed is part of their business model.

Some people sort of forked something related to stackexchange at some point, and created this: CNPROG, which is fortunately based on Python. There are about 20 sites using CNPROG now, including one for all questions about the use of Python in science, mathematics, and engineering.
I tried this site, answering a question about Cython, and it is snappy and clean.

Perhaps I will add jsmath or mathjax support to cnprog and start another site (http://q.sagemath.org ?), say on using math software as an aid to mathematical research. The site would not be specific to Sage or restricted to open source. The FAQ would say that all questions must be of the form: "(How) can I use a computer to compute XYZ, where XYZ should be some sort of advanced mathematical question." The emphasis on "advanced" and "research" is that there are already other sites about how to do elementary stuff (=people's homework), and it will provide an excuse to keep that out, which will greatly raise the quality. It is, after all, exactly this uncompromising focus on research that makes http://mathoverflow.net so interesting.

EDIT: I've now created http://ask.sagemath.org which is based on http://askbot.org, which is in turn based on CNPROG.

PARI on the iPAD (a component of Sage)

noreply@blogger.com (William Stein) — Mon, 07 Jun 2010 09:47:00 +0000

I got PARI (http://pari.math.u-bordeaux.fr/), which is a very powerful C program for doing number theory, to run natively on my iPad and iPhone!

"All" I had to do was:

1. Jailbreak my iPad using Spirit.
2. Make a gcc wrapper script on my MAC laptop that can cross-compiler binaries for iPhoneOS, and put this script first in my path (I called it gcc):

#!/bin/sh

# the following is all on one line:

/Developer/Platforms/iPhoneOS.platform/Developer/usr/bin/gcc -arch armv6 -mthumb -isysroot /Developer/Platforms/iPhoneOS.platform/Developer/SDKs/iPhoneOS3.2.sdk/ "$@"

3. Download the PARI source code and extract it: pari-2.3.5.tar.gz

4. Configure and build PARI (this requires that you have the latex XCode installed).

5. The build fails, so I edited the file src/kernel/none/mp_indep.c in a somewhat random way to get it to compile. More precisely, I commented out lines 794-801, and replaced them by:

# define INDEX0 1

# define INDEX1 0

6. Copy Odarwin-i386/gp-sta over to the iPad/iPhone using ssh (I installed an ssh daemon using Cydia).

7. Run it, via iSSH (purchased from the App store) connected to localhost -- see above.

Here is a link to my gp-sta, in case you want to just drop it on your phone and run it.

If I can put a simple GUI on this, I may try to submit this to the App store, so that anybody can trivially install GP for free. Another possibility would be to get it included in Cydia.

This is of course just a tiny step on the way to porting Sage to the iPad.

Addendum

I was also able to build Pari *directly* on the iPhone with readline support. Installing GCC was pretty crazy.


William-A-Steins-iPad:~/pari/pari-2.3.5 mobile$ Odarwin-arm/gp-sta 
                                 GP/PARI CALCULATOR Version 2.3.5 (released)
                            arm running darwin (portable C kernel) 32-bit version
                      compiled: Jun  7 2010, gcc-4.2.1 (Based on Apple Inc. build 5555)
                             (readline v6.0 enabled, extended help not available)

                                    Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY 
WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 4000000, primelimit = 500000
? 2+3
%1 = 5
?

My notes for installing GCC on the iphone:

1) Install this

  http://files.getdropbox.com/u/876743/fake-libgcc_1.0_iphoneos-arm.deb

dpkg -i fake-libgcc_1.0_iphoneos-arm.deb

2) apt-get install iphone-gcc


3) Install headers:

Copy these over, which I got from http://www.megaupload.com/?d=55ZNOCKI, and extra to /usr/include

   sdk-2.0-headers.tar.gz

I literally just put them in /usr/include/   

4) Missing

  /usr/lib/libgcc_s.1.dylib

...

wget http://apt.saurik.com/debs/libgcc_4.2-20080410-1-6_iphoneos-arm.deb


5) Hmm:

  http://blog.aaronash.com/?p=15

I downloaded this and extracted it as lib, and had to use some funny password.   
"aksblog.co.nr"
Then I copied lib/libSystem.dylib to /usr/lib/ on my iPad

... and now gcc seems to work! 

6) This isn't needed for some reason: Make it so I can sign my apps:

    apt-get install ldid  

ldid -S main

Maybe I don't need this only because I'm not making a gui yet. 


7) Compiling runs into fork limits a lot, so raise the limit:

William-A-Steins-iPad:~/pari/pari-2.3.5 mobile$ sysctl -w kern.maxprocperuid=64
kern.maxprocperuid: 26
sysctl: kern.maxprocperuid: Operation not permitted
William-A-Steins-iPad:~/pari/pari-2.3.5 mobile$ sudo sysctl -w kern.maxprocperuid=64
Password:
kern.maxprocperuid: 26 -> 64

A Python on iPad benchmark

noreply@blogger.com (William Stein) — Sat, 08 May 2010 01:10:00 +0000

Now that my iPad is really mine, i.e., jailbroken, I installed Python on it and tried a large integer arithmetic benchmark. I'm curious because this will indicate something about the performance of fully porting Sage to the iPad (though of course Sage would use MPIR for large integers...).

First, on my 64-bit 2.6Ghz Intel Dunnington box (sage.math.washington.edu):

>>> import resource
>>> def cputime(s=0): return sum(resource.getrusage(resource.RUSAGE_SELF)[:2])-s
... 
>>> t=cputime()
>>> a=3**(10**6)
>>> cputime()-t
0.53000000000000003
>>> b=a*(a+1)
>>> cputime()-t
2.46

Next on my laptop, which is a top-end macbook air (64-bit intel core2 duo running 64-bit python 2.6.x):

>>> t=cputime()
>>> a=3**(10**6)
>>> cputime()-t
0.64609700000000003
>>> b=a*(a+1)
>>> cputime()-t
3.1051849999999996

And, on the iPad

>>> t=cputime()
>>> a=3**(10**6)
>>> cputime()-t
2.3500000000000014
>>> b=a*(a+1)
>>> cputime()-t
9.5899999999999963

Not bad!! Note that 32-bit versus 64-bit (and Python 2.5 versus 2.6) may be relevant, depending on how Python big integer arithmetic is implemented.

As a bonus, I have an older iPhone 3G (not 3Gs), where we get:

>>> t=cputime()
>>> a=3**(10**6)
>>> cputime()-t
7.6699999999999999
>>> b=a*(a+1)
>>> cputime()-t

Wow, so the iPhone 3G at this benchmark is about TEN TIMES slower than the iPad. No wonder the iPad feels snappier.

Note that I view genuinely porting Sage to the iPad/iPhone as something that will only ever be available to people who jailbreak their devices. This is because Apple bans running any interpreter except Javascript on the iPhone. (Of course, I can always hope that Apple will get sued into opening up their app store...) For a person like me, a jailbroken iPad is dramatically superior to the standard iPad -- full multitasking, ssh access, Python, being able to easily change screen brightness, having full access to the filesystem, etc. Now if only I had Sage! (Of course, Sage usable on the iPad via the web, but sometimes I don't have reliable network access.)

Mathematical Software and Me: A Very Personal Recollection

noreply@blogger.com (William Stein) — Mon, 07 Dec 2009 19:32:00 +0000

[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

noreply@blogger.com (William Stein) — Mon, 12 Oct 2009 06:56:00 +0000

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

noreply@blogger.com (William Stein) — Thu, 08 Oct 2009 04:29:00 +0000

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

noreply@blogger.com (William Stein) — Fri, 03 Apr 2009 15:04:00 +0000

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!

noreply@blogger.com (William Stein) — Mon, 22 Dec 2008 23:07:00 +0000

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

noreply@blogger.com (William Stein) — Sat, 29 Nov 2008 03:44:00 +0000

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

noreply@blogger.com (William Stein) — Mon, 24 Nov 2008 03:43:00 +0000

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 (?).