wiki:SageCombinatRoadMap

Version 52 (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% #10622
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

  • #10622: Improve combinatorial species / decomposable classes
  • Basic support for operads (depends on #10622)
  • Improve Trees
  • Generating series, analytic combinatorics, ...:
    • Implement MacMahon? partition analysis, aka Omega operator (#10669)
    • Review #10519: Computation of asymptotics for multivariate rational fractions
  • Cleanup of combinatorics
    • Goal: deprecate the old CombinatorialClass?
    • In practice, all classes that currently inherit from CombinatorialClass should instead inherit from Parent and register themselves in one of the categories (*EnumeratedSets, *FiniteEnumeratedSets, or *InfiniteEnumeratedSets). For examples, see e.g. FiniteEnumeratedSets().example().
    • Expected benefits:
      • Support for TestSuite?
      • Support for conversions, coercions, and morphisms, in particular for bijections (as morphisms in the category of Sets with bijection, with properly defined domain and co-domain rather than python functions).
    • Steps:
      1. Let CombinatorialClass inherits from Parent (mostly done #8910)
      2. For each CombinatorialClass C:
        • Have C inherit directly from Parent
        • Ensure that C.__init__ sets up the proper category (Finite|Infinite)...
        • Add TestSuite(C).run() to the doctests and make all the tests pass
        • Have a properly setup attribute C.Element and use C.element_class (as defined by the categories) when constructing elements
        • Ensure proper unique representation behavior by having C inherit both from UniqueRepresentation and Parent
      3. Deprecate and remove CombinatorialClass
      4. Turn all the factory functions into factory classes by mean of ClasscallMetaClass; see PerfectMatching and Trees for an advanced example.
    • Reimplement iteration of subsets/set partitions (too slow!): implementation of a Python extension in C + inclusion in Sage (VincentDelecroix?, #10534)
    • Reimplement from scratch IntegerListsLex?, fixing its 8-year old bugs

Former road maps and history

  • Todo for/at the joint Sage-Combinat/Chevie? workshop (June 2010):
    • #8380: Finalize and merge the interface with GAP3
    • #6588: Categorification of root systems (NicolasThiéry?)
      • Make Root and WeightLatticeRealization? into categories
      • Declare the various embeddings as coercion/conversions
      • Define and use an overloaded operator for the scalar product (depends on (7) above)
      • See preliminary patch in the Sage-Combinat queue
    • Constructing a root/coroot lattice realization from pair of matrices (Volunteers?)
    • Automatic finite Coxeter/(affine)Weyl type recognition, using graph isomorphism with predefined cartan types (complex reflection group is harder) (Volunteers?)
    • Computation of reflection degrees (easy; NicolasThiéry? or any volunteer)
    • #8359: Finalize permutation representation of a Coxeter group
    • #8347: Positivity testing for cyclotomic fields. See also #8327: implement the universal cyclotomic field, using Zumbroich basis
    • Implement general Coxeter groups given by Coxeter diagram (depends on #8347)
    • Port over the character tables (depends on 1 to be most useful)
    • Representations/character tables of the Hecke algebra
    • Interface to Coxeter 3 from Fokko Ducloux (MikeHansen?)
    • 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
  • Todo for/at Sage Days 20.5 (May 2010):
    • Review of #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout (VincentDelecroix?)
    • Finalize the basic Cython data-sctructure for combinatorial objects (in progress #8702, FlorenHivert?)
    • Finalize the cleanup of combinatorial object: permutations, partitions, compositions...(First step: #6655 FlorentHivert?)
    • Trees (mostly done #8703, FlorentHivert?)
    • Basic framework for operads (FlorentHivert? + FredericChapoton?)
    • Plan for cleanup of Posets + category for partially ordered sets (FlorentHivert? + FrancoSaliola?)
    • #8876: Generalize #7914 (Florent; depends on #7938)
      • 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?
    • (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))
    • (8) Refactor the support for covariant functorial construction (NicolasThiéry?, in good progress)
    • (9) Implement the Sub / Quotient / Subquotient functorial constructions (FlorentHivert??, depends on (8))
    • (10) Implement Sub and Quotient of finite dimensional free modules / algebras / ... (FlorentHivert??, depends on #7938 and #7914 with generalization)
    • #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:
      • #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):
    • Merge #7921 and #8001 in Sage 4.2.2: Categories for extension types via getattr_ + tests(Robert, NicolasThiéry?)
    • Merge #7938 in Sage 4.2.2: swap_term_and_monomial (JasonBandlow?)
    • Rebase, finalize and merge #7004: Refactor the graph layout code, and add interface with graphviz for acyclic layout (Robert Beezer)
    • Finalize #7914: Triangular isomorphisms of free modules (JasonBandlow?)
    • #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
  • 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

  • P1050207.JPG Download (807.6 KB) - added by nthiery 13 months ago. Roadmap in May 2010 (Sage Days 20.5, Toronto)