Version 58 (modified by nthiery, 3 years ago) (diff) 

Roadmap and status report for SageCombinat
This page is an attempt at drawing a road map for SageCombinat, and in particular the migration from MuPADCombinat.
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%  200708 by Mike  
Decomposable objects / Species  75%  #10662  
Trees  30%  
Posets  %  
Words  %  
Symmetric functions  90%  
kSchur & 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  
Copyonwrite 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 quasisymmetric 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 GuayPaquet, 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 semisimple 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 8year old bugs
Former road maps and history
 Todo for/at Sage Days 20.5 (May 2010):
 Finalize the basic Cython datasctructure 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 breathfirstsearch 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 nilTemperleyas.patch in the sagecombinat 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 SageCombinat
 Goal: All new users can start directly with Sage
 October 08: Sage Days 10 (Nancy, France)
 Get the core MuPADCombinat 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 MuPADCombinat developers.
 Plan for a last stable release of MuPADCombinat dropped.
 Summer 2008: port of decomposable objects (from MuPADcombinat) / species (from aldorcombinat) 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 MuPADCombinat at the AMS meeting in SanDiego; 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 MuPADCombinat, 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 MuPADCombinat
Attachments (1)

P1050207.JPG
(807.6 KB) 
added by nthiery 3 years ago.
Roadmap in May 2010 (Sage Days 20.5, Toronto)
Download all attachments as: .zip