wiki:SageCombinatRoadMap

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

--

Roadmap and status report for Sage-Combinat

This page is an attempt at drawing a road map for Sage-Combinat, starting with the migration from MuPAD-Combinat.

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

All Sage-Combinat tickets

Progress of the migration from MuPAD to Sage

Topic Progress Comments
Basic combinatorial classes 75% 2007-08 by Mike
Decomposable objects / Species 75% #10662
Trees 30%
Posets 100%
Words 100%
Symmetric functions 90%
k-Schur & 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 quasi-symmetric 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
  • Monoids, algebras, and their 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 and semigroups
      • #12914 (prototype): Representation theory of finite semigroups
      • #8360 (needs finalization) interface to Jean-Éric Pin's Semigroupe package
      • #12915: Interfaces to the GAP packages KBMag (and to Monoids, Citrus, ...)
    • Calculus on modules (direct sums, tensor products, induction, restriction, quotients, radical, ...) (in progress for semigroups)
    • Tower of algebras: representations, Grothendieck rings, ...
    • Group algebras:
      • #10305 (prototype): Add rings for the center of the symmetric group algebras Mathieu Guay-Paquet, Valentin Feray
      • #6654 (prototype): new features in group algebra category Valentin Feray
    • Path algebras:
      • #9889 (prototype): A new module implementing Monomial Algebras
      • #12630 (needs review): Representations of quivers and quiver 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
  • 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 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:
    • Implement more models of Crystals?
    • #11305 (prototype): Bijection between Rigged Configurations and Crystal Paths (Travis Scrimshaw)
    • #12251 (needs finalization): Implementation of Littelmann path model for crystals (Anne Schilling, Mark Shimozono, Reda Chhaibi)
  • 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 Cohen-Macaulay 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, ...)
  • Enumerative combinatorics
    • #10662: Improve combinatorial species / decomposable classes
    • Basic support for operads (partially depends on #10662) (FlorentHivert?, FredericChapoton?)
    • Analytic combinatorics:
      • #10669: MacMahon? partition analysis, aka Omega operator (Jason Bandlow, Greg Musiker)
      • #10519 (needs review): Computation of asymptotics for multivariate rational fractions
      • guessing (Martin Rubey?)
      • automatic summation (Burcin Erocal)
    • Posets:
      • #12848: Bug in order_ideal_complement_generators: 'down'
      • #12916: Dedekind-MacNeil? completion of finite posets
      • Support for lazy/infinite 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 8-year old bugs
      • Trees (Florent Hivert):
        • #8703 (needs review): Improve Trees
        • #11529 (needs review): Rooted_trees
      • #12250: Combinatorics of k-tableaux 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/sp-s13/
  • 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
  • Sage-Combinat workflow:
    • Write down the properties we want our workflow to have, and improve it!

History

  • 2011:
    • #8702: Fast datastructure for (combinatorial) objects with prototype (clone) design pattern (Florent Hivert)
    • #11290: Implementation of non-commutative k-Schur functions in the nilCoxeter algebra (Anne Schilling, Chris Berg)
    • Documentation: #11251, #11282
    • Debugging, profiling: #11287
    • Installation: #11296
    • Posets: #10065, #11293
    • Combinatorics: #11300, #11301, #11314
      • #11742, #11700: Cores (Anne Schilling)
      • #10155: Cyclic sieving phenomenon (Christian Stump)
    • Certainly many more!
    • Crystals:
      • #11546: Energy function for Crystals (Anne Schilling)
      • #11183: Stembridge rules (Tom Denton)
      • #10485: Thematic tutorial (Anne Schilling)
      • #10446: Schutzenberger involution, promotion, etc (Anne Schilling)
      • #8442: Lie tutorial (Dan Bump)
  • 2008: Switching to Sage!
    • October: 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: 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 final stable release of MuPAD-Combinat dropped.
  • Port of decomposable objects (from MuPAD-combinat) / species (from aldor-combinat) 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!
  • 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 MuPAD-Combinat at the AMS meeting in San-Diego; 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 MuPAD-Combinat, 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.
  • 2006-2008: Aldor-Combinat
    • Species (Martin Rubey, Ralf Hemmecke)
  • 2000-2008: 100k lines of code in MuPAD-Combinat, 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 MuPAD-Combinat

Attachments (1)

Download all attachments as: .zip