Symmetry and Computations

A moment matrix approach to computing symmetric cubatures; with
M. Collowald.
[hal01188290],
[video]
Abstract:
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 polynomial 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 Λ : R[x] → R, p → r j=1 a j
p(ξ j) from the knowledge of its restriction to R[x] ≤d. The
unknowns are the number of nodes r, the weights a j and the nodes ξ
j. An approach based on moment matrices was proposed in [25]. We
give a basisfree version in terms of the Hankel operator H
associated to Λ. 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 [13, 27, 28].
Introducing adapted bases obtained from representation theory,
the symmetry constraint allows to block diagonalize the Hankel
operator H. We then deal with smallersized matrices both for
securing the existence of the cubature and computing the nodes. The
sizes of the blocks are furthermore explicitly related to the orbit
types of the nodes with the new concept of the matrix of
multiplicities of a finite group. It provides preliminary criteria
of existence of a cubature with a given organisation of the nodes in
orbit types. The Maple implementation of the presented algorithms
allows to determine, with moderate computational efforts, all the
symmetric cubatures of a given degree. We present new relevant
cubatures.
Algebraic Invariants

Rational invariants of ternary forms under the orthogonal group; with
P. Goerlach and T. Papadopoulo.
[hal01570853]
Abstract:
In this article we determine a generating set of rational invariants of minimal cardinality for the action of the orthogonal group O3 on the space R[x, y, z]_2d of ternary forms of even degree 2d. The construction relies on two key ingredients: On one hand, the Slice Lemma allows us to reduce the problem to dermining the invariants for the action on a subspace of the finite subgroup B3 of signed permutations. On the other hand, our construction relies in a fundamental way on specific bases of harmonic polynomials. These bases provide maps with prescribed B3equivariance properties. Our explicit construction of these bases should be relevant well beyond the scope of this paper. The expression of the B3invariants can then be given in a compact form as the composition of two equivariant maps. Instead of providing (cumbersome) explicit expressions for the O3invariants, we provide efficient algorithms for their evaluation and rewriting. We also use the constructed B3invariants to determine the O3orbit locus and provide an algorithm for the inverse problem of finding an element in R[x, y, z]_2d with prescribed values for its invariants. These are the computational issues relevant in brain imaging.

Symmetrization of Polynomial Systems.
[hal01254954]
Abstract:
Assuming the variety of a polynomial set is invariant under a group
action, we construct a set of invariants that define the same
variety. Our construction can be seen as a generalization of the
previously known construction for finite groups once we introduce
the symmetrizations of a polynomial w.r.t. a section to the orbits
of the group action. The symmetrisations are polynomials in a
generating set of rational invariants as constructed by Hubert and
Kogan (2007).
The results have thus to be understood outside of a proper closed
invariant variety, independent of the polynomial set considered.

Computation of the Invariants of Finite Abelian Groups; with
G. Labahn. Mathematics of Computation (AMS) 85 p 30293050 (2016).
[hal00921905]
Abstract:
We investigate the computation and applications of rational
invariants of the linear action of a finite abelian group in the
nonmodular case. By diagonalization, such a group action
can be described by integer matrices of orders and exponents. We make
use of integer linear algebra to compute a minimal generating set
of invariants along with the substitution needed to rewrite
any invariant in terms of this generating set. In addition, we show
how to construct a minimal generating set that consists only of
polynomial invariants.
As an application, we provide a symmetry reduction scheme for
polynomial systems whose solution set is invariant by a finite
abelian
group action. Finally, we also provide an algorithm to find such symmetries given a polynomial system.

Rational Invariants of a Group Action. Les cours du CIRM 3:1, Journees
Nationales de Calcul Formel, P. Boito, G. Cheze, C. Pernet, M. Safey
El Din Editors (2013)
[CEDRAM],
[Hal00839283]
Abstract:
This article is based on an introductory lecture delivered at the
Journées Nationales de Calcul Formel that took place at the Centre
International de Recherche en Mathématiques (2013) in Marseille. We
introduce basic notions on algebraic group actions and their
invariants. Based on geometric consideration, we present algebraic
constructions for a generating set of rational invariants.

Scaling Invariants and Symmetry Reduction of Dynamical Systems; with
G. Labahn. Foundations Computational Mathematics. 13:4 pages
479516 (2013)
[doi:10.1007/s1020801391659]
[HAL]
Abstract:
A scaling is accurately described by a matrix
of integers. Tools from linear algebra over the integers are
exploited to compute their invariants and offer an algorithmic
scheme for the symmetry reduction of dynamical systems. A special
case of the symmetry reduction algorithm applies to reduce the
number of parameters in physical, chemical or biological models.
Keywords:
Group actions; Rational invariants; Matrix normal form;
Model reduction; Dimensional analysis.

Rational invariants of scalings from Hermite normal forms;
with G. Labahn. ISSAC 2012, pages 219226, ACM Press (2012)
[doi:10.1145/2442829.2442862]
[HAL]
Abstract:
Scalings form a class of group actions on affine spaces that have both
theoretical and practical importance. A scaling is accurately
described by an integer matrix. Tools from linear algebra are
exploited to compute a minimal generating set of rational
invariants, trivial rewriting and rational sections for such a
group action. The primary tools used are Hermite normal forms and
their unimodular multipliers. With the same line of ideas, a
complete solution to the scaling symmetry reduction of a polynomial
system is also presented.
Keywords:
Matrix normal form; Group actions; Rational invariants; Symmetry reduction.

Smooth and Algebraic Invariants of a Group Action. Local and Global Constructions;
with I. Kogan.
Foundations Computational Mathematics.
7:4 pages 345383 (2007)
[doi:10.1007/s1020800602190]
[pdf], [video]
Abstract:
Motivated by a wealth of applications both the theory of differential
invariants and the theory of algebraic invariants
have versed in computational mathematics.
Differential invariants are intimately linked
with studying differential systems,
while algebraic theories give proper grounds to symbolic algorithms.
The ambition of this paper is to provide algebraic foundations to the
moving frame method for the construction of local invariants
and present a parallel algebraic construction
that produces algebraic invariants together with the relations they satisfy.
We then show that the algebraic setting offers a computational solution to
the differential geometric construction.
Keywords:
rational and algebraic invariants; smooth and differential
invariants; algebraic and Lie group actions;
crosssection; moving frame method; Groebner basis.

Rational Invariants of a Group Action. Construction and Rewriting;
with I. Kogan. Journal of Symbolic Computation, 42:12 pages 203217 (2007).
[doi:10.1016/j.jsc.2006.03.005]
[pdf], [video]
Attachment: Maple code applied to the examples treated in the paper.
Abstract:
Geometric constructions applied to a rational action of an algebraic
group lead to a new algorithm for computing rational invariants.
A finite generating set of invariants appears as the coefficients of a reduced Groebner basis.
The algorithm comes in two variants. In the first construction the ideal of the graph of
the action is considered. In the second one the ideal of a
crosssection is added to the ideal of the graph. Zerodimensionality
of the resulting ideal brings a computational advantage.
In both cases, reduction with respect to the
computed Groebner basis allows to express any rational invariant
in terms of the generators.
Keywords:
Algebraic Invariants, Moving Frame, Groebner Bases, Computational Algebra.

Rational and Replacement Invariants of a Group Action;
with I. Kogan.
ACM SIGSAM Bulletin, Volume 39,
Issue 3 (2005).
[doi:10.1145/1113439.1113447]
Comment:
ISSAC 2005 award winning poster.
Geometrical Modeling

Numerical Reconstruction of Convex Polytopes from Directional Moments;
with M. Collowald, A. Cuyt, W.S.
Lee and O. Salazar Celis. Advances in Computational
Mathematics, 41:6 pages 10791099 (2015).
[doi:10.1007/s1044401494010]
[HAL]
Abstract:
We reconstruct an ndimensional convex polytope from the knowledge
of its directional moments up to a certain order. The directional
moments are related to the projection of the polytope's vertices on
a particular direction. To extract the vertex coordinates from the
moment information we combine established numerical algorithms such
as generalized eigenvalue computation and linear interval
interpolation. Numerical illustrations are given for the
reconstruction of polygons and polyhedra.

Identifying Perceptually Salient Features on 2D Shapes; with
L. J. Larsson, G. Morin,
A. Begault, R. Chaine,
J. Abiva, M. Hurdal, M. Li,
B. Paniagua, G. Tran,
and M.P. Cani.
In Research in Shape Modeling, Los Angeles, July
2013. Springer. Association for Women in Mathematics Series 1 (2015).
Abstract:
Maintaining the local style and scale of 2D shape features during deformation, such as when elongating, compressing, or bending a shape, is essential for interactive shape editing. To achieve this, a necessary first step is to develop a robust classification method able to detect salient shape features, if possible in a hierarchical manner. Our aim is to overcome the limitations of existing techniques, which are not always able to detect what a user immediately identifies as a shape feature. Therefore, we first conduct a user study enabling us to learn how shape features are perceived. We then propose and compare several algorithms, all based on the medial axis transform or similar skeletal representations, to identify relevant shape features from this perceptual viewpoint. We discuss the results of each algorithm and compare them with those of the user study, leading to a practical solution for computing hierarchies of salient features on 2D shapes.

Convolution Surfaces based on Polygons for Infinite and Compact Support Kernels.
Graphical Models 74:1 (2012)
[doi:10.1016/j.gmod.2011.07.001]
[HAL]
Abstract:
We provide mathematical formulae to create 3D smooth shapes fleshing
out a skeleton made of line segments and planar polygons. The boundary
of the shape is alevel set of the sum of the convolution functions
for the basic elements of the skeleton. Providing the closed form
formulae for the convolution function generated by a polygon is the
main contribution of the present paper. We apply Green's theorem so as
to improve on previous results in several ways. First we do not
require the prior triangulation of the polygon.
Then, we obtain formulae for complete families of kernels, either
with infinite or compact supports. Last, but not least, the geometric
computations needed, in the case of compact support kernels, are
restricted to intersections of spheres with line segments, rather than
intersections of spheres with triangles in previous works.
Keywords:
Skeleton; Convolution Surfaces; Implicit Modeling; Computer Graphics;
Green's theorem; Recurrences; Symbolic Integration.

Warpbased Helical Implicit Primitives;
with C. Zanni and M.P. Cani.
Computers & Graphics volume 35:3 (2011)
[10.1016/j.cag.2011.03.027]
[HAL]
Abstract:
Implicit modeling with skeletonbased primitives has been limited up
to now to planar skeletons elements, since no closedform solution was
found for convolution along more complex curves. We show that warping
techniques can be adapted to efficiently generate convolutionlike
implicit primitives of varying radius along helices, a useful 3D
skeleton found in a number of natural shapes. Depending on a single
parameter of the helix, we warp it onto an arc of circle or onto a
line segment. For those latter skeletons closed form convolutions
are known for entire families of kernels. The new warps introduced preserve the
circular shape of the normal cross section to the primitive.
Keywords:
Circular helices; Skeleton; Implicit Modeling; Natural Shapes.

Convolution Surfaces based on Polygonal Curve Skeletons;
with M.P. Cani.
Journal of Symbolic Computation 47:6, pages 680699 (2012)
[doi:10.1016/j.jsc.2011.12.026]
[HAL]
Attachment: Maple code for the recurrence
Abstract:
This paper reviews and generalizes Convolution Surfaces, a technique
used in Computer Graphics to generate smooth 3D models around
polygonal line serving as skeletons. Convolution surfaces are
defined as level set of a function obtained by integrating a kernel
function along this skeleton. To allow interactive modeling, the
technique has relied on closed form formulae for integration
obtained through symbolic computation software. This paper provides
new qualitative results and generalizations on the topic. It is also
an opportunity for us to introduce the field of convolution surfaces
to the symbolic computation community, hoping that researchers well
versed into integration techniques can bring additional contribution
to this appealing shape representation.
Keywords:
Implicit Surfaces; Symbolic Integration; Recurrences.
Differential Invariants

Lagrangian Curves in 4dimensional Affine Symplectic space;
with Emilio Musso. Acta Applicandae
Mathematicae, 134:1 pages 133160 (2014).
[doi:10.1007/s1044001498743]
[HAL]
Abstract:
Lagrangian curves in 4space entertain intriguing relationships with
second order deformation of plane curves under the special affine
group and null curves in a 3dimensional Lorentzian space form. We
provide a natural affine symplectic frame for Lagrangian curves. It
allows us to classify Lagrangrian curves with constant symplectic
curvatures, to construct a class of Lagrangian tori and determine
Lagrangian geodesics.
Keywords: Symplectic geometry –
Lagrangian planes – Differential invariants – Moving frame – Lie
group actions.

Algebraic and Differential Invariants.
Foundations of Computational Mathematics, Budapest 2011,
London Mathematical Society Lecture Note Series (403), Cambridge
University Press (2012).
[doi:10.1017/CBO9781139095402]
[pdf].
Abstract:
We present the results of previous articles so as to show the
coherent series of algebraic and algorithmic tools they provide to handle differential invariants.
Keywords:
Group Actions; Rational invariants; Differential Invariants; Differential Algebra;
Moving Frame; Symmetry; Algebraic algorithms.
 Generation properties of MaurerCartan invariants.
Preprint
[hal:inria00194528], [video]
Abstract:
For the action of a Lie group, which can be given by its infinitesimal
generators only, we characterize a generating set of differential invariants
of bounded cardinality and show how to rewrite any other differential
invariants in terms of them. Those invariants carry geometrical
significance and have been used in equivalence problem in differential geometry.
Keywords:
Lie group actions; Differential invariants; Moving frame; MaurerCartan forms.

Differential invariants of a Lie group action: syzygies on a generating set.
Journal of Symbolic Computation, 44:4 pages 382416 (2009).
[doi:10.1016/j.jsc.2008.08.003]
[HAL], [video]
Abstract:
Given a group action, known by its infinitesimal generators,
we exhibit a complete set of syzygies on a generating
set of differential invariants.
For that we elaborate on the reinterpretation of
Cartan's moving frame by Fels and Olver (1999).
This provides constructive tools for
exploring algebras of differential invariants.
Keywords:
Lie group actions; Differential invariants; Moving frame;
Syzygies; Differential algebra; Symbolic computation

Differential Invariants of Conformal and Projective Surfaces;
with P. J. Olver,
Symmetry, Integrability and Geometry: Methods and Applications,
volume 3 (2007).
[doi:/10.3842/SIGMA.2007.097]
Abstract:
We show that, for both the conformal and projective groups, all the
differential invariants of a generic surface in threedimensional
space can be written as combinations of the invariant derivatives of a
single differential invariant. The proof is based on the equivariant
method of moving frames.
Keywords:
conformal differential geometry; projective differential geometry;
differential invariants; moving frame; syzygy; differential algebra;
symbolic computation.

Differential Algebra for Derivations with Nontrivial Commutation Rules,
Journal of Pure and Applied Algebra.
Volume 200, Issues 12, August 2005, Pages 163190.
[doi:10.1016/j.jpaa.2004.12.034].
[HAL]
Abstract:
The classical assumption of differential algebra,
differential elimination theory and
formal integrability theory is that the derivations do commute.
That is the standard case arising from systems of partial differential
equations written in terms of the derivations w.r.t. the independant
variables. We inspect here the case where the derivations
satisfy nontrivial commutation rules. That situation arises
for instance when we consider a system of equations on the differential
invariants of a Lie group action. We develop the algebraic foundations
for such a situation. They lead to algorithms for completion to formal
integrability and differential elimination.
Keywords:
Differential Algebra 
Differential Elimination  Differential Invariants
Computational differential algebra

Improvements to a triangulationdecomposition algorithm for ordinary
differential systems in higher degree cases.
ISSAC 2004.
[doi:10.1145/1005285.1005314]
[pdf]
Attachment:
Experimental evaluation of performances
Abstract:
We introduce new ideas to improve the efficiency
and rationality of a triangulation decomposition algorithm.
On the one hand we identify and
isolate the polynomial remainder sequences in the
triangulationdecomposition algorithm.
Subresultant polynomial remainder sequences are then used to compute
them and their specialisation properties are applied for the splittings.
The gain is two fold: control of expression swell
and reduction of the number of splittings.
On the other hand, we remove the role that initials had
in previous triangulationdecomposition algorithms.
They are not needed in theoretical results and it was expected
that they need not appear in the algorithms. This is the case
of the algorithm presented.
Keywords:
systems of differential equations, differential elimination,
differential ideal theory, triangular sets,
subresultant polynomial remainder sequence.

Computing Power Series Solutions of Nonlinear PDE systems,
with N. Le Roux,
ISSAC 2003.
[doi:10.1145/860854.860891]
[pdf]
Abstract:
This paper presents a new algorithm to compute the power series solutions of
a system of a significant class of nonlinear systems of partial
differential equations. The algorithm presented is very different
from previous algorithms to perform this task. Those
relie on differentiating iteratively the differential equations
to get coefficients of the power series one at a time.
The here presented algorithm relies on using the
linearisation of the system and is thus in the line of
Newton methods. At each step the
order up to which the power series solution is known is doubled.
Keywords:
nonlinear partial differential systems 
power series solutions  differential algebra  formal integrability.

Notes on triangular sets and triangulationdecomposition algorithms
I: Polynomial systems.
Chapter of Symbolic and Numerical Scientific Computations
Edited by U. Langer and F. Winkler.
LNCS, volume 2630, SpringerVerlag Heidelberg.
[doi:10.1007/354045084X_1]
[pdf]
Abstract:
This is the first in a series of two tutorial articles devoted to
triangulationdecomposition algorithms.
The value of these notes resides in the
uniform presentation of triangulationdecomposition of
polynomial and differential radical ideals with detailed proofs
of all the presented results.%, most of which are not original.
We emphasize the study of the mathematical objects
manipulated by the algorithms and show their properties
independently of those.
We also detail a selection of algorithms, one for each task.
We address here polynomial systems and some of the material
we develop here will be used in the second part,
devoted to differential systems.
Keywords: polynomial systems, triangular sets,
regular chains, characteristic sets, algorithms.
 Notes on triangular sets and
triangulationdecomposition algorithms II: Differential Systems.
Chapter of Symbolic and Numerical Scientific Computations
Edited by U. Langer and F. Winkler.
LNCS, volume 2630, SpringerVerlag Heidelberg.
[doi:10.1007/354045084X_2]
[pdf]
Attachment:
How to treat the examples of
applications given in the paper with the Maple library diffalg.
Abstract:
This is the second in a series of two tutorial articles devoted to
triangulationdecomposition algorithms. The value of these notes resides in the
uniform presentation of triangulationdecomposition of
polynomial and differential radical ideals with detailed proofs
of all the presented results. We emphasize the study of the mathematical objects
manipulated by the algorithms and show their properties
independently of those. We also detail a selection of algorithms, one for each task.
The present article deals with differential systems.
It uses results presented in the first article on polynomial
systems but can be read independently.
Keywords:
systems of nonlinear partial differential equations,
differential algebra, differential ideal theory, algorithms.

Probabilistic Algorithms for Computing Resolvent Representations of
Regular Differential Ideals;
with T. Cluzeau.
Applicable Algebra and Error Correcting Codes, volume 19, number 5, p365392
[doi:/10.1007/s0020000800798]
[HAL].
Abstract:
In a previous article, we proved the existence of resolvent
representations for regular differential ideals. The present paper
provides practical algorithms for computing such representations. We
propose two different approaches. The first one uses differential
characteristic decompositions whereas the second one proceeds by
prolongation and algebraic elimination. Both constructions depend on
the choice of a tuple over the differential base field and their
success relies on the chosen tuple to be separating. The probabilistic
aspect of the algorithms comes from this choice. To control it, we
exhibit a family of tuples for which we can bound the probability that
one of its element is separating.

Resolvent Representation for Regular Differential Ideals,
with T. Cluzeau,
Applicable Algebra in Engineering, Communication and Computing,
13:5, pages 395425, 2003.
[doi:10.1007/s0020000201104]
[HAL].
Abstract:
We show that the generic zeros of a differential ideal $[A]:H_A^\infty$ defined
by a differential chain $A$ are birationally equivalent to the
general zeros of a single regular differential polynomial. This provides a
generalization of both the cyclic vector construction for system of
linear differential equations and the rational univariate
representation of algebraic zero dimensional radical ideals.
Keywords:
differential algebra, differential primitive element,
cyclic vector, computer algebra, resolvent.

Factorization free decomposition algorithms in differential algebra,
Journal of Symbolic Computations, 2000, volume 29(45) pp641662.
[doi:10.1006/jsco.1999.0344]
[pdf]
Abstract:
Insight on the structure of differential ideals defined by coherent
autoreduced set allows one to uncouple the differential and algebraic
computations in a decomposition algorithm. Original results as well as
concise new proofs of already presented theorems are exposed.
As a consequence, an effective version of Ritt's algorithm can be simply described.

A note on the Lax pairs for Painleve equations,
with A. Kapaev,
Journal of Physics. A. Mathematical and General, volume 32, number 46 (1999).
[doi:10.1088/03054470/32/46/311]
Abstract:
The theory of integrable
integral operators suggests a new way for generating Lax pair
for the classical Painelvé equations. This method
involves a gauge transformation applied to
a linear system exactly solvable in terms of the classical
special funstions. Some of the Lax pairs we introduce are
known, others are new. The computationnal investigations were lead with
diffalg(99),
a MapleV package for differential elimination.
General and singular solutions of differential equations

Essential components of an algebraic differential equation,
Journal of Symbolic Computations, 1999, volume 28(45), 657680.
[doi:10.1006/jsco.1999.0319]
[pdf]
Abstract:
We present an algorithm to determine the essential
singular components of an algebraic differential equation.
Geometrically, this corresponds to
determine the singular solutions that have enveloping properties.
The algorithm is practical and efficient because it is
factorisation free, unlike the previous such algorithm.
This paper is self contained in the sense that it requires
nearly only to textbooks (Mainly Kolchin, 1973,
Differential Algebra and Algebraic Groups).

Detecting Degenerate Behaviors in NonLinear Differential Equations of First order
Algebraic Differential Equations
Theoretical Computer Science,1997, vol 187 (12), pages 725.
[doi:10.1016/S03043975(97)000546]
Abstract:
Differential geometric and algebraic ideas are exposed and transposed
into algorithms to detect and classify degenerate behaviors appearing in first order ordinary differential
equations. Differential geometry is considered for a local analysis.
It indeed gives insight on the behavior of the solutions
at singular points. A sequence of algebraic operations will be put forth to
split the locus of singular points according to their properties.
When part of the locus of singular points turns out to be a singular solution,
the set of solutions splits and shall be considered from a global
standpoint. To this aim, differential algebra allows to define rigorously
the general and particular solutions. Investigating further leads to
an original algorithm to compute a differential basis of the general
solution. This basis give means to determine which singular
solutions are particular solutions.
Keywords:
Singularities of Ordinary Differential Equations Singular Solutions
Particular Solutions  General Solution  Differential Algebra.

The general solution of an ordinary differential equation
ISSAC 1996.
[doi:10.1145/236869.237073]
[pdf]
Abstract:
We consider in this paper an implicit nonlinear ordinary differential
equation P(Z, y, y’) = O. There are several types of solutions.
The singular solutions are characterized by the fact they make and
vanish. No such characterization of the so called general solution
can be found in classical treatises.
We propose here an algorithmic method to compute a similar
characterisation of the general solution.
We apply the result to give some insight on the local behaviour of the
solutions in the neighbourhood of a singular solution.
Keywords:
General Solution, Singular Solutions, Differential algebra, Formal Power Series Solution.
Dynamical Systems

Constructing stable manifolds of stationary solutions,
with G. Moore,
IMA J. Numer. Anal., 1999, volume 19(3), pp 375424.
[doi:10.1093/imanum/19.3.375]
[pdf]
Abstract:
Algorithms for computing stable manifolds of hyperbolic stationary
solutions of autonomous systems are of two types: either the aim is to
compute a single point on th emanifold or the entire (local)
manifold. Traditionally only indirect methods have been considered,
i.e. first the continuous problem is discretised by a onestep scheme
and then the LiapunovPerron or Hadamard graph transform are applied
to the resulting discrete dynamical system. We will consider different
variants of these indirect methods but also algorithms of the above
two types which are applied to the continuous problem.
Comment:
See more links on the subject
on the web site of my MSc advisor
Pr. G. Moore.
HOME PAGE