Austria, ISSAC, and Hidden Markov Models

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

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

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

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

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

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

ISSAC

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

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

• Michael Abshoff
  
• Elliot Brossard
  
• Gary Furnish
  
• Mike Hansen
  
• Emily Kirkman
  
• Robert Miller
  
• Brett Nakashima
  
• Yi Qiang
  
• Chris Swierczewski
  
• Igor Tolkov
  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

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

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

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

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

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

http://www.sagemath.org

Sage-3.0 and Beyond

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


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

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

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



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

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

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

Google Funds Sage!!

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

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

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