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 Anne Schilling, Jennifer Morse, and
Mark Shimozono (2007-2010)
- "Combinatorics of crystals: geometric, physical, and computational
applications" led by Cristian Lenart Anne Schilling Mark Shimozono
Julianna Tymoczko (2010-2013, submitted).
Those 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 at the
University Marne-la-Vallee in November 2006 (host Jean-Christophe
Novelli) and at Universite Orsay, Paris-Sud in November 2008 (host
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 later plays a fundamental
role in numerous theories such are group representations (as character
of finite and Lie groups, spherical function of complex groups, real
and p-adic), algebraic topology (cobordism rings), algebraic geometry
(Schubert calculus) and mathematical physics (integrable system,
vertex operators).
Since a few years, several such Hopf algebras appeared in seemingly
unrelated domain. Natural in operads theory since each operad
verifying some simple conditions gives rise to a Hopf algebra, they
appear in combinatorics when one try to lift to a non-commutative
level certain computations on polynomials 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 projet is not only to ground a theory 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
5.4 / Description of activites, including levels, timetable, and milestones
The main activity will consist of short to long visits across the
Atlantic, in particular for PhD students and postdocs. There are two
typical scenarios there: in the first one, two or more researchers 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 France (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
France due to the current state of the job market in the US; this
includes Jason Bandlow (symmetric functions), Brant Jones (crystals
and Hecke algebras, available), Robert Miller (graphs), Steve Pon, 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.
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
Those venues will require mobile development and computing hardware
(laptops, ...) + TODO: Sage-Combinat server (taken from NSF project)
(TODO) Milestones:
- FPSAC 2010: Full migration of MuPAD-Combinat completed
Operads, Hopf algebras, Representation theory of finite dimensional
algebras, ...
- FPSAC 2011:
- FPSAC 2012: Sage-Combinat development cruise speed reached
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://sagetrac.org/sage_trac/).
The overall development progress and the induced publications will be
tracked on the Sage-Combinat Wiki
(http://combinat.sagemath.org/).
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 Instituted 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
Wang Qiang *
University of California at Davis, graduate student 2004-current
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-
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
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), 1992-1996
Adrien Boussicault
Université de Marne-la-Vallée, PhD, 2005-2009
Valentin Ferray
Université de Marne-la-Vallée, graduate student, 2007-current
École Normale Supérieure 2003-2007
Pierre Loic Meliot
Université de Marne-la-Vallée, graduate student, 2007-current
École Normale Supérieure 2004-current
7.2 / EQUIPMENT AVAILABLE FOR THE PROJECT
us:
N/a
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.
J. Combin. Theory Ser. A, November 2008. Accepted.
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, June 2008. Submitted.
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
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