 |
September
14 - 20,
2015
Workshop
on Symbolic Combinatorics and Computational Differential Algebra
| Co-Organizers |
Program
Committee |
Manuel
Kauers, RISC, Johannes Kepler University, Austria
Peter Paule, RISC, Johannes Kepler University, Austria
Greg Reid, University of Western Ontario, Canada
|
Evelyne
Hubert,
Inria, France
Manuel Kauers, RISC, Johannes Kepler University,
Austria
Ilias Kotsireas, Wilfrid Laurier University, Canada
Ziming Li, Academy of Mathematics and Systems Science,
China
Peter Paule, RISC, Johannes Kepler University,
Austria
Greg Reid, University of Western Ontario, Canada
Michael Singer, North Carolina State University,
USA
Nikolay Vasilyev, Steklov Institute of Mathematics
at St. Petersburg, Russia
|
|
|
Overview
This workshop is devoted to algorithmic developments in Combinatorics and
Differential Algebra with a particular focus on the interaction of these two
areas.
Symbolic Combinatorics: Symbolic algorithms and software
have recently been developed that allow researchers to discover and prove
combinatorial identities as well as understand analytic and algebraic properties
of generating functions. These functions seldom have closed form solutions
and even when they do, direct evaluation may be intractable. Recent work
in Symbolic Combinatorics has focused on representing such functions by
annihilating differential or difference operators and then using techniques
from differential and difference algebra, as well as analysis, to analyze
these equations and their solutions. Besides methods relating to creative
telescoping and verication of function identities, other areas of emphasis
will include effective methods in difference algebra, the Galois theories
of difference equations, and the interaction of differential and difference
algebra in combinatorics.
Computational Differential Algebra is an approach to nonlinear
or linear differential equations and differential structures, focusing not
only on finding explicit closed form solution, but also on simplifying such
equations to yield preconditioning for subsequent numerical solution, as
well clearer understanding of the qualitative behavior of solutions. Highlighted
aspects will include differential-elimination completion algorithms; geometric
differential algebra, moving frames and differential invariants; differential
Galois theory and integrability; complexity and open problems.
Schedule
| Monday,
September 14 |
|
8:15-8:45
|
On site registration and morning coffee |
|
8:45-9:00
|
Welcoming remarks |
|
9:00-9:50
|
George Labahn, University of Waterloo
Rational Invariants of Finite Abelian Groups
and their use in solving polynomial systems |
|
10:10-11:00
|
Markus Rosenkranz, University of
Kent
Partial Integral Operators and the Hopf Algebra
of Linear Substitutions |
|
11:00-11:30
|
Coffee break |
|
11:30-12:20
|
Austin Roche, Maplesoft
Targeted overdetermined functional decomposition
and applications to differential equations |
|
12:20-14:00
|
Lunch break |
|
14:00-14:50
|
Manuel Kauers, Johannes Kepler University
Creative Telescoping via Hermite Reduction
|
|
14:50-15:30
|
Coffee break |
|
15:30-16:20
|
Peter J. Olver, University of Minnesota
Algebras of Differential Invariants |
|
Personal time
(16:20-19:00)
|
|
19:00-21:00
|
Reception at Fields
featuring Bowser and Blue
|
| Tuesday,
September 15 |
|
9:00-9:50
|
Alin Bostan, INRIA
Quasi-optimal computation of the p-curvature
|
|
10:10-11:00
|
Carlos Arreche,
North Carolina State University
On the computation of the difference-differential
Galois group for a second-order linear difference equation |
|
11:00-11:30
|
Coffee Break
|
|
11:30-12:20
|
Joachim von zur Gathen,
University of Bonn
Combinatorics on polynomial equations: do they
describe nice varieties? |
|
12:20-14:00
|
Lunch |
|
14:00-14:50
|
Rika Yatchak, Johannes Kepler University
A primer on lattice path combinatorics |
|
15:10-16:00
|
Marni Mishna, Simon
Fraser University
The combinatorics behind lattice path asymptotics
|
| Wednesday,
September 16 |
|
9:00-9:50
|
Elizabeth Mansfield,
University of Kent
Lattice based multispace and applications
to moving frames |
|
10:10-11:00
|
Alexey Ovchinnikov,
CUNY Queens College
Algorithms for computing Galois groups of
parameterized differential equations |
|
11:00-11:30
|
Coffee Break |
|
11:30-12:20
|
Peter Paule, Research
Institute for Symbolic Computation (RISC), Johannes Kepler University
Linz
Computer Algebra Algorithms for Modular Functions |
|
|
| Thursday,
September 17 |
|
9:00-9:50
|
Evelyne Hubert,
INRIA Méditerranée
A moment matrix approach to symmetric cubatures |
|
10:10-11:00
|
Doron Zeilberger,
Rutgers University
To Think in a Symbolic-Computational Way... |
|
11:00-11:30
|
Coffee Break |
|
11:30-12:20
|
Ekaterina Shemyakova,
SUNY at New Paltz
Darboux transformations for differential
operators on the superline |
|
12:20-14:00
|
Lunch |
|
14:00-14:50
|
Johannes Middeke,
Johannes Kepler University
Uncoupling of Linear Difference/Differential Systems of Higher
Order |
|
15:10-16:00
|
Frédéric
Chyzak, INRIA Saclay Île-de-France
Explicit generating series for small-step walks
in the quarter plane |
|
Participant paid dinner
(details to be announced)
|
| Friday,
September 18 |
|
9:00-9:50
|
Cyril Banderier,
Institut Galilée - Université Paris-Nord
From algebraic to differentialy-algebraic
functions in combinatorics: impact of positive (integer) coefficients |
|
10:10-11:00
|
Moulay A. Barkatou,
Universite de Limoges
On Apparent Singularities of Systems of Linear
Differential Equations with Rational Function Coefficients |
|
11:00-11:30
|
Coffee Break |
|
11:30-12:20
|
Greg Reid, University
of Western Ontario
Symbolic-Numeric Differential Algebra and Applications |
|
12:20-14:00
|
Lunch |
|
14:00-14:50
|
Yang Zhang, University
of Manitoba
The generalized inverses of Ore matrices and applications
|
|
15:10-16:00
|
Stephen Melczer, University
of Waterloo & ENS Lyon
Effective Analytic Combinatorics in Several
Variables, With Applications to Lattice Path Enumeration |
| Saturday,
September 19 |
|
9:00-9:50
|
Christian Krattenthaler,
Universitaet Wien
Two problems at the interface of combinatorics
and symbolic computation |
|
10:10-11:00
|
Sumayya
Suzy Maddah, XLIM
Formal Reduction of Singularly-Perturbed Linear
Differential Systems |
|
11:00-11:30
|
Coffee Break |
|
11:30-12:20
|
Georg Regensburger,
Austrian Academy of Sciences
Computational and algebraic aspects of
integro-differential operators |
|
12:20-14:00
|
Lunch |
Registrants
as of August
18, 2015
|
Full Name
|
Institution
|
Arrival Date
|
Departure Date
|
| Alonso, Maria Emilia |
University complutense of Madrid |
01-Sep-15 |
03-Nov-15 |
| Amzallag, Eli |
CUNY Graduate Center |
13-Sep-15 |
20-Sep-15 |
| Arnold, Andrew |
University of Waterloo |
01-Sep-15 |
31-Dec-15 |
| Arreche, Carlos |
North Carolina State University |
01-Sep-15 |
04-Nov-15 |
| Banderier, Cyril |
Univ Paris 13 |
13-Sep-15 |
20-Sep-15 |
| Barkatou, Moulay |
XLIM, CNRS, University of Limoges |
12-Sep-15 |
19-Sep-15 |
| Behrouzinia, Paria |
Alzahra University |
06-Sep-15 |
21-Sep-15 |
| Bostan, Alin |
INRIA |
13-Sep-15 |
19-Sep-15 |
| Chen, Shaoshi |
Chinese Academy of Sciences |
12-Sep-15 |
28-Dec-15 |
| Dema, Ilir |
University of Toronto |
14-Sep-15 |
20-Sep-15 |
| Diatta, Seny |
University Assane Seck of Ziguinchor |
10-Sep-15 |
18-Dec-15 |
| Goktas, Unal |
Turgut Ozal University |
13-Sep-15 |
20-Sep-15 |
| Guo, Feng |
Dalian University of Technology |
09-Sep-15 |
31-Dec-15 |
| Gustavson, Richard |
CUNY Graduate Center |
13-Sep-15 |
20-Sep-15 |
| Hubert, Evelyne |
Inria Méditerranée |
01-Sep-15 |
17-Dec-15 |
| Ivan, Daniel |
University of Waterloo |
14-Sep-15 |
20-Sep-15 |
| Kauers, Manuel |
Johannes Kepler University |
13-Sep-15 |
19-Sep-15 |
| Krattenthaler, Christian |
Universitaet Wien |
13-Sep-15 |
20-Sep-15 |
| Labahn, George |
University of Waterloo |
01-Sep-15 |
18-Dec-15 |
| Li, Nan |
Tianjin University |
|
|
| Maddah, Sumayya Suzy |
XLIM |
01-Sep-15 |
31-Dec-15 |
| Mansfield, Elizabeth |
University of Kent |
13-Sep-15 |
20-Sep-15 |
| Melczer, Stephen |
University of Waterloo & ENS Lyon |
13-Sep-15 |
20-Sep-15 |
| Mishna, Marni |
Simon Fraser |
|
|
| Neiger, Vincent |
LIP - ENS de Lyon |
13-Sep-15 |
20-Sep-15 |
| Niemerg, Matthew |
|
13-Aug-15 |
21-Aug-15 |
| Olver, Peter |
University of Minnesota |
13-Sep-15 |
18-Sep-15 |
| Ovchinnikov, Alexey |
CUNY Queens College |
|
|
| Paule, Peter |
Johannes Kepler University |
10-Sep-15 |
20-Sep-15 |
| Raab, Clemens |
Austrian Academy of Sciences |
05-Sep-15 |
20-Sep-15 |
| Regensburger, Georg |
Austrian Academy of Sciences |
16-Sep-15 |
19-Sep-15 |
| Reid, Greg |
University of Western Ontario |
13-Sep-15 |
21-Sep-15 |
| Riener, Cordian |
Aalto University |
05-Sep-15 |
20-Dec-15 |
| Roche, Austin |
Maplesoft |
13-Sep-15 |
20-Sep-15 |
| Rosenkranz, Markus |
University of Kent |
13-Sep-15 |
20-Sep-15 |
| Shemyakova, Ekaterina |
State University of New York at New Paltz |
13-Sep-15 |
21-Sep-15 |
| Singer, Michael |
NC State University |
06-Sep-15 |
10-Oct-15 |
| Thompson, Peter |
CUNY The Graduate Center |
13-Sep-15 |
19-Sep-15 |
| van Hoeij, Mark |
FSU |
13-Sep-15 |
19-Sep-15 |
| von zur Gathen, Joachim |
University of Bonn |
23-Aug-15 |
21-Sep-15 |
| Yatchak, Rika |
Johannes Kepler University |
13-Sep-15 |
20-Sep-15 |
| Zeilberger, Doron |
Rutgers University |
15-Sep-15 |
19-Sep-15 |
| Zhang, Yang |
University of Manitoba |
13-Sep-15 |
20-Sep-15 |
Abstracts
Carlos Arreche, North Carolina State University
On the computation of the difference-differential Galois group for a second-order
linear difference equation
Given a linear difference equation, there is a difference-differential
Galois group that encodes the differential-algebraic dependencies among
the solutions of the equation. After giving a brief introduction to this
theory, I will describe algorithms to compute the Galois group associated
to a second-order linear difference equation over C(x), the field of rational
functions over a computable field C of characteristic zero, with respect
to the C-linear shift automorphism that sends x to x+1. I will also discuss
some concrete examples to illustrate these algorithms, and show explicitly
in the examples how to derive the differential-algebraic dependencies among
the solutions from the knowledge of the defining equations for the Galois
group.
Cyril Banderier, Institut Galilée -
Université Paris-Nord
From algebraic to differentialy-algebraic functions in combinatorics: impact
of positive (integer) coefficients
Asymptotics of recurrences is the key to get the typical properties
of combinatorial structures, and thus the complexity of many algorithms relying
on these structures. The associated generating function often follows a linear
differential equation: we are here in the so-called "D-finite" world.
For the matters of asymptotics, this case of linear recurrences (with polynomial
coefficients) is well covered by the "Analytic Combinatorics" book
of Flajolet and Sedgewick (though the computations of constants is still a
challenge, related to the theory of Kontsevich-Zagier periods and evaluation
of G-functions and E-functions). At the border of this D-finite world, lies
"algebraic-differential functions". The terminology is not yet fixed
and similar terms are used, up to a permutation, by several authors: let dz^m
be the m-th derivative of F(z), the function is said "algebraic-differential"
if there a exists a polynomial P such that P(z,F,F',..., dz^m F)=0. For all
these worlds, having some positive (integer) coefficients leads to some strong
constraints on the asymptotics (these is now well understood for algebraic
function), and we try to see what happens in a more general setting.
We will give examples of such functions (motivated by some combinatorial
problems), and show how a symbolic combinatorics approach can help for automatic
asymptotics of their coefficients, and some open related open questions/challenges
for computer algebra (joint works with Michael Drmota and Hsien-Kuei Hwang)
Moulay A. Barkatou, Universite de Limoges
On Apparent Singularities of Systems of Linear Differential Equations with
Rational Function Coefficients
Let (S) $\frac{dY}{dz}= A(z)Y$ be a system of first order linear differential
equations with rational function coefficients. The (finite) singularities
of (S) are the poles of the entries de the matrix $A(z)$. A singular point
$z_0$ of (S) is called an apparent singularity for $(S)$ if there is a basis
of solutions of (S) which are holomorphic in a neighborhood of $z_0$. In
this talk we shall present a new algorithm which, given a system of the
form (S), detects apparent singularities and constructs an equivalent system
(S') with rational coefficients the singularities of which coincide with
the non apparent singularities of (S). Our method can, in particular, be
applied to the companion system of any linear differential equation with
arbitrary order $n$. We thus have an alternative method to the standard
methods for removing apparent singularities of linear differential operators.
We shall compare our method to the one designed for operators and we shall
show some applications and examples of computation. This talk is based on
a joint work, with S. Maddah, recently presented at ISSAC 2015.
Alin Bostan, INRIA
Quasi-optimal computation of the p-curvature
The p-curvature of a system of linear differential equations in characteristic
p is a matrix that measures to what extent the system is close to having
a fundamental matrix of rational function solutions. This notion, originally
introduced in the arithmetic theory of differential equations, has been
recently used as an effective tool in computer algebra and in combinatorial
applications. We describe a recent algorithm for computing the p-curvature,
whose complexity is almost optimal with respect to the size of the output.
The new algorithm performs remarkably well in practice. Its design relies
on the existence of a well-suited ring, of so-called Hurwitz series, for
which an analogue of the Cauchy–Lipschitz Theorem holds, and on a FFT-like
method in which the "evaluation points" are Hurwitz series. Joint
work with Xavier Caruso and Éric Schost.
Frédéric Chyzak, INRIA Saclay Île-de-France
Explicit generating series for small-step walks in the quarter plane
Lattice walks occur frequently in discrete mathematics, statistical physics,
probability theory, and operational research. The algebraic properties of
their enumeration generating series vary greatly according to the family
of admissible steps chosen to define them: their generating series are sometimes
rational, algebraic, or D-finite, or sometimes they possess no apparent
equation. This has recently motivated a large classification effort. Interestingly,
the equations involved often have degrees, orders, and sizes, making calculations
an interesting challenge for computer algebra.
In this talk, we study nearest-neighbours walks on the square lattice, that
is, models of walks on the square lattice, defined by a fixed step set that
is a subset of the 8 non-zero vectors with coordinates 0 or ±1.
We concern ourselves with the counting of walks constrained to remain in
the quarter plane, counted by length. In the past, Bousquet-Mélou
and Mishna showed that only 19 essentially different models of walks possess
a non-algebraic D-finite generating series; the linear differential equations
have then been guessed by Bostan and Kauers. In this work in progress, we
give the first proof that these equations are satisfied by the corresponding
generating series. This allows to derive nice formulas for the generating
series, expressed in terms of Gauss' hypergeometric series, to decide their
algebraicity or transcendence. This also gives hope to extract asymptotic
formulas for the number of walks counted by lengths.
(Based on work in progress with Alin Bostan, Mark van Hoeij, Manuel Kauers,
and Lucien Pech.)
Shaoshi
Chen, Chinese Academy of Sciences
Proof of the Wilf-Zeilberger Conjecture
In 1992, Wilf and Zeilberger conjectured that a hypergeometric term in
several discrete and continuous variables
is holonomic if and only if it is proper. Strictly speaking the conjecture
does not hold, but it is true when
reformulated properly: Payne proved a piecewise interpretation in 1997,
and independently, Abramov and
Petkovsek in 2002 proved a conjugate interpretation. Both results address
the pure discrete case of the conjecture.
In this paper we extend their work to hypergeometric terms in several discrete
and continuous variables and prove the conjugate interpretation of the Wilf-Zeilberger
conjecture in this mixed setting. This is a joint work with Christoph Koutschan.
Evelyne Hubert, INRIA Méditerranée
A moment matrix approach to symmetric cubatures
Coauthor: Mathieu Collowald
A quadrature is an approximation of the definite integral of a function
by a weighted sum of function values at specified points, or nodes, within
the domain of integration. Gaussian quadratures are constructed to yield
exact results for any polynomials of degree 2r-1 or less by a suitable choice
of r nodes and weights. Cubature is a generalization of quadrature in higher
dimension.
Constructing a cubature amounts to find a linear form p -> a1 p(x1) +
.... + ar p(xr) from the knowledge of its restriction to polynomials of
degree d or less. The unknowns are the weights aj and the nodes xj. An approach
based on moment matrices was proposed in [2,4]. We give a basis-free version
in terms of the Hankel operator H associated to a linear form. The existence
of a cubature of degree d with r nodes boils down to conditions of ranks
and positive semidefiniteness on H. We then recognize the nodes as the solutions
of a generalized eigenvalue problem. Standard domains of integration are
symmetric under the action of a finite group. It is natural to look for
cubatures that respect this symmetry [1,3]. Introducing adapted bases obtained
from representation theory, the symmetry constraint allows to block diagonalize
the Hankel operator H. The size of the blocks is explicitly related to the
orbit types of the nodes. From the computational point of view, we then
deal with smaller-sized matrices both for securing the existence of the
cubature and computing the nodes.
[1] R. Cools. Constructing cubature formulae: the science behind the art.
Acta numerica, 6:1--54, 1997.
[2] L. Fialkow and S. Petrovic. A moment matrix approach to multivariable
cubature. Integral Equations Operator Theory, 52(1):85--124, 2005.
[3] K. Gatermann. The construction of symmetric cubature formulas for the
square and the triangle. Computing, 40(3):229--240, 1988.
[4] J.~B. Lasserre. The existence of {G}aussian cubature formulas. J. Approx.
Theory, 164(5):572--585, 2012.
Manuel
Kauers, Johannes Kepler University
Creative Telescoping via Hermite Reduction
Creative telescoping is a key tool in symbolic summation and integration.
It is used for constructing for a given definite sum or integral an associated
linear recurrence or differential equation, which can then be used by other
algorithms for finding out all sorts of interesting facts about the quantity
in question. Four generations of creative telescoping algorithms can be
distinguished: the first was based on elimination in ideals of operator
algebras. The second is the classical Zeilberger algorithm and its variants.
The third goes back to an idea of Apagodu and Zeilberger. These algorithms
are particularly easy to implement and to analyze, but may not find optimal
solutions. The fourth and final (so far) generation of creative telescoping
algorithms is based on Hermite reduction. This idea was first worked out
for definite integrals of multivariate rational functions by Bostan, Chen
and Chyzak. It has since been extended to more general classes of sums and
integrals by these and other authors. In the talk, we will explain the idea
of this apprach and a striking advantage over earlier algorithms. We will
also present a Hermite-reduction based algorithm applicable to definite
hypergeometric sums, published this year in a joint ISSAC paper with Chen,
Huang, and Li.
Christian
Krattenthaler, Universitaet Wien
Two problems at the interface of combinatorics and symbolic computation
I shall present two (unrelated) problems which arise in work on congruences
for combinatorial sequences that I have been pursuing with Thomas M\"uller.
The first one concerns the formal power series $\sum_n z^{p^n}$, where $p$
is a given prime number. The question is to determine the minimal degree
of a polynomial relation satisfied by this series modulo some fixed power
of $p$. The second problem arises in combinatorial group theory and concerns
the (Hadamard) product of P-recursive sequences. The question is what one
can say about the leading coefficient of the recurrence satisfied by the
product sequence. In both cases, I shall explain the context, and I will
formulate precise conjectures (that may sometimes rather be speculations).
George
Labahn, University of Waterloo
Rational Invariants of Finite Abelian Groups and their use in solving polynomial
systems
We give a constructive procedure for determining a generating set of rational
invariants of the linear action of a finite abelian group in the non-modular
case and investigate its use in the symmetry reductions of polynomial systems.
Finite abelian subgroups of GL(n,K) can be diagonalized which allows the
group action to be accurately described by an integer matrix of exponents.
We can make use of integer linear algebra to construct both a minimal generating
set of invariants and the substitution to rewrite any invariant in terms
of this generating set. The set of invariants provide a symmetry reduction
scheme for polynomial systems whose solution set is invariant by a finite
abelian group action.
This is joint work with Evelyne Hubert ( INRIA Méditerranée
).
Sumayya
Suzy Maddah, XLIM
Formal Reduction of Singularly-Perturbed Linear Differential Systems
In this talk, we are interested in the local analysis of singularly-perturbed
linear differential systems. Such systems have a vast literature and arise
profoundly in applications. However, their symbolic resolution is still open
to investigation. The complications arise mainly from the phenomenon of turning
points. We extend notions introduced for the treatment of their unperturbed
counterparts and generalize corresponding algorithms to construct formal solutions.
The underlying components of the formal reduction proposed are stand-alone
algorithms as well and serve di erent purposes (e.g. rank reduction, classi
cation of singularities, computation of the restraining index). We present
our proposed algorithm and associated packages written in Maple. This is a
joint work with Molay A. Barkatou.
Keywords: Computer algebra, formal reduction, rank reduction, singu-
larities, turning points, linear di erential systems, singularly-perturbed
linear
di erential systems, apparent singularities.
Elizabeth
Mansfield, University of Kent
Lattice based multispace and applications to moving frames
Joint work with Gloria Mari Beffa.
We propose a generalisation of the jet bundle based on equivalence classes
of functions in a neighbourhood of a point, in which a function is equivalent
to its Lagrange interpolation on diffeomorphic images of corner lattices.
Under coalescence of the lattice, this interpolation becomes the Taylor polynomial,
and thus the jet bundle is an embedded sub manifold. The construction relies
on the multivariate approximation results of de Boor and Ron. We use our construction
to provide a space in which smooth and discrete moving frames can be treated
by a uniform construction, and in which certain convergence results can be
assumed. In particular, we will have limits of discrete to smooth invariants
as well as showing the recurrence relations of the discrete invariants will
limit to the differential syzygies of the smooth invariants. Other possible
uses of our construction will be discussed. However, the difference operators
associated to the Lagrange interpolation have some interesting properties
which could make them hard to work with.
Stephen
Melczer, University of Waterloo & ENS Lyon
Effective Analytic Combinatorics in Several Variables, With Applications
to Lattice Path Enumeration
Recent work in the study of analytic combinatorics in several variables
has shown how to derive asymptotics for the coefficients of certain families
of D-finite functions by representing them as diagonals of multivariate rational
functions. Although a theoretical framework has been laid over the last two
decades (and before), there are still obstacles which has made the ultimate
dream of an effective implementation of these techniques elusive. We begin
by surveying the field of analytic combinatorics and outline the difficulties
mentioned above. This will be followed by a more hopeful look at the problem
when restricted to the so-called “combinatorial” case. Previous
work by Melczer and Mishna on the enumeration of lattice paths whose defining
sets of steps are highly symmetric can be viewed in this context, and it will
be shown how the results they obtained relate to more general structure theorems.
Finally, new work on lattice paths whose sets of steps are missing some symmetries
— whose analysis relies on rational functions that are not combinatorial
— will be outlined.
This is joint work with Mark Wilson, Marni Mishna, George Labahn, and Bruno
Salvy.
Johannes
Middeke, Johannes Kepler University
Uncoupling of Linear Difference/Differential Systems of Higher Order
We consider linear systems of difference or differential equations of higher
order. Modelling them as matrices of Ore polynomials, we will explore the
use of matrix normal forms for reducing the system to independent scalar equations.
Marni
Mishna, Simon Fraser University
The combinatorics behind lattice path asymptotics
Lattice path walk models are straightforward combinatorial classes
that are well suited to a systematic analysis. Indeed many of the enumerative
results from the past 20 years or so have had a computer algebra component
to the argument. In this talk I will first survey some of these techniques
and results (with a focus on asymptotic enumeration), and then discuss the
underlying combinatorial structure which guides these results. The combinatorial
interpretations are key to various applications such as uniform random generation
of lattice walks in the quarter plane, notably for models with strong drift.
Joint work with Samuel Johnson, Jeremie Lumbroso, Yann Ponty and Karen Yeats.
Peter
J. Olver, University of Minnesota
Algebras of Differential Invariants
A classical theorem of Lie and Tresse states that the algebra of differential
invariants of a Lie group or (suitable) Lie pseudo-group action is finitely
generated. I will present a fully constructive algorithm, based on the equivariant
method of moving frames, that reveals the full structure of such non-commutative
differential algebras, and, in particular, pinpoints generating sets of
differential invariants as well as their differential syzygies. A variety
of applications and outstanding issues will be discussed, including equivalence
and symmetry detection in image processing, and some surprising results
in classical surface geometries.
Alexey
Ovchinnikov, CUNY Queens College
Algorithms for computing Galois groups of parameterized differential equations
Galois groups of parameterized linear differential equations are linear
differential algebraic groups, that is, groups of matrices whose entries
satisfy polynomial differential equations. The theory was initiated by Cassidy,
Landesman, and Singer. Arreche and Dreyfus have developed algorithms for
computing such groups of second order differential equations, and Arreche
has applied this to study properties of special functions.
We will discuss how to calculate the unipotent radicals of parameterized
Galois groups if the differential operator is a composition of two completely
reducible differential operators. We will also discuss how to use this to
calculate the Galois group of a third order linear differential equation
with parameters and to illustrate this by a concrete example of the Lommel
differential equation.
This is joint work with Charlotte Hardouin.
Peter Paule, Research Institute for Symbolic Computation
(RISC), Johannes Kepler University Linz
Computer Algebra Algorithms for Modular Functions
The talk reports on a joint project with Silviu Radu. Its goal is to develop
computer algebra algorithms to assist mathematical research in connection
with modular functions. A major application is a new unified approach to
the celebrated Ramanujan congruences for partition numbers modulo powers
of 5, 7, and 11. The algorithms presented in the talk are also relevant
outside this application domain, for instance, to decide subalgebra membership
or to construct algebraic relations for functions on Riemann surfaces.
Greg Reid, University of Western Ontario
Symbolic-Numeric Differential Algebra and Applications
Geometric involutivity is a property which first arose in the geometric
analysis of systems of analytic nonlinear PDE for compatibility and formal
existence of solutions. Cartan conjectured a finite prolongation (differentiation)
procedure to makes systems geometrically involutive and this finiteness
was eventually proved under certain regularity assumptions by Kuranishi.
The geometric invariance of geometric involution, yields favourable properties
for symbolic-numeric implementations, as shown in joint work with Wittkopf.
In the special case of PDE with constant coefficients and their naturally
associated polynomial systems, geometric involutivity yields Geometric Involutive
Bases. Such bases are a geometric cousin of Pommaret Involutive Bases, which
are a type of Groebner Basis. Computation and exploitation of Geometric
Involutive Bases for systems of polynomial equations were further developed
in joint work with Zhi, Scott, Wu and others.
I will discuss some recent theoretical developments and applications of
symbolic-numeric algorithms to determine geoemtric involutivity. Specifically
some recent progress in determination of approximate symmetry Lie algebras
and related structures of differential equations is discussed. This is joint
work with Ian Lisle, Tracy Huang and Shenghao Yang. I will also discuss
some applications of involutivity to semi-definite programming methods for
real solutions of polynomial systems which has played a significant role
in in our recent work, and also those of Lasserre, Zhi and their respective
collaborators.
Georg Regensburger, Austrian Academy of
Sciences
Computational and algebraic aspects of integro-differential operators
Differential operators with polynomial coefficients provide a rich algebraic
structure with a wealth of results and algorithmic methods. Adding integral
operators and evaluations (that is, multiplicative functionals), many new
phenomena appear, including zero devisors and non-finitely generated ideals.
The resulting algebra of integro-differential operators allows us in particular
to study initial value and boundary problems for linear ODEs from an algebraic
point of view.
In this talk, we will first describe a construction and normal forms of
integro-differential operators with polynomial coefficients and discuss
some basic algebraic properties. Then we present an algorithmic approach
for computing polynomial solutions and the index for a class of linear operators
on the polynomial ring that includes integro-differential operators. A generating
set for right annihilators can be constructed in terms of polynomial solutions.
For initial value problems, an involution of the algebra of integro-differential
operators also allows us to compute left annihi-lators, which can be interpreted
as compatibility conditions of integro-differential equations. We illustrate
our approach with an implementation in the computer algebra system Maple.
This is joint work with Alban Quadrat.
Finally, we will outline a recent generalization of integro-differential
operators that allows integral operators acting on functions with singularities
and arbitrary linear functionals. This is joint work with Clemens G. Raab.
Austin Roche, Maplesoft
Targeted overdetermined functional decomposition and applications to differential
equations
The equivalence method for ordinary differential equations (ODEs) involves
finding a transformation mapping a given equation into a target equation
with known solution. Such equivalence transformations are found by solving
systems relating the differential invariants of the input equation to those
of the target equation. Standard solution techniques, applicable when the
invariants are rational functions, use algebraic elimination and can solve
complete families of equations characterized by many parameters. However,
the complexity of such methods increases exponentially with the number of
parameters, and can become impractical in interesting cases. A technique
is presented for overdetermined rational function decomposition, specifically
tailored to systems of invariants. Its complexity is effectively independent
of the number of parameters defining the system. The use of this technique
in the ODE equivalence method is described, including the use of minimal
invariants which ensures the solution of all rational coefficient equations
in the target class. Recognizing that related invariants tend to be composed
as products of powers of a set of common polynomials, and furthermore that
the pattern of these polynomials is invariant under composition by rational
functions, we can compute these component polynomials invariantly. Using
the target system as a model, a sequence of invariant computations is built
that successively simplifies the system, leading eventually to the determination
of the parameters and transformation function. The resulting algorithm mimics
a formula in its specificity but lacks the associated expression growth.
Application to solving the first order Abel ODE will be shown.
Markus Rosenkranz, University of Kent
Partial Integral Operators and the Hopf Algebra of Linear Substitutions
In contrast to their differential analogue, partial integral operators exhibit
a rather subtle interaction with the action of GL(n) and its singular shell.
We propose a new algebraic approach that reduces the matrix action on coefficient
functions to the following three ingredients: (i) coalgebra structure on "univariate"
coefficient functions, (ii) permutations, (iii) scaling of independent variables.
Having these ingredients and a suitable univariate integral operator, the
tensor algebra is endowed with a linear action and a hierarchy of integral
operators compatible with the substitutions.
The resulting multivariate hierarchy can then be used as coefficient functions
in an extenive operator ring that contains additionally the partial integral
operators as well as all linear substitutions. We propose a rewrite system
for doing computations in this operator ring. The rewrite system is terminating,
and we present a natural system of normal forms for it. It is conjectured
that the system is moreover confluent, and hence a noncommutative Groebner
basis for the ideal it generates. Applications to a simple class of linear
partial differential equations are presented.
Ekaterina Shemyakova, SUNY at New Paltz
Darboux transformations for differential operators on the superline
I shall present our very general result on a full description of Darboux
transformations of any order for arbitrary (nondegenerate) differential
operators on the superline.
We show that every Darboux transformation of such operators factorizes into
elementary Darboux transformations of order one. Similar statement holds
for operators on the ordinary line.
This is a joint work with S. Hill and Th. Voronov.
Mark van Hoeij, Florida State University
Hypergeometric solutions of Linear Differential Equations
If a convergent power series with integer coefficients satisfies a linear
differential equation with polynomial coefficients, then it is conjectured
that it can be expressed in terms of hypergeometric functions. This talk
will give an overview of the algorithms to find such expressions for differential
equations of order 2, and discuss the prospects for extending to higher
order.
Rika Yatchak, Johannes Kepler University
A primer on lattice path combinatorics
Lattice paths are fundamental combinatorial objects that appear in many
different areas of mathematics. We provide an overview of classical techniques
for enumerating lattice paths and finding expressions for their generating
functions.
Joachim von zur Gathen, University of Bonn
Combinatorics on polynomial equations: do they describe nice varieties?
We consider natural combinatorial questions about systems of multivariate
polynomials over a finite field and the variety V that they define over
an algebraic closure. Fixing the number of variables, the number of polynomials
and the sequence of degrees, there are finitely many such systems. We ask:
for how many systems is V nice? Is that usually the case?
"Nice" can refer to various properties:
o The system is regular, so that no polynomial is a zero divisor modulo
the previous ones.
o V is a settheoretic complete intersection.
o V is an idealtheoretic complete intersection.
o V is absolutely irreducible.
o V is nonsingular.
o V is nondegenerate (not contained in a hyperplane).
All but the last property usually hold. More precisely, for each of them
we present a nonzero obstruction polynomial in the coefficients of the system
so that the property holds when the obstruction does not vanish. The obstructions
come with explicit bounds on their degrees. They yield estimates on the
probability for the properties to hold. These probabilities
tend rapidly to 1 with growing field size. Somewhat surprisingly, the last
property behaves differently. Fixing the degree of V, most systems (with
at least two polynomials) describe varieties that are hypersurfaces in some
proper linear subspace.
Joint work with Guillermo Matera.
Doron Zeilberger, Rutgers University
To Think in a Symbolic-Computational Way...
Currently, symbolic computation is still a small, fringe, discipline, at
the borderline of math and computer science, with relatively little prestige.
But this will change very soon, since once people (including those working
in this area) would learn hour to FULLY think in a symbolic-computational
way, mathematics would grow exponentially, both in quantity, and especially
in quality.
Yang Zhang, University of Manitoba
The generalized inverses of Ore matrices and applications
Ore matrices are matrices over Ore algebras (including differential operators
and difference operators), which have a long research history, at least
dated back to Jacobson's seminal work in 1940s. In past two decades, Ore
matrices have attracted more and more people in computer algebra area, and
many important properties of Ore matrices have been discussed by using symbolic
computation methods.
It is well-known that the generalized inverse of matrices over commutative
rings (or fields), especially the Moore-Penrose inverse, play important
roles in matrix theory and have applications in many areas: solving matrix
equations, statistics, engineering, etc. This motivates us to consider the
generalized inverse of Ore matrices.
First we define the generalized inverse and the Moore-Penrose inverse for
Ore matrices, and prove some basic properties
including uniqueness. Unlike the commutative case, the generalized inverse
for a given Ore matrix may not exist. We use blocked matrices and greatest
common right (left) divisor computations to give some sufficient and necessary
conditions for Ore matrices to have the generalized inverses and the Moore-Penrose
inverses. Moreover when these inverses exist, we construct algorithms to
compute them.
Back to top
|
|
