wiki:SageCombinatRoadMap

Version 59 (modified by nthiery, 2 years 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

All Sage-Combinat tickets

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

  • 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
      • #12914 (prototype): Representation theory of finite semigroups
      • #8360 (finalize) interface to Jean-Éric Pin's Semigroupe package
      • #12915: Interfaces to the GAP packages KBMag (and to Monoids, Citrus, ...)
    • Group algebras:
      • #10305 (prototype): Add rings for the center of the symmetric group algebras Mathieu Guay-Paquet, Valentin Feray
      • #6654: new features in group algebra category Valentin Feray
    • Path algebras:
      • #9889 (prototype): A new module implementing Monomial Algebras
  • Experiment with KBMAG / PLURAL (see #4539) to implement various algebras like 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.
  • Root systems:
    • #8906 (needs finalization): Optional package for gap3
    • Integrate/interface PyCox?
    • Root systems:
      • Constructing a root/coroot lattice realization from a pair of matrices Work in progress by Christian Stump
      • Allows a generalized Cartan matrix as input for Dynkin diagrams
    • 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: 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
  • Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder)

(Volunteers?)

  • #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: Bijection between Rigged Configurations and Crystal Paths
    • #12251: Implementation of Littelmann path model for crystals
  • Cluster algebras (Christian Stump, ...):
    • #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:
    • Generalized tensor product
    • #10673: Roadmap for (Combinatorial)FreeModule?
    • #11111 (needs finalization): More support for finite dimensional free modules and algebras Depends on #8678
    • #8678: module morphisms (tensor products, inverses, ...)
  • Categories & coercion:
  • #10963: More functorial constructions (NicolasThiéry?)
  • #10668, #10667: Cleanup support for morphisms
  • (prototype) Implement multiparameter morphisms This could be extracted and finalized without much work
  • #8900 (prototype): Implement multiparameter overloaded functions, with explicit registration Depends on #7420; #383 is not enough NicolasThiery?
  • #7420 (prototype): Use breath-first-search or Dijkstra in Coercion, as discussed in (volunteers?) NicolasThiery?
  • Combinatorics
  • Generating series, analytic combinatorics, ...:
    • #10669: MacMahon? partition analysis, aka Omega operator
    • #10519 (needs review): Computation of asymptotics for multivariate rational fractions
  • Trees:
    • #8703 (needs review): Improve Trees
    • #11529 (needs review): Rooted_trees

Former road maps and history

  • Todo for/at Sage Days 20.5 (May 2010):
    • Design and implement framework for computing with representations / modules / character rings
  • Words improvements:
    • #8595, #8618, #8574, #8673 and #8674 (misc defect fixes),
    • #8429 (Split word.py file into 4 files),
    • #8604 (Add a class for factor-enumerable words),
    • #8407 and #8670 (new methods for word paths),
    • #8287 (_check makes it slower),
    • #8431 (Rauzy fractal (discrete planes and broken lines)
  • 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
  • 2011:
  • 2010:
    • Root systems, crystals, ...
      • #8984: Implementation of the Lenart--Postnikov alcove path crystal
      • #8380: Interface with GAP3
      • #8911: Categorification of Crystals
    • Categories, parents, elements:
    • Symmetric functions:
      • #8259: Conversion from symmetric polynomials to basis of monomial symmetric functions
    • 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)
  • 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!
  • 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.

Attachments (1)

Download all attachments as: .zip