| Version 58 (modified by nthiery, 14 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
- #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
- #10305 (prototype): Add rings for the center of the symmetric group algebras Mathieu Guay-Paquet, Valentin Feray
- Root systems
- #8906 (needs finalization): Optional package for gap3
- Constructing a root/coroot lattice realization from a pair of matrices Work in progress by Christian Stump
- Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder)
(Volunteers?)
- Computation of reflection degrees from positive roots (easy)
- #8359 (needs finalization): permutation representation of a Coxeter group, using GAP3
- #8327 (needs review): implement the universal cyclotomic field, using the Zumbroich basis Christian Stump
- Implement general Coxeter groups given by a Coxeter diagram
- #12912: Interface to Coxeter 3 from Fokko Ducloux (MikeHansen?)
- Port over the character tables (depends on 1 to be most useful)
- Representations/character tables of the Hecke algebras
- #12774: (needs review): various enhancements for Coxeter and Weyl groups
- 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
- 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, ...
- Modules and vector spaces
- Tensor products of morphism
- Generalized tensor product
- #10673: Roadmap for (Combinatorial)FreeModule?
- #11111 (needs finalization): More support for finite dimensional free modules and algebras
- Categories
- #10963: More functorial constructions (NicolasThiéry?)
- 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
- #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):
- Finalize the basic Cython data-sctructure for combinatorial objects (in progress #8702, FlorenHivert?)
- Finalize the cleanup of combinatorial object: permutations, partitions, compositions...
- #8876: Generalize #7914 (Florent)
- 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?
- phi.preimage(y): returns the preimage x of y or None if it does not exists (or raise an exception?)
- (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))
- #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):
- #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:
- Symmetric functions and generalizations:
- #10333: Interface for lrcalc
- Categories: #9469, #8119, #12527
- 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
- Symmetric functions and generalizations:
- 2011:
- #8702: Datastructure for objects with prototype (clone) design pattern.
- 2010:
- #6655: Cleanups and new features about corners and cells in partition and tableau
- Root systems, crystals, ...
- Categories:
- Symmetric functions:
- #8259: Conversion from symmetric polynomials to basis of monomial symmetric functions
- #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout
- 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)
- 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 14 months ago.
Roadmap in May 2010 (Sage Days 20.5, Toronto)
