wiki:SageCombinatRoadMap

Version 44 (modified by hivert, 3 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

Timeline

  • December 2000: Birth of  MuPAD-Combinat
  • 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.
  • June 2007: design discussions between Nicolas and Mike at the Axiom Workshop 2007
  • January 2008: presentation of MuPAD-Combinat at the AMS meeting in San-Diego; meeting and discussions with the Sage team
  • 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.
  • June 19th 2008: Visit of Florent to Davis. Final decision to migrate!
  • June 24th 2008, FPSAC (Valparaiso, Chile):
    • Official announcement of the migration
    • Goal: elementary combinatorics users can start directly with Sage
  • Summer 2008: port of decomposable objects (from MuPAD-combinat) / species (from aldor-combinat) by Mike Hansen, funded by Google
  • 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.
  • 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
  • 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
  • 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
  • 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?)
    • 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/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 list for the cleanup of combinatorics part

The goal here is to have the combinatorial classes to be Parent in the proper category (*EnumeratedSets?) and their element to be Element. The expected benefice includes to make it possible to use TestSuite? and coercion, and to have bijection to be morphisms (in the category of Sets with biijection) with correctly defined domain and co-domain rather than python functions.

1 - let CombinatorialClass? ihnerits from Parent (mostly done #8910)

2 - for each CombinatorialClass? C:

  • Ensure to have C.init give the proper category (Finite|Infinite)...
  • Add TestSuite?(C).run() to the doctests and make all the tests pass
  • have properly setup C.Element and let element_class to be set by the categories
  • remove the inheritance from CombinatorialClass?

3 - turn all the factory functions into factory classes by the mean of ClasscallMetaClass?

Progress of the migration to Sage

Topic Progress Priority Comments
Basic combinatorial classes 75% 2007-08 by Mike
Decomposable objects / Species 75% Google summer of code 2008 by Mike
Trees 20%
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 50%
Algebra (desosseur, ...) 0%
* with several bases 0%
Operads 0%
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%
GLIP 50% Deprecated by Robert's generic code (also funded by Google)
dot2tex 10% Delegated to the SAGE graph theorists
Copy-on-write data structure 30%
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

Attachments

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