| Version 59 (modified by nthiery, 13 months ago) (diff) |
|---|
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
Progress of the migration to Sage
| Topic | Progress | Priority | Comments |
| Basic combinatorial classes | 75% | 2007-08 by Mike | |
| Decomposable objects / Species | 75% | #10662 | |
| Trees | 30% | ||
| 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 | 80% | ||
| Algebra (desosseur, ...) | 30% | ||
| * with several bases | 50% | ||
| Operads | 10% | ||
| 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% | ||
| lrcalc | 60% | #10333 | |
| GLIP | 50% | #6812 | |
| graphviz / dot2tex | 80% | #7004, #10518 | |
| Copy-on-write data structure | 60% | see #8702 | |
| 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 |
Road map
- Hopf algebras, Symmetric functions, and generalizations
- Symmetric Functions
- #11563: Make lrcalc a standard package
- #12525: SFAHomogeneous does not work with RealField?
- Refactor SymmetricFunctions? using «multiple realizations» and deprecate SFASchur and friends See also: #7980
- #10930 (prototype): specializations for symmetric functions Martin Rubey, ???
- #10554: Better support for casual usage of symmetric functions
- #9558: Make is_symmetric method for polynomials or where else useful
- #9194: Expose and extend the thematic tutorial on symmetric functions
- #9755, #12645, #12381, #8259 (closed)
- #11929 (prototype): Implement quasi-symmetric functions JasonBandlow?, Valentin Feray, ???
- #8899 (prototype): Implement Non Commutative Symmetric Functions JasonBandlow?, AdrienBoussicault?, LenniTevlin?, JeanYvesThibon?, MikeZabrocki?
- #11979 (prototype): Divided power algebras Bruce
- Implement Schubert polynomials (Viviane Pons, AdrienBoussicault?, Nicolas Borie)
- #6889: Invariant rings of permutation group
- Symmetric Functions
- Representation theory:
- Finite dimensional algebras:
- Decomposition of the center, construction of central idempotents (as in MuPAD-Combinat)
- Quiver, Cartan matrix, radical filtration (as in MuPAD-Combinat)
- Depends on: #11111
- Finite monoids
- Group algebras:
- Path algebras:
- #9889 (prototype): A new module implementing Monomial Algebras
- Finite dimensional algebras:
- Experiment with KBMAG / PLURAL (see #4539) to implement various algebras like affine nilCoxeter algebra, affine nilTemperley Lieb algebra, affine local plactic algebra), see also patch nilTemperley-as.patch in the sage-combinat queue) (AnneSchilling?) This could possibly make use of KBMAG.
- Root systems:
- #8906 (needs finalization): Optional package for gap3
- Integrate/interface PyCox?
- Root systems:
- Constructing a root/coroot lattice realization from a pair of matrices Work in progress by Christian Stump
- Allows a generalized Cartan matrix as input for Dynkin diagrams
- Coxeter groups, reflection groups:
- Computation of reflection degrees from positive roots (easy)
- #8359 (needs finalization): permutation representation of a Coxeter group, using GAP3
- Implement general Coxeter groups given by a Coxeter diagram
- #12912: Interface to Coxeter 3 from Fokko Ducloux (MikeHansen?)
- #12774: (needs review): various enhancements for Coxeter and Weyl groups
- #11187 (prototype): Implementation of finite reflection groups
- Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder)
(Volunteers?)
- #8327 (needs review): implement the universal cyclotomic field, using the Zumbroich basis Christian Stump
- Representations of Coxeter groups and Hecke algebras
- Port over the character tables
- Representations/character tables of the Hecke algebras
- Port Specht (AndrewMathas?)
- Implement data structures for character tables / use it systematically in Sage (Volunteers? Nicolas has some design notes about this):
- of groups in Sage / GAP
- of semi-simple algebras (in Sage / GAP)
- of a coset
- See also #7555: fix Cayley tables, add operation tables
- Implement the many realizations of the Hecke algebra (AndrewMathas?, ...)
- Further improve root systems, Coxeter groups and the like, getting features, inspiration, code, doc, tests, developers from Chevie (...)
- Crystals:
- Cluster algebras (Christian Stump, ...):
- #10819: Implementation of the cluster complex
- #10538: Implementation of the classes ClusterSeed? and Quiver
- #11010: Implementation of the SubwordComplex? as defined by Knutson and Miller
- #12587: Simplicial complexes lack hash function
- #11523: Implementation of Cohen-Macaulay test for simplicial complexes
- Modules and vector spaces:
- Generalized tensor product
- #10673: Roadmap for (Combinatorial)FreeModule?
- #11111 (needs finalization): More support for finite dimensional free modules and algebras Depends on #8678
- #8678: module morphisms (tensor products, inverses, ...)
- Categories & coercion:
- #10963: More functorial constructions (NicolasThiéry?)
- #10668, #10667: Cleanup support for morphisms
- (prototype) Implement multiparameter morphisms This could be extracted and finalized without much work
- #8900 (prototype): Implement multiparameter overloaded functions, with explicit registration Depends on #7420; #383 is not enough NicolasThiery?
- #7420 (prototype): Use breath-first-search or Dijkstra in Coercion, as discussed in (volunteers?) NicolasThiery?
- Combinatorics
- #10662: Improve combinatorial species / decomposable classes
- Basic support for operads (partially depends on #10662) FlorentHivert? + FredericChapoton?
- Generating series, analytic combinatorics, ...:
- Enumerated sets:
- #12913: Deprecate CombinatorialClass? in favor of the EnumeratedSet?'s categories
- #5268: Further cleanup of Enumerated sets
- #11407: Add normalization to clonable lists
- Use ClonableIntArray? and friends for all combinatorial object: permutations, partitions, compositions...
- Fix everything from: http://wiki.sagemath.org/combinat/Weirdness
- #10534 (needs review): Optimizations for the generation of subwords, subsets, and set partitions VincentDelecroix?
- #6812: Enumerate integer vectors modulo to the action of a Permutation Group Nicolas Borie
- #6538: Reimplement from scratch IntegerListsLex?, fixing its 8-year old bugs
Former road maps and history
- Todo for/at Sage Days 20.5 (May 2010):
- Design and implement framework for computing with representations / modules / character rings
- Words improvements:
- Todo for Sage Days 20 (February 2010):
- #7004 will be used intensively to visualize semigroups and others
- words bug : #8095 (word morphism is primitive), #8140 (sturmian words definition), #8186 (length handling), #8215 (empty word), #8232 (cmp bug), #7520 (word construction)
- words enhancement : #8187 (equality of words), #8268 (speed up christoffel words), #8287 (_check function), #8289 (word morphism call function), #7619 (pickle for word defined by callable or iterator), #8233 (concatenation), #8266 (documentation)
- words new functions : #8093, #8127, #8227
- Disjoint set data structure : #6775
- 2012:
- Optimizations:
- #11115: Rewrite cached_method in Cython
- Symmetric functions and generalizations:
- #10333: An interface to Anders Buch's Littlewood-Richardson Calculator lrcalc
- Categories: #9469, #8119, #12527, #12877, #11943
- Coercion: #11250, #11257
- Enumerated sets: #11118
- Posets: #10998 (Categorification), #12476, #12677, #10670, #11382, #12536 (Linear extensions)
- Modules and vector spaces: #12464, #12484, #12489, #12528
- Root systems:
- Quivers: #10349, #10347
- Sphinx, Documentation: #9128, #12717, #12849, #12490
- #7980: Implement generic support for parents with (multiple) realizations
- Optimizations:
- 2011:
- #8702: Fast datastructure for (combinatorial) objects with prototype (clone) design pattern.
- #11290: Implementation of non-commutative k-Schur functions in the nilCoxeter algebra
- Documentation: #11251, #11282
- Debugging, profiling: #11287
- Installation: #11296
- Posets: #10065, #11293
- Combinatorics: #11300, #11301, #11314
- 2010:
- Root systems, crystals, ...
- Categories, parents, elements:
- Symmetric functions:
- #8259: Conversion from symmetric polynomials to basis of monomial symmetric functions
- Modules and vector spaces:
- #8876: Triangular morphisms with domain and codomain having different index sets
- #7914: Triangular isomorphisms of free modules
- #7938: swap_term_and_monomial
- #9651: Addition on CombinatorialFreeModule? directly on dictionaries (closed: fixed)
- #9648: ModulesWithBasis? allows module_morphism's to a wider class of ... (closed: fixed)
- Graphs:
- #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout
- Enumerated sets:
- #8519: NN, NonNegativeIntegers?, PositiveIntegers?, IntegerRange?, ...
- #6655: Cleanups and new features about corners and cells in partition and tableau
- 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
- 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
- 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.
- Summer 2008: port of decomposable objects (from MuPAD-combinat) / species (from aldor-combinat) by Mike Hansen, funded by Google
- June 24th 2008, FPSAC (Valparaiso, Chile):
- Official announcement of the migration
- Goal: elementary combinatorics users can start directly with Sage
- June 19th 2008: Visit of Florent to Davis. Final decision to migrate!
- May 2008: Fixed several of the Weirdness issues (#3286, JasonBandlow?)
- 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
- 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 #10669
- January 2008: presentation of MuPAD-Combinat at the AMS meeting in San-Diego; meeting and discussions with the Sage team
- June 2007: design discussions between Nicolas and Mike at the Axiom Workshop 2007
- 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.
- December 2000: Birth of MuPAD-Combinat
Attachments
-
P1050207.JPG
(807.6 KB) -
added by nthiery 13 months ago.
Roadmap in May 2010 (Sage Days 20.5, Toronto)
