Roadmap and status report for Sage-Combinat
This page is an attempt at drawing a road map for Sage-Combinat, and in particular the migration from MuPAD-Combinat.
Todo: extend the history, and include links to the relevant trac tickets.
Overview
Timeline
- December 2000: Birth of MuPAD-Combinat
- February 2007: First contact with Mike Hansen who wanted to port some features of MuPAD-Combinat, which we very much encouraged. Since then Mike translated 30k lines of code, which accounts for most of the basic combinatorics (tableaux, permutations, ...), and symmetric functions.
- June 2007: design discussions between Nicolas and Mike at the Axiom Workshop 2007
- January 2008: presentation of MuPAD-Combinat at the AMS meeting in San-Diego; meeting and discussions with the Sage team
- February 2008: Sage Days 7 (Los Angeles)
- Technical experimentation with Sage to see how fit it is for our purposes.
- Partial port of the crystals library (#2742, AnneSchilling? and NicolasThiéry?)
- Implementation of Xin's Omega algorithm by Jason and Greg.
- Spring 2008, in particular at MSRI (Berkeley, USA):
- Long discussions within the community about the opportunity to switch
- Port of root systems (#2808, #2809, #2864, #2868, #2874, #2964, #3660, #3664, NicolasThiéry?, DanBump?, JustinWalker?, MikeHansen?, TomDenton?)
- Further port and extensions to the crystals library (#2868,#3032,#3417,#3418,#3660, AnneSchilling?, DanBump?, JustinWalker?, BrantJones?)
- Basic setup for FreeModule?'s
- Posets (FrancoSaliola?)
- Created the ' Weirdness' web page
- May 2008: Fixed several of the Weirdness issues (#3286, JasonBandlow?)
- June 19th 2008: Visit of Florent to Davis. Final decision to migrate!
- June 24th 2008, FPSAC (Valparaiso, Chile):
- Official announcement of the migration
- Goal: elementary combinatorics users can start directly with Sage
- Summer 2008: port of decomposable objects (from MuPAD-combinat) / species (from aldor-combinat) by Mike Hansen, funded by Google
- September 08: announcement that Sciface is purchased by Mathworks (Matlab).
- MuPAD does not qualify anymore as a "reasonably priced high quality computer algebra system".
- Sciface cancels its formerly liberal licence policy for MuPAD-Combinat developers.
- Plan for a last stable release of MuPAD-Combinat dropped.
- October 08: Sage Days 10 (Nancy, France)
- Get the core MuPAD-Combinat developers started with Sage
- Design, prioritization, planning
- Design of the categories and (Hopf) algebra framework using the new coercion system
- 2009:
- Implementation of categories in Sage (#5891, #7251, #7443) (NicolasThiéry?, ...)
- Cleanup and refactoring of root systems and Coxeter groups (#4326, #4327, #4608, #7753, #7754), Weyl characters (#5794) and crystals (#4311,#5729,#3663, #5002, #5729, #5879) (AnneSchilling?, DanBump?, NicolasBorie?, StevenPon?, NicolasThiéry?, ...)
- Cleanup and refactoring of the combinatorics (#4549, #5200, #5308, #5487, #5534, #5551, #5781, #5600, #6000, #7403, #7395, #7396, #7397) (FlorentHivert?, NicolasThiéry?, ...)
- Implementation of FreeModule? / Hopf algebra framework (#6136)
- Refactoring of symmetric functions (#5457, #6137, #7777) (NicolasThiéry?, JasonBandlow?)
- Refactoring of the SymmetricGroupAlgebra? to use categories and free modules (#6138)
- Words, ...
- Families: #5538, #7208, ... (FlorentHivert?)
- TestSuites?: #6097, #6809, #6343, #7478 (NicolasThiéry?)
- Technical patches: #5120, #5405, #5449, #5598, #5783, #5843, #5920, #5967, #5979, #5985, #5986, #5991, #6000, #6097, #7420, #7421, #7776, #7928, #7842 (NicolasThiéry?, ...)
- Partial support for Iwahori Hecke algebras for all types: #7729 (DanielBump?, AnneSchilling?, NicolasThiéry?)
- July 2009: FPSAC'09 (RISC, Linz, Austria)
- Goal: Most features ported
- Goal: Most of the research done with Sage-Combinat
- Goal: All new users can start directly with Sage
- Todo for Sage Days 20 (February 2010):
- Merge #7921 and #8001 in Sage 4.2.2: Categories for extension types via getattr_ + tests(Robert, NicolasThiéry?)
- Merge #7938 in Sage 4.2.2: swap_term_and_monomial (JasonBandlow?)
- Rebase, finalize and merge #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout (Robert Beezer)
- Finalize #7914: Triangular isomorphisms of free modules (JasonBandlow?)
- Generalize #7914: (Jason?, Nicolas; depends on #7938)
- Support for a (partial) inverse function on terms (when the indices of the domain do not coincide with those of the codomain)
- Non invertible triangular morphism:
- phi.preimage(y): returns the preimage x of y or None if it does not exists (or raise an exception?)
- phi.reduce(y): returns (x, r) such that y = phi(x) + r, and r contains no leading term of phi(domain) (that would be euclidean division if phi was x -> x * p where p is some polynomial) Better name for that method?
- (6) Use breath-first-search or Dijkstra in Coercion, as discussed in #7420 (volunteers?)
- (7) Allow for user defined overloaded operators, with signature declarations (#383 is a progress, but not enough) (NicolasThiéry?, depends on (6))
- (8) Refactor the support for functorial construction (NicolasThiéry?)
- (9) Implement the Sub / Quotient / Subquotient functorial constructions (FlorentHivert??, depends on (8))
- (10) Implement Sub and Quotient of finite dimensional free modules / algebras / ... (FlorentHivert??, depends on #7938 and #7914 with generalization)
- #7980: Extract basic support for the "concrete representation of an abstract algebra" relation out of the ncsf patch (JasonBandlow?)
- #6588: Categorification of root systems Make Root and WeightLatticeRealization? into categories Declare the various embeddings as coercion/conversions Define and use an overloaded operator for the scalar product (depends on (7)) There is a preliminary patch in our queue
- (7), #7980 are building blocks for further progress in qsym/ncsf/polynomials with several basis (#6889)
- (9) is a building block for the representation theory of monoids
- (10) is the main building block for the representation theory of finite dimensional algebra
- #7004 will be used intensively to visualize semigroups and others
- 2010:
- Implement QSym, NCSF, ... (JasonBandlow?, NicolasThiéry?, LenniTevlin?, MikeZabrocki?)
- Further improve root systems, coxeter groups and the like, getting features, inspiration, code, doc, tests, developers from Chevie (...) Also integrate Coxeter 3 (Mike Hansen)
- Implement the many representations of the Hecke algebra (AndrewMathas?, ...)
- Implement interface to Jean-Éric Pin's Semigroupe package, and extend further the semigroup/monoid/group algebra code (#6654, ...)
- Improve Trees, Species, ...
- Reimplement from scratch IntegerListsLex?, fixing its 8-year old bugs
- Basic support for operads
- Crystals: categorification, more models (alcove and littlemann path, ...)
Progress of the migration to Sage
| Topic | Progress | Priority | Comments |
| Basic combinatorial classes | 75% | 2007-08 by Mike | |
| Decomposable objects / Species | 75% | Google summer of code 2008 by Mike | |
| Trees | 20% | ||
| Posets | % | ||
| Words | % | ||
| Symmetric functions | 90% | ||
| k-Schur & the like | 50% | ||
| Root systems / ... | 90% | ||
| Crystals | 90% | ||
| Category framework | 80% | ||
| Hopf algebra framework | 50% | ||
| Free modules & such | 50% | ||
| Algebra (desosseur, ...) | 0% | ||
| * with several bases | 0% | ||
| Operads | 0% | ||
| Linbox interface | 100% | (compares to 10% in MuPAD) | |
| GAP interface | 80% | (compares to 1% in MuPAD) | |
| Interface for fast Gröbner basis | 100% | (compares to 0% in MuPAD) | |
| Nauty | 100% | (compares to 50% in MuPAD | |
| Symmetrica | 60% | ||
| GLIP | 50% | Deprecated by Robert's generic code (also funded by Google) | |
| dot2tex | 10% | Delegated to the SAGE graph theorists | |
| Copy-on-write data structure | 30% | ||
| Database access | 100% | ||
| MachineIntegerListsLex? | 0% | Will be easy via cython | |
| Rigged configurations | 0% | ||
| Basic abstract data structures | 100% | (fast stacks, AVL, dancing links) compares to just the basic ones in MuPAD + no real way to implement some with serious speed ourselves |
