|Version 57 (modified by nthiery, 13 months ago) (diff)|
Roadmap and status report for Sage-Combinat
Todo: extend the history, and include links to the relevant trac tickets.
Progress of the migration to Sage
|Basic combinatorial classes||75%||2007-08 by Mike|
|Decomposable objects / Species||75%||#10662|
|k-Schur & the like||50%|
|Root systems / ...||90%|
|Hopf algebra framework||50%|
|Free modules & such||80%|
|Algebra (desosseur, ...)||30%|
|* with several bases||50%|
|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|
|graphviz / dot2tex||80%||#7004, #10518|
|Copy-on-write data structure||60%||see #8702|
|MachineIntegerListsLex?||0%||Will be easy via cython|
|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|
- Hopf algebras, Symmetric functions, and generalizations
- Symmetric Functions
- #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)
- Symmetric Functions
- #10305 (prototype): Add rings for the center of the symmetric group algebras Mathieu Guay-Paquet, Valentin Feray
Tensor products of morphism Generalized tensor product
- #7980 (closed 5.0) Implement generic support for parents with (multiple) realizations
- Further improve root systems, Coxeter groups and the like, getting features, inspiration, code, doc, tests, developers from Chevie (...)
- Implement the many representations of the Hecke algebra (AndrewMathas?, ...)
- Implement more models of Crystals (alcove and littlemann path, ...): #8984, ...
- #10662: Improve combinatorial species / decomposable classes
- Basic support for operads (partially depends on #10662)
- Improve Trees #8703
- Generating series, analytic combinatorics, ...:
- #10673: Roadmap for (Combinatorial)FreeModule?
#9651: enhancement: Addition on CombinatorialFreeModule? directly on dictionaries (closed: fixed) #9648: enhancement: New feature: ModulesWithBasis? allows module_morphism's to a wider class of ... (closed: fixed)
- Cleanup of combinatorics
- Goal: deprecate the old CombinatorialClass?
- In practice, all classes that currently inherit from CombinatorialClass should instead inherit from Parent and register themselves in one of the categories (*EnumeratedSets, *FiniteEnumeratedSets, or *InfiniteEnumeratedSets). For examples, see e.g. FiniteEnumeratedSets().example().
- Expected benefits:
- Support for TestSuite?
- Support for conversions, coercions, and morphisms, in particular for bijections (as morphisms in the category of Sets with bijection, with properly defined domain and co-domain rather than python functions).
- Let CombinatorialClass inherits from Parent (mostly done #8910)
- For each CombinatorialClass C:
- Have C inherit directly from Parent
- Ensure that C.__init__ sets up the proper category (Finite|Infinite)...
- Add TestSuite(C).run() to the doctests and make all the tests pass
- Have a properly setup attribute C.Element and use C.element_class (as defined by the categories) when constructing elements
- Ensure proper unique representation behavior by having C inherit both from UniqueRepresentation and Parent
- Deprecate and remove CombinatorialClass
- Turn all the factory functions into factory classes by mean of ClasscallMetaClass; see PerfectMatching and Trees for an advanced example.
- Reimplement iteration of subsets/set partitions (too slow!): implementation of a Python extension in C + inclusion in Sage (VincentDelecroix?, #10534)
- #6538: Reimplement from scratch IntegerListsLex?, fixing its 8-year old bugs
Former road maps and history
- Todo for/at the joint Sage-Combinat/Chevie? workshop (June 2010):
- #8380: Finalize and merge the interface with GAP3
- #6588: Categorification of root systems (NicolasThiéry?)
- 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) above)
- See preliminary patch in the Sage-Combinat queue
- Constructing a root/coroot lattice realization from pair of matrices (Volunteers?)
- Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder) (Volunteers?)
- Computation of reflection degrees (easy; NicolasThiéry? or any volunteer)
- #8359: Finalize permutation representation of a Coxeter group
- #8347: Positivity testing for cyclotomic fields. See also #8327: implement the universal cyclotomic field, using Zumbroich basis
- Implement general Coxeter groups given by Coxeter diagram (depends on #8347)
- Port over the character tables (depends on 1 to be most useful)
- Representations/character tables of the Hecke algebra
- Interface to Coxeter 3 from Fokko Ducloux (MikeHansen?)
- 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 #7555: fix Cayley tables, add operation tables
- Todo for/at Sage Days 20.5 (May 2010):
- Review of #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout (VincentDelecroix?)
- Finalize the basic Cython data-sctructure for combinatorial objects (in progress #8702, FlorenHivert?)
- Finalize the cleanup of combinatorial object: permutations, partitions, compositions...(First step: #6655 FlorentHivert?)
- Trees (mostly done #8703, FlorentHivert?)
- Basic framework for operads (FlorentHivert? + FredericChapoton?)
- Plan for cleanup of Posets + category for partially ordered sets (FlorentHivert? + FrancoSaliola?)
- #8876: Generalize #7914 (Florent; 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 covariant functorial construction (NicolasThiéry?, in good progress)
- (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?)
- (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
- Design and implement framework for computing with representations / modules / character rings
- Finalize interface to Jean-Éric Pin's Semigroupe package (#8360), and extend further the semigroup/monoid/group algebra code (#6654, ...)
- Explore / expose the functionalities of KBMAG for computing with (semi)groups defined by presentations
- Discussion about implementation of various algebras (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.
- Categorification of the crystal code (AnneSchilling?) #8911
- Words improvements:
- 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?)
- #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
*#8259: Conversion from symmetric polynomials to basis of monomial symmetric functions
- 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!
- 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)
- 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