Monday, March 31, 2008

Sage 2.11 is out!

Sage 2.11 has been released. In total 31 people did contribute patches for this release. Due to spring break and the easter holidays things moved a little slower than I had anticipated. But in the end it looks like we put together a pretty decent release. Binaries are available by now.

The high level changes in detail are:

  • ATLAS: Michael Abshoff and Burcin Erocal upgraded ATLAS to the 3.8.1 release. In addition tuning info for 32 bit Prescott CPUs as well as Powerbook G4s under Linux was added.
  • zn_poly: David Harvey's zn_poly library is now a standard package for Sage. zn_poly is a new C library for polynomial arithmetic in (Z/nZ)[x] where 3≤n≤ULONG_MAX (i.e. any machine-word-sized modulus). The main benefit is speed. The library is used so far only to compute the zeta function for hyperelliptic curves.
  • Small roots method for polynomials mod N (N composite): Martin Albrecht implemented Coppersmith's method for finding small roots of univariate polynomials modulo N where N is composite.
  • Generic Multivariate Polynomial Arithmetic: Joel Mohler improved the efficiency of the generic multivariate polynomial arithmetic in Sage by roughly a factor of ten.
  • k-Schur Functions and Non-symmetric Macdonald Polynomials: Mike Hansen: k-Schur functions s^(k)_\lambda are a relatively new family of symmetric functions which play a role in Z[h1,...,hk] as the Schur functions s_\lambda do in \Lambda. The k-Schur functions, amongst other things, provide a natural basis for the quantum cohomology of the Grassmannian. The k-Schur functions can be used like any other symmetric functions and are created with kSchurFunctions. Non-symmetric Macdonald polynomials in type A can now be accessed in Sage. The polynomials are computed from the main theorem in "A Combinatorial Formula for the Non-symmetric Macdonald Polynomials" by Haglun, Haiman, and Loehr.
  • Marshall Hampton did upgrade gfan as well as the optional phcpack spkgs and their interfaces. He also increased doctest coverage to 100% for both interfaces.
  • Improved capabilities for solving matrix equations: William Stein implemented code so that one can now solve matrix equations AX=B and XA=B whenever a solution exists. In particular, solving linear equations now works even if A is singular or nonsquare.
  • Generators for congruence subgroups: Robert Miller implemented an algorithm for very quickly computing generators for congruence subgroups \Gamma_0(N), \Gamma_1(N), and \Gamma_H(N).
  • Various other people fixed a number of bugs and did improve other bits of Sage.
Next up is the 3.0 release. We are shooting for a two week release cycle, but we will see how things go :)

Cheers,

Michael

Tuesday, March 25, 2008

Sage vs. GSoC 2008

Oh well, Sage didn't make it into the GSoC 2008. Looking at the selected projects one can see that mathematical Open Source software is underrepresented. Only the R project (which is technically a statistics software package and not mathematics - some people insist on that distinction) made it in out of many mathematical software projects who applied. In recent years various projects made it into the GSoC via other orgs, i.e. sympy via multiple orgs and at least one Axiom related project via LispNYC.org.

So why didn't Sage make it in? It is hard to tell since there is little transparency during the selection of the mentor organizations. Various people put up theories at Slashdot. Specifically pongo000 commented after hanging out a couple hours in #gsoc when various mentor orgs showed up and inquired why the hadn't been selected. pongo000's observation was that the following issues did play a large role:
  • the size of the organization
  • whether an org participated in years past
  • the quality of the ideas list
So how does Sage fit the bill?
  • the size of the organization: not huge, but certainly not at the low end of the spectrum. Interestingly enough OpenOffice.org didn't make it as a mentor org this year. Somebody did show up in #gsoc and inquired why that had happened and was informed that they allegedly didn't apply.
  • whether an org participated in years past: we applied twice and got twice rejected.
  • the quality of the ideas list: Some Sage developers did hang out in #gsoc and did talk to lh and ask questions about the application and list of ideas Sage had submitted. One aspect was the quality and accesibility of our idea list. Apparently there are people out there who are not familar with the more abstract aspects of mathematics :) and who do need a little more info about the projects, i.e. it isn't obvious to many people what commutative alegbra consists of. We had initially discussed at Sage Days 8 what kind of application we wanted (new blood vs. tried and true contributors) and come down pretty much in favor of tried and true contributors. While we had at least two projects on the list that didn't require mathematical expertise (the notebook and Cython) the other projects were very specifically tailored for the people who wanted to do them and do contribute to Sage in that area. I won't go into details here, but if we do participate in another GSoC we need to do have more CS that mathematical projects - at least that is worked for the R's project idea page. Another highly recommended feature is a template system that list requirements and difficulty of a given projcet. But in mathematics that is highly subjective, i.e. "Drawing Graphs on Surfaces with Genus greater than 0", is not something the average non-math student will be familiar with or get up to speed in three months. Emily Kirkman on the other hand has been working in Graph theory for a while, so while I am sure it is far from trivial it would have been a nice project. Other projects like "Combinatorial Species/Decomposable Objects" or "Free abelian groups and integer lattices" aren't exactly know to the average College graduate either.
So in the end while we aren't happy with the decision of Google it is up to Google in the first place where they spend their money. And it isn't game over for Sage yet and the GSoC 2008. We have various project suggestions that we are trying to get accepted via other mentor orgs like the PSF.

And while I cannot go into details right now I can tell you that this might not be the end of the road, so stay tuned for further announcements.

Cheers,

Michael

Monday, March 17, 2008

Sage 2.10.4 coming up

We are very close to a Sage 2.10.4 release. I didn't announce the 2.10.3 release here, but Marshall Hampton did. My reduced blogging activities were are mix of procrastination, the need for some time away from the computer and Sage Days 8 in Austin, TX. Sage Days 8 was very nice and I had a lot of fun in Austin, but more about that in a later post.

So I am being lazy now and I will more or less copy and paste the announcement from the release notes:

  • Memory leaks exposed by modular symbols: Michael Abshoff, Martin Albrecht, Burcin Erocal, Willem Jan Palenstijn, Clement Pernet, William Stein: memory leaks exposed by modular symbols functionality. This ticket is a composite of numerous other memleak fixes merged over a 7 month period. Modular forms are an excellent way to expose memory leaks in pretty much every algebraic component of Sage and all known issues there are now finally fixed.
  • SQLAlchemy and DSage: We merged SetupTools and SQLAlchemy into Sage as standard packages. SQLAlchemy is now used as in DSage replacing hand written code with much more efficient classes from SQLAlchemy. SetupTools is required to install SQLAlchemy, but is also useful for a number of optional spkgs like MayaVI and packages from the Enthought Tools. Yi Qiang improved DSage making it more robust and finally adding the documentation to the standard Sage manual.
  • Graph theory: chromatic polynomial: An algorithm originally written in C by Gordon Royle has been adapted by Robert Miller to replace the old slow method. This algorithm uses a cut and merge algorithm to recursively compute the chromatic polynomial, and is written in Cython.
  • Documentation: Many doctest patches written during Doc Day 2 were merged. In addition many people kept up the good work after Doc Day 2 was over and have been submitting patches to increase coverage. We did exceed the target for the release by 0.6% reaching 47.6%.
  • Symmetric function updates: Mike Hansen, reviewed by Franco Saliola: Sage 2.10.4 adds support for Macdonald polynomials, LLT polynomials, and Jack polynomials as well as a whole class of user-defined symmetric functions which can characterized by orthogonality and triangularity conditions. Support for working with ribbon tableaux was also added as part of these updates. In addtition, many doctests were added and subtle bugs fixed.
  • Notebook Updates Tom Boothby, William Stein and Timothy Clemans: Fixed a bunch of new and old issue that improve the usability of the notebook. Among those are a working trash, fixes to the polling infrastructure, saving the content of unevaluated cells, URL issues to work around problems introduced by restrictive firewalls and small improvements to the interact command.
  • Parallel Doctesting: Gary Furnish reviewed by Michael Abshoff: "sage -tp" has been introduced as an experimental multithreaded doctester. The first parameter is the number of threads, and the second parameter is the folder to doctest. Thus "sage -tp 4 devel/sage/sage" tests everything with four threads running. Additional options like "-long" or valgrind options like "-memcheck" do work. The code base is still young and needs more testing. The eventual goal will be to replace the current doctesting infrastructure with this code base.
Sage 2.10.4.final has been released and is currently being build tested on our compiler farm. Once it has passed tests and no blocker issue shows up in testing we will release.