Consider performing a Preparation of the Partner University Fund application
Last year, we applied with Anne Schilling for a PUF grant around Sage-Combinat:
The application failed, but the organizers warmly recommended to apply again this year. This is a three years grant that can fund travel, short to long term accommodation, meeting expenses to encourage exchanges between France and the USA, especially for grad students and postdocs, and possibly some hardware. The application deadline is December 15th, with the grant starting around March/April.
Here is the current draft of project, as a call for suggestions. Please highlight your edits and comments in bold!
1 / PROJECT
TITLE OF THE PROJECT:
*-Combinat: boosting open source research-driven mathematical software for algebraic combinatorics
US INSTITUTION:
UC Davis
FRENCH INSTITUTION:
Faculté d'Orsay, Université Paris-Sud
Level(s)*: Master PhD Postdoctoral Research
Subject Area(s)*:
*Projects may include several subject areas
Mathematics, IT and applications XXX
4.3 / OTHER GRANT(S) REQUESTED OR ALREADY OBTAINED FOR THIS PROJECT
The *-Combinat platform was adopted for the computational aspects of
two NSF Focused Research Groups:
- "Affine Schubert Calculus: Combinatorial, geometric, physical, and
computational aspects" led by Jennifer Morse, Anne Schilling, and
Mark Shimozono (2007-2010)
- "Combinatorics of crystals: geometric, physical, and computational
applications" led by Cristian Lenart, Anne Schilling, Mark Shimozono,
and Julianna Tymoczko (2010-2013, submitted).
These many-faceted international projects involve and tie together
various problems from combinatorics, geometry, representation theory,
physics, and computation. Many investigations in these areas are
largely fueled by extensive computational experimentation. The robust
implementation of algorithms derived from the projects leads to the
development of new libraries for computer algebra systems. The open
source dissemination of this new software not only advances the
research program but also has an outreach impact on the mathematics,
physics, and computer science communities.
As part of the first NSF project, Nicolas M. Thiéry spent the academic
year 2007-2008 at UC Davis and spent again 6 months there in Spring
2009.
Anne Schilling was invited through the Kastler foundation to the
University Marne-la-Vallee in November 2006 (hosted by Jean-Christophe
Novelli) and to Universite Orsay, Paris-Sud in November 2008 (hosted by
Nicolas M. Thiéry).
*-Combinat is also the software underlying the French Non thematic ANR
project "blanc" ANR-06-BLAN-0380 which involves, among others, Florent
Hivert, Jean-Christophe Novelli, and Franco Saliola.
Combinatorial Hopf algebras, operads and props:
Combinatorial Hopf algebras are Hopf algebras whose bases are indexed
by combinatorial objects. They can be seen as generalizations of the
Hopf algebra of symmetric functions. The latter plays a fundamental
role in numerous theories such as group representations (as characters
of finite and Lie groups, spherical functions of complex groups, real
and p-adic), algebraic topology (cobordism rings), algebraic geometry
(Schubert calculus) and mathematical physics (integrable system,
vertex operators).
In the last couple of years, several such Hopf algebras appeared in seemingly
unrelated domains. They appear naturally in operads theory since each operad
verifying some simple conditions gives rise to a Hopf algebra. They also
appear in combinatorics when one tries to lift certain computations on polynomials
to a non-commutative level to get combinatorial interpretations of multiplicities.
Moreover, since the work of Connes and Kreimer on renormalization, they appear
regularly in mathematical physics.
The goal of this ANR project is to not only provide the theoretical foundation of
combinatorial Hopf algebras but also to find new algorithms needed for
computer exploration during research, and which can be used for
applications in physics (computation of perturbation series to a high
order).
5 / PROJECT DESCRIPTION AND RATIONALE
(TEXT BOXES BELOW ARE EXPANDABLE. HOWEVER PLEASE REMAIN AS CONCISE AS POSSIBLE)
5.1 / Objectives of the partnership
Algebraic combinatorics is a field of mathematics which is
interdisciplinary by nature and has deep connections with many other
areas, and in particular computer science and theoretical physics.
Due to the concrete and constructive approach, computer exploration
has been playing an increasing role as a guide for research ever since
Marcel-Paul Schützenberger introduced it in 50's.
The involved computations vary a lot, requiring a wide range of tools
as well as, more often than not, specific development by the
researchers. Given the increasing scale and level of complexity, it
has become essential to share the development efforts and capitalize
on those in a well organized body of code.
This is the purpose of the *-Combinat project, which was founded in
2000 by Florent Hivert and Nicolas M. Thiéry; it has now reached
maturity, and has become a major tool in the field with 30+
researchers involved worldwide. This project is by nature research
driven and already led to 50+ publications.
In 2000, there was no viable open-source mathematical platform, and
the project started as the package MuPAD-Combinat
(http://mupad-combinat.sf.net) for the computer algebra system MuPAD
(http://www.mupad.de). Meanwhile, Sage appeared
(http://www.sagemath.org/), a completely open source general purpose
mathematical software (similar to Maple, MuPAD, Mathematica, and up to
some point matlab) based on the popular python programming language.
Sage is gaining strong momentum in the math community, and we decided
in June 2008 to migrate our project under the name Sage-Combinat (see
http://wiki.sagemath.org/combinat). This move by itself attracted
many new developers, and half of the code has readily been
ported. However there still is a massive amount of work left, which
must be carried out swiftly in order to support continuous use by the
community for research. At the same time, care needs to be taken in
laying out strong foundations for the future, and new features are
continuously needed.
The purpose of the PUF project is to provide short to mid-term funding
to boost the international development of Sage-Combinat around the
bipole France-America during this critical period. The key is
communication and coordination; therefore the primary needs are
mobility (in particular of graduate students and postdocs),
organization of regular workshops, and hardware for collaborative
development tools.
5.2 / History of the partnership (if applicable)
Anne Schilling joined the *-Combinat development team after meeting
with Nicolas Thiéry in the international conference FPSAC in July
2006. Shortly after, Anne Schilling was invited for one month in
Marne-la-Vallée, where she worked with Jean-Christophe Novelli on
problems related to symmetric functions and started the discussion
about implementation details for a crystal library in *-Combinat with
Nicolas Thiéry.
Later on, *-Combinat was chosen as research platform for a three year
(2007-2010) NSF Focused Research Group under the lead of Anne
Schilling and others; see
http://garsia.math.yorku.ca/dokuwiki/doku.php?id=start. This project
financed the visit of Nicolas M. Thiéry in Davis in 2007-2008 and in
Spring 2009. This visit fueled an active research collaboration
between UC Davis, Orsay, the University of Marne-la-Vallée and of
Rouen. It was also the occasion to build an active software
development collaboration, in particular with the University of
Washington and Stanford University. The decision to migrate *-Combinat
to Sage was taken during this period at the Mathematical Sciences
Research Institute in Berkeley.
5.3 / Departments/units involved
Math department, University of California at Davis, USA
Math department, University of Washington in Seattle, USA
Math department, University of Pennsylvania, USA
Math department, University of Minnesota, USA
Math department, Stanford University, USA
Laboratoire de Mathématiques d'Orsay, Université Paris Sud, France
Département d'informatique, Université de Rouen, France
Institut Gaspard Monge, Université de Marne-la-Vallée, France
Laboratoire Bordelais de Recherche en Informatique, Université Bordeaux 1, France
5.4 / Description of activites, including levels, timetable, and milestones
Here are some of the key areas that we want to improve in Sage-Combinat:
- Symmetric functions: this is the original flagship of
Sage-Combinat; the current implementation is feature reach, but
heavy refactoring is needed for further.
- Enumerative combinatorics: Sage-Combinat contains more than one
hundred predefined enumerated sets (partitions, permutations,
...). Deep refactoring and infrastructure work (combinatorial
factories, bijections) is crucial for further extensions.
- (affine) root systems, Coxeter and Weyl groups, Hecke algebras,
generalization to pseudo-reflection groups.
- Crystals, Lie algebras and their characters
- Combinatorial Species
- Posets
- Infrastructure for combinatorial Hopf and Kac algebras, with
noncommutative symmetric functions, ...
- Representation theory of semigroups and finite dimensional algebras.
For most of them, we have or will have soon a specific development
plan (design, algorithmic, personnel). For example, the upcoming Sage
days 20 at CIRM, in February 2009 will include sessions about root
systems, Hecke algebras, and semi groups, with specialists of those
fields on board (Andrew Mathas, author of Specht, Meinholf Geck,
coauthor of the Chevie package for GAP, and Jean-Éric Pin, author of
the SemiGroups package).
As per *-Combinat's tradition, all the development work is done with a
combination of a long term vision and of short term goals which are
strongly tied to research needs. Hence, even though all the topics
above will undoubtedly be needed at some point by the participants, it
would be impossible, and in fact prejudicial, to set specific
timelines.
The main purpose of this PUF project is to obtain flexible funding for
short to long term visits across the Atlantic. There are two typical
scenarios there: in the first one, two or more researchers (student,
postdoc, or faculty) are working on distinct research projects which
require the same computational tool. A short visit or very focused
workshop (3-8 people) will help them coordinate to setup the design
and foundations. By nature such workshops cannot be planned long in
advance; however experience gathered over the previous years calls for
about two of them every year on each side of the Atlantic.
In the second scenario, researchers gather to work together on a
common research project which requires software development. This
includes for example long visits of Tom Denton to Orsay (Spring 2010
and 2011), as part of his PhD (representation theory of crystals and
monoids) coadvised by Schilling and Thiéry. Postdoc positions are
also well suited for this, in particular since there is an
exceptionally large pool of excellent candidates for postdocs in
Orsay; this includes Jason Bandlow (symmetric functions), Brant Jones
(crystals and Hecke algebras), Robert Miller (graphs), Steve Pon
(affine Stanley symmetric functions), and Qiang Wang (posets, root
systems). Reciprocally, Nicolas Borie (root systems, Hecke algebras,
invariants) will be available in 2010-2011 for a postdoc in Davis. All
of them are regular contributors to Sage, and have expressed great
interest in participating in this project.
Parallel to this, regular workshops gathering the whole community will
be organized, including a yearly Sage-Combinat satellite workshops to
FPSAC, the primary international conference in algebraic
combinatorics. Those workshops focus on coding sessions in an extreme
programming setup, and introducing new users and developers to the
system. They also are the occasion to set and advertise important
milestones in the development. The previous such workshop was held in
July 2009 at RISC in Austria
(http://www.risc.uni-linz.ac.at/about/conferences/fpsac2009/), and
gathered 30 researchers. The upcoming ones are:
- FPSAC'10: San Francisco, USA, 2010
- FPSAC'11: Reykjavik, Iceland, 2011
- FPSAC'12: Nagoya, Japon, 2012
- FPSAC'13: Paris, France, 2013
The collaborative nature of the project requires advanced software
development tools (ticket server, distributed version control), as
well as heavy computational resources (compilation, regression
testing, time or memory demanding calculations). So far, we have been
using a server courtesy of the Sage team at the University of
Washington (combinat.sagemath.org). Scaling further will require its
replacement by a modern machine, which the Sage team agreed to host as
part of the Sage computation farm (which includes four GNU/Linux
servers with 24 cores and 128Gb of RAM). Unused resources will be made
available to the Sage-Combinat and Sage community at large. The Sage
team is committed to the ongoing administration of this server so that
it will continue to be a resource for the Sage-Combinat community well
after the end of this project (see the attached letter by William
Stein).
Budget rationale:
The main lines of the PUF-funded part of the budget follows the
activities listed above. This include one postdoc to France in Year 1
($60000), one post doc to the US in Year 2 ($45000), half a postdoc to
France in Year 3 ($40000), the purchase of a Sage-Combinat server
($20000), regular funding for Sage-Combinat workshops and meetings,
software development laptops for the long term visitors. It would
have been desirable to purchase the server right at the start of the
project, but the exceptional situation for postdocs (due to the
current state of the job market in the US) convinced us to hire in
priority a postdoc to France.
Most of the cofunding consists of the salaries of the main
participants N. M. Thiéry (1/2), F. Hivert (1/2), Nicolas Borie (1/2),
Anne Schilling (...), TODO: other people in Davis proportionally to
their involvement in the project, as well as the associated
overhead. We did not include in the budget some other major sources of
cofunding that are not yet secured. For example, the planned budget of
the NSF-FRG project "Combinatorics of crystals: geometric, physical,
and computational applications" which was submitted in September 2009,
includes cofunding of Sage-Combinat workshops and small meetings,
laptops for software development, postdocs involved in the development
of Sage-Combinat, etc. We also expect cofunding for Tom Denton's stay
in France from the American embassy and from the "Île de France"
Région. Finally, Sage-Combinat will be used in a variety of research
projects, which will fund personnel to participate to Sage-Combinat's
development and workshops. We did not include either the contribution
\emph{in kind} of the University of Seattle through the hosting and
administration of the Sage-Combinat server, which is extremely
valuable yet hard to estimate.
5.5 / Description of how the project will be sustained after the grant period
A major policy of *-Combinat is that its core developers have
permanent positions. In general, all the code is written by
researchers for their own research; therefore this activity is an
integral part of their research work. At the same time the code is
made visible and useable to others through the open-source
environment. This development model has proved its pertinence and
validity over the eight years of MuPAD-Combinat development, and by
the time PUF will be over Sage-Combinat will have reached its cruise
speed. Further development will then occur as part of many standard
research projects.
5.6 / If exchanges are INVOLVED, housing and other arrangements
5.7 / Originality, innovativeness of the project
There is a long tradition of software packages for algebraic
combinatorics, and to name but a few:
- SF, posets, coxeter/weyl (J. Stembridge, University of Michigan)
- Symmetrica (University of Bayreuth)
- ACE, mu-EC (University of Marne-la-Vallée)
- combstruct, gfun, ... (INRIA)
Each of those packages is developed by a small university team, if not
a single person, to tackle (very efficiently!) a specific problem
(symmetric functions, decomposable objects, generating series, ...).
The originality of *-Combinat lies in the following simultaneous focus:
- Offer a wide variety of interoperable and extensible tools,
integrated in a general purpose mathematical software, as needed
for daily computer exploration in algebraic combinatorics
- Be developed by a community of researchers spread around the world
and across institutions
Reaching this scale is a true challenge, as there is a simultaneous
need for mathematical and algorithmic expertise and for strong
computer science experience, in particular concerning the design and
the development model. For example, *-Combinat puts great emphasis in
high level programing techniques (object orientation and polymorphism,
iterators, functional programming) to obtain concise, expressive, and
easy to maintain code.
The migration to Sage is the occasion to reach yet another scale, with
a wider community and a long desired interoperability with tools from
other areas of mathematics (e.g. fast sparse exact linear algebra,
group theory, ...). This migration also makes *-Combinat into the
first large scale top-to-bottom open source package for algebraic
combinatorics.
6 / OUTCOMES OF THE PROJECT
6.1 / Expected outcomes of this project: Joint and dual degrees, educational initiatives, PUBLICATIONS; COMMUNICATIONS; symposiums
- Coadvised PhD (and possible dual degree) for Tom Denton (Orsay and
UC Davis). In general, all the mobility will be very beneficial to
the students and postdocs.
- In keeping with the *-Combinat tradition, all the software
development is associated to mathematical research and leads to a
continuous stream of joint research publications.
- All the code produced by the Sage-Combinat community is released as
open source and integrated into Sage. This will give indirectly a
substantial push to the Sage project which has an enormous
potential for research and teaching at all university levels, as
well as industrial applications.
- Yearly large Sage-Combinat workshop, and regular smaller meetings.
6.2 / Regional perspectives: Existing or PLANNED PARTICIPATION in European/ North American programs; names and partners
6.3 / Other international perspectives
The NSF-FRG projects are international cooperative research ventures,
with core group members located in Canada, the United States, Chile,
and France, and interdisciplinary, involving mathematicians,
physicists, and computer scientists.
6.4 / Present or considered Industrial Perspectives
MuPAD-Combinat has been used for statistical software testing, but was
put aside recently due to licensing issue. The migration to an open
source platform will solve this, and open the door to further
applications.
6.5 / Monitoring of the partnership (suggested internal steps/procedures)
All the code is shared via a public mercurial patch queue server
(http://combinat.sagemath.org/patches), and is immediately available
as open source. Stable patches are integrated into Sage after a formal
review process, and can be monitored via the Sage trac server
(http://trac.sagemath.org/).
The overall development progress and the induced publications will be
tracked on the Sage-Combinat Wiki
(http://wiki.sagemath.org/combinat).
7 / ADDITIONAL INFORMATION (for joint research projects only)
Additional information can be uploaded together with the application
7.1 / TEAMS’ PRESENTATIONS
U.S : NAMES AND SHORT BIOS
University of California at Davis:
Anne Schilling *
University of California at Davis, Professor 2006-current
University of California at Davis, Associate Professor 2004-2006
University of California at Davis, Assistant Professor 2000-2004
Massachusetts Institute of Technology, CLE Moore Instructor 1999-2001
University of Amsterdam, postdoc 1997-1999
Brant C. Jones *
University of California at Davis, VIGRE Assistant Professor, 2007-present
University of Washington, PhD, 2002-2007
Synygy Inc. (Chester, PA), Senior Software Developer, 2002
PricewaterhouseCoopers (Fort Lee, NJ), Computer Systems Consultant, 1997-2001
Bard College, B.A. in Mathematics, 1993-1997
Andrew S. Berget *
University of California, Davis. VIGRE Postdoctoral Fellow (2009-)
University of Minnesota, PhD (2004-2009)
Wang Qiang *
University of California at Davis, graduate student 2004-2010
San Jose State University, mathematics student 2002-2004
Software Engineer 1994-2001
Dalian University of Technology, China, B.E. in Software Engineering 1990-1994
Steve Pon *
University of California at Davis, PhD, 2005-2010
University of California at San Diego, B.A. mathematics 2004
Tom Denton *
University of California at Davis, graduate student 2006-current
University of Oregon, mathematics student 2003-2006
University of Washington in Seattle:
Sara Billey *
University of Washington in Seattle, associate professor, 2003-present
Massachusetts Instituted of Technology, assistant/associate professor, 1998-2003
Massachusetts Instituted of Technology, postdoc, 1994-1998
University of California at San-Diego, PhD, 1994
William Stein *
Founder and head of Sage
UW, Assoc. Professor (with tenure), 2006-present,
UCSD, Assoc. Professor (with tenure), 2005-2006
Harvard University, Benjamin Peirce Assistant Professor, 2001-2005
Harvard University, NSF Postdoc, 2000-2001
UC Berkeley, 1995-2000
Andrew Crites
University of Washington, graduate teaching assistant, 2005-current
Mike Hansen
Translator of 30k lines of MuPAD-Combinat code to Sage
University of Washington, graduate student, 2008-2009
Robert L. Miller *
University of Washington, PhD, 2005-present
Syracuse University, 2001-2005
University of Pennsylvania:
Jason Bandlow *
University of Pennsylvania, lecturer, 2008-2011
University of California at Davis, NSF postdoc, 2007-2008
University of California at San-Diego, PhD, 2007
University of Minnesota:
Vic Reiner *
University of Minnesota, professor, 2001–present
University of Minnesota, associate professor, 1997–2001
University of Minnesota, assistant professor, 1993–1997
University of Minnesota, Dunham Jackson assistant professor, 1990–1993
Massachusetts Institute of Technology, Ph.D. in Mathematics 1986–1990
Stanford University:
Daniel Bump *
Professor of Mathematics, Stanford 1995-present
Associate Professor, Stanford 1990-1995
Assistant Professor, Stanford 1986-1990
Member, Institute for Advanced Study (Princeton) 1985-1986
Lecturer, The University of Texas (Austin) 1983-1985
PhD 1982 The University of Chicago
France : NAMES AND SHORT BIOS
Université Paris Sud:
Nicolas M. Thiéry *
Habilitation à diriger des recherches, December 2008
University of California at Davis, researcher, 2007-2008 and Spring 2009
Université Paris Sud, maître de conférences, 2004-current
IDEALX, Senior software developer, spring 2004
Université Lyon I, maître de conférences, 2001-2004
Colorado School of Mines, Postdoc, 1999-2000
Université Lyon I, PhD, 1996-1999
École Normale Supérieure (Paris), 1992-1996
Nicolas Borie *
Université Paris Sud, graduate student 2008-
Université de Rouen:
Florent Hivert *
Cofounder of *-Combinat
Professor, Université de Rouen, 2005-present
Habilitation à diriger des recherches, December 2004
Independent University of Moscou, Russia, chargé de recherches CNRS, 2003-2004
Université de Marne-la-Vallée, maître de conférences, 1999-2005
Université de Marne-la-Vallée, PhD, 1996-1999
École Normale Supérieure (Paris), 1991-1995
Université de Marne-la-Vallée:
Jean-Christophe Novelli *
Université de Marne-la-Vallée, professeur, 2007-present
Independent University of Moscou, Russia, détaché du CNRS, 2002-2003
Université de Marne-la-Vallée, chargé de recherche CNRS, 1999-2007
Habilitation à diriger des recherches, September 2001,
Université Paris VI, PhD, 1995-1999
École Normale Supérieure (Paris), 1993-1997
Adrien Boussicault*
Université de Marne-la-Vallée, PhD, 2005-2009
Marc Sage*
Université de Marne-la-Vallée, graduate student, 2007-current
École Normale Supérieure 2004-2008
Pierre Loic Meliot*
Université de Marne-la-Vallée, graduate student, 2007-current
École Normale Supérieure 2004-2008
Université Bordeaux 1:
Valentin Feray
Université Bordeaux 1, chargé de recherche CNRS, 2009-current
Université de Marne-la-Vallée, PhD, 2006-2009
École Normale Supérieure 2003-2007
7.2 / EQUIPMENT AVAILABLE FOR THE PROJECT
us:
Sage computational farm at Seattle (sagemath.org), which includes four
GNU/Linux servers with 24 cores and 128Gb of RAM.
france:
N/a
7.3 /Significant publications relative to the project
us:
- Florent Hivert, Anne Schilling, and Nicolas M. Thiéry.
Hecke group algebras as degenerate affine Hecke algebras.
Journal of Combinatorial Theory, Series A 116 (2009) 844--863
http://arxiv.org/abs/0804.3781
- Jason Bandlow, Anne Schilling, and Nicolas M. Thiéry.
On the uniqueness of promotion operators on tensor products of type a crystals.
Algebraic Combinatorics, to appear ( arXiv:0806.3131 [math.CO] )
http://arxiv.org/abs/0806.3131
- Anne Schilling
Combinatorial structure of Kirillov-Reshetikhin crystals of type D_n(1), B_n(1), A_{2n-1}(2),
J. Algebra 319 (2008) 2938-2962,
http://arxiv.org/abs/0704.2046
- Brant Jones and Anne Schilling
Affine structures and a tableau model for E_6 crystals
preprint arXiv:0909.2442 [math.CO], submitted.
FRANCE:
- Florent Hivert and Nicolas M. Thiéry
MuPAD-Combinat, an open-source package for research in algebraic combinatorics.
Sém. Lothar. Combin.,51 :Art. B51z, 70 pp. (electronic), 2004.
http://igd.univ-lyon1.fr/~slc/wpapers/s51thiery.html
- Anne Schilling and Jean-Christophe Novelli
The forgotten monoid
RIMS Kokyuroku Bessatsu B8 (2008) 71-83
http://arxiv.org/abs/0706.2996
- Tom Denton, Florent Hivert, Anne Schilling, Nicolas M. Thiéry
The representation theory of J-trivial monoids.
in preparation