Version 69 (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, starting with the migration from MuPADCombinat.
Please feel free to edit this page to add more items, or add your names for topics you contributed to or would be interested in contributing to (this helps knowing who does what and who to contact for further collaborations).
Overview
Progress of the migration from MuPAD to Sage
Topic  Progress  Comments 
Basic combinatorial classes  75%  200708 by Mike 
Decomposable objects / Species  75%  #10662 
Trees  30%  
Posets  100%  
Words  100%  
Symmetric functions  90%  
kSchur & the like  90%  
Root systems / ...  90%  
Crystals  90%  
Category framework  100%  
Hopf algebra framework  80%  
Free modules & such  80%  
Algebra (desosseur, ...)  50%  
Operads  15%  
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  95%  #10333 
GLIP  50%  #6812 
graphviz / dot2tex  80%  #7004, #10518 
Database access  100%  
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 
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
 #11929 (prototype): Implement quasisymmetric functions (JasonBandlow?, Franco Saliola, Chris Berg)
 #8899 (prototype): Implement Non Commutative Symmetric Functions (JasonBandlow?, Franco Saliola, Chris Berg, LenniTevlin?, MikeZabrocki?)
 #11979 (prototype): Divided power algebras (Bruce)
 (prototype) Implement Schubert polynomials (Viviane Pons, AdrienBoussicault?, Nicolas Borie)
 #6889 (prototype): Invariant rings of permutation group
 Implement more generic algorithms:
 Antipode defined recursively
 Product and coproduct defined by duality
 Group like elements from primitive idempotents
 Kac algebras
 Quantum groups
 Planar algebras
 Symmetric Functions
 Monoids, algebras, and their representation theory:
 Finite dimensional algebras:
 Decomposition of the center, construction of central idempotents (as in MuPADCombinat)
 Quiver, Cartan matrix, radical filtration (as in MuPADCombinat)
 Depends on: #11111
 Finite monoids and semigroups
 Calculus on modules (direct sums, tensor products, induction, restriction, quotients, radical, ...) (in progress for semigroups)
 Tower of algebras: representations, Grothendieck rings, ...
 Group algebras:
 Path algebras:
 Experiment with KBMAG / PLURAL / Letterplace (see #4539) to easily implement algebras like affine nilCoxeter algebra, affine nilTemperley Lieb algebra, affine local plactic algebra).
 Free monoids, free groups (#12339), free algebras (see #7797)
 #7797 (needs review): Full interface to letterplace from singular
 Finite dimensional algebras:
 Root systems, Coxeter groups, Hecke algebras:
 #8906 (needs finalization): Optional package for gap3
 Integrate/interface PyCox?
 Root systems:
 #12882 (prototype): Allows a generalized Cartan matrix as input for Dynkin diagrams Work in progress by Christian Stump Christian Stump
 Constructing a root/coroot lattice realization from a pair of matrices Christian Stump
 #12838 (needs finalization): Root poset should treat type A1 properly Christian Stump
 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 (needs finalization): 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
 #11109 (prototype): Stable grothendieck polynomials in type A affine (Nicolas Thiéry)
 Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder)
 #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 semisimple 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, Greg Musiker, Hugh Thomas):
 #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 CohenMacaulay test for simplicial complexes
 Modules and vector spaces:
 #10673: Roadmap for (Combinatorial)FreeModule?
 #11111 (needs finalization): More support for finite dimensional free modules and algebras Depends on #8678 and #10963
 #8678 (needs finalization): module morphisms (tensor products, inverses, ...)
 Tensor products over an algebra, and application to representation theory
 #9280: graded modules
 Graded morphisms of modules (inverse, adjoint, ...)
 Categories & coercion:
See also the Categories Road Map
 #10963: More functorial constructions NicolasThiéry?
 #10668, #10667: Cleanup support for morphisms NicolasThiéry?, SimonKing?
 (prototype) Implement multiparameter morphisms This could be extracted and finalized without much work Nicolas
 #8900 (prototype): Implement multiparameter overloaded functions, with explicit registration Depends on #7420; #383 is not enough NicolasThiery?
 #7420 (prototype): Use breathfirstsearch or Dijkstra in Coercion, as discussed in (volunteers?) NicolasThiery?
 #11935: Make parent/element classes independent of base rings SimonKing?, NicolasThiery?
 Enumerative combinatorics
 #10662: Improve combinatorial species / decomposable classes
 Basic support for operads (partially depends on #10662) (FlorentHivert?, FredericChapoton?)
 Analytic combinatorics:
 Posets:
 Enumerated sets and combinatorial objects:
 #12913: Deprecate CombinatorialClass? in favor of the EnumeratedSet?'s categories
 #5268: Further cleanup of Enumerated sets
 #10193: graded/... enumerated sets
 #10194 (needs review): Set factories (Florent Hivert)
 #11407 (prototype): Add normalization to clonable lists (Florent Hivert)
 Optimization: use ClonableIntArray? and friends for all combinatorial object: permutations, partitions, compositions...
 Fix everything from: http://wiki.sagemath.org/combinat/Weirdness In particular cleanup permutations!!!!
 #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
 Trees (Florent Hivert):
 #12250: Combinatorics of ktableaux and the like (Anne Schilling, Mike Zabrocki)
 Dynamics (Vincent Delecroix)
 Rauzy fractals, ...
 Flat surfaces, origamis
 Interval exchange transforms
 Languages (Vincent Delecroix, ...)
 Automorphic Forms, Combinatorial Representation Theory, and Multiple Dirichlet Series ICERM http://icerm.brown.edu/sps13/
 Tutorials
 Merge in Sage as many of our tutorials
 Notebook and help (is this a tutorial or a primer?)
 Calculus and Linear algebra
 Combinatorics (to be taken from «Calcul Mathématique Avec Sage») NicolasThiery? and Hugh Thomas
 Merge in Sage as many of our tutorials
 SageCombinat workflow:
 Write down the properties we want our workflow to have, and improve it!
History
 2012:
 Optimizations:
 #11115: Rewrite cached_method in Cython
 Symmetric functions and generalizations:
 #10333: An interface to Anders Buch's LittlewoodRichardson Calculator lrcalc
 Categories: #9469, #8119, #12527, #12877, #11943
 #4539: Plural wrapper for skew commutative Gröbner bases
 Coercion: #11250, #11257
 Enumerated sets: #11118
 Posets: #10998 (Categorification), #12476, #12677, #10670, #11382, #12536 (Linear extensions), #12831 (products)
 Optimizations:
 Modules and vector spaces: #12464, #12484, #12489, #12528
 Root systems:
 #12667: RootLatticeRealizations?: infinite loops while trying to reflect to the positive chamber
 #10817: Generalized associahedron as a polyhedral complex
 #6588: Categorification of root systems
 Quivers: #10349, #10347
 Sphinx, Documentation: #9128, #12717, #12849, #12490
 #7980: Implement generic support for parents with (multiple) realizations
 2011:
 #8702: Fast datastructure for (combinatorial) objects with prototype (clone) design pattern (Florent Hivert)
 #11290: Implementation of noncommutative kSchur functions in the nilCoxeter algebra (Anne Schilling, Chris Berg)
 Documentation: #11251, #11282
 Debugging, profiling: #11287
 Installation: #11296
 Posets: #10065, #11293
 Combinatorics: #11300, #11301, #11314
 Certainly many more!
 Crystals:
 2010:
 The road map in May 2010 (Sage Days 20.5, Toronto)
 Symmetric functions:
 Root systems, crystals, ...
 Categories, parents, elements:
 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:
 Enumerated sets:
 #8519: NN, NonNegativeIntegers?, PositiveIntegers?, IntegerRange? Nicolas Borie
 #6655: Cleanups and new features about corners and cells in partition and tableau
 #6775: Disjoint set data structure
 Words:
 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
 #8595, #8618, #8574, #8673 and #8674 (misc defect fixes)
 #8429 (Split word.py file into 4 files)
 #8604 (Add a class for factorenumerable words)
 #8407 and #8670 (new methods for word paths)
 #8287 (_check makes it slower)
 #8431 (Rauzy fractal (discrete planes and broken lines)
 2009:
 Category framework (#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 combinatorics (#4549, #5200, #5308, #5487, #5534, #5551, #5781, #5600, #6000, #7403, #7395, #7396, #7397) (FlorentHivert?, NicolasThiéry?, ...)
 #6136: Implementation of FreeModule? / Hopf algebra framework
 Refactoring of symmetric functions (#5457, #6137, #7777) (NicolasThiéry?, JasonBandlow?)
 #6138: Refactoring of the SymmetricGroupAlgebra? to use categories and free modules
 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: 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
 2008: Switching to Sage!
 October: 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: 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 final stable release of MuPADCombinat dropped.
 Port of decomposable objects (from MuPADcombinat) / species (from aldorcombinat) by Mike Hansen, funded by Google Summer of Code
 June 24th, FPSAC (Valparaiso, Chile):
 Official announcement of the migration
 Goal: elementary combinatorics users can start directly with Sage
 June 19th: Visit of Florent to Davis. Final decision to migrate!
 May: Fixed several of the Weirdness issues (#3286, JasonBandlow?)
 Spring, 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: 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: presentation of MuPADCombinat at the AMS meeting in SanDiego; meeting and discussions with the Sage team
 2007: Early contacts with Sage
 June: design discussions between Nicolas and Mike at the Axiom Workshop 2007
 February: First contact with Mike Hansen who wanted to port some features of MuPADCombinat, which we very much encouraged. In the following month, Mike translated 30k lines of code, which accounts for most of the basic combinatorics (tableaux, permutations, ...), and symmetric functions.
 20062008: AldorCombinat
 Species (Martin Rubey, Ralf Hemmecke)
 20002008: 100k lines of code in MuPADCombinat, 20 contributers, 25+ papers
 Symmetric functions (François Descouens, NicolasThiery?, ...)
 NCSF, QSym, Hopf algebras, Kac algebras, Operads (Florent Hivert, NicolasThiery?)
 Crystals (Anne Schilling, ...)
 Root systems, Weyl groups (NicolasThiery?, ...)
 Representation theory of algebras (Florent Hivert, ...)
 Enumerative combinatorics (tableaux, compositions, trees, ...)
 Decomposable classes/species (NicolasThiery?, ...)
 Coercion system (NicolasThiery?)
 Categories for algebraic combinatorics (NicolasThiery?)
 Graph & Graphviz (Teresa Gomez Diaz)
 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