Optimization of trigonometric polynomials with crystallographic symmetry and spectral bounds for set avoiding graphs; with
T. Metzlaff, P. Moustrou and C. Riener.
[hal-03768067]
Abstract:
Trigonometric polynomials are usually defined on the lattice of integers. We consider the larger class of weight and root lattices with crystallographic symmetry. This article gives a new approach to minimize trigonometric polynomials, which are invariant under the associated reflection group. The invariance assumption allows us to rewrite the objective function in terms of generalized Chebyshev polynomials. The new objective function is defined on a compact basic semi-algebraic set, so that we can benefit from the rich theory of polynomial optimization. We present an algorithm to compute the minimum: Based on the Hol-Scherer Positivstellensatz, we impose matrix-sums of squares conditions on the objective function in the Chebyshev basis. The degree of the sums of squares is weighted, defined by the root system. Increasing the degree yields a converging Lasserre-type hierarchy of lower bounds. This builds a bridge between trigonometric and polynomial optimization, allowing us to compare with existing techniques. The chromatic number of a set avoiding graph in the Euclidean space is defined through an optimal coloring. It can be computed via a spectral bound by minimizing a trigonometric polynomial. If the to be avoided set has crystallographic symmetry, our method has a natural application. Specifically, we compute spectral bounds for the first time for boundaries of symmetric polytopes. For several cases, the problem has such a simplified form that we can give analytical proofs for sharp spectral bounds. In other cases, we certify the sharpness numerically.
Keywords: Trigonometric Optimization; Crystallographic Symmetry; Lattices; Chebyshev Polynomials; Chromatic Numbers; Set Avoiding Graphs; Spectral Bound.
Polynomial description for the T-Orbit Spaces of Multiplicative Actions; with
T. Metzlaff and C. Riener.
[hal-03590007]
Abstract:
The Weyl group of a crystallographic root system has a nonlinear action on the compact torus. The orbit space of this action is a compact basic semi-algebraic set. We present a polynomial description of this set for the Weyl groups of type A, B, C, D and G. Our description is given through a polynomial matrix inequality. The novelty lies in an approach via Hermite quadratic forms and a closed formula for the matrix entries. The orbit space of the nonlinear Weyl group action is the orthogonality region of generalized Chebyshev polynomials. In this polynomial basis, we show that the matrices obtained for the five types follow the same surprisingly simple pattern. The results presented apply to the optimization of trigonometric polynomials with crystallographic symmetries for instance.
Keywords: Orbit space; Weyl groups; Multiplicative Invariant Theory; Chebyshev polynomials; Polynomial matrix inequalities; Semi-algebraic sets.
Abstract:
Sparse interpolation refers to the exact recovery of a function as a short linear combination of basis functions from a limited number of evaluations. For multivariate functions, the case of the monomial basis is well studied, as is now the basis of exponential functions. Beyond the multivariate Chebyshev polynomial obtained as tensor products of univariate Chebyshev polynomials, the theory of root systems allows to define a variety of generalized multivariate Chebyshev polynomials that have connections to topics such as Fourier analysis and representations of Lie algebras. We present a deterministic algorithm to recover a function that is the linear combination of at most r such polynomials from the knowledge of r and an explicitly bounded number of evaluations of this function.
Symmetry in Multivariate Ideal Interpolation; with
E. Rodriguez Bazan. Journal of Symbolic Computation 115:174-200 (2023) [doi:10.1016/j.jsc.2022.08.014]
[hal-03129766]
Abstract:
An interpolation problem is defined by a set of linear forms on the (multivariate) polynomial ring and values to be achieved by an interpolant. For Lagrange interpolation the linear forms consist of evaluations at some nodes, while Hermite interpolation also considers the values of successive derivatives. Both are examples of ideal interpolation in that the kernels of the linear forms intersect into an ideal. For an ideal interpolation problem with symmetry, we address the simultaneous computation of a symmetry adapted basis of the least interpolation space and the symmetry adapted H-basis of the ideal. Beside its manifest presence in the output, symmetry is exploited computationally at all stages of the algorithm. For an ideal invariant, under a group action, defined by a Groebner basis, the algorithm allows to obtain a symmetry adapted basis of the quotient and of the generators. We shall also note how it applies surprisingly but straightforwardly to compute fundamental invariants and equivariants of a reflection group.
Ideal interpolation, H-bases, and Symmetry; with
E. Rodriguez Bazan. ISSAC 2020.
Proceedings of the 2020 on International Symposium on Symbolic and Algebraic Computation,
Pages 402-409, ACM Press (2020).
[doi:10.1145/3373207.3404057]
[hal-02482098]
Comment: This conference article was developed in the journal article above.
Multivariate interpolation: Preserving and exploiting symmetry; with
E. Rodriguez Bazan. Journal of Symbolic Computation 107:1-22 (2021)
[doi:10.1016/j.jsc.2021.01.004]
[hal-03123418],[Video]
Abstract:
Interpolation is a prime tool in algebraic computation while symmetry is a qualitative feature that can be more relevant to a mathematical model than the numerical accuracy of the parameters. The article shows how to exactly preserve symmetry in multivariate interpolation while exploiting it to alleviate the computational cost. We revisit minimal degree and least interpolation with symmetry adapted bases, rather than monomial bases. For a space of linear forms invariant under a group action, we construct bases of invariant interpolation spaces in blocks, capturing the inherent redundancy in the computations. With the so constructed symmetry adapted interpolation bases, the uniquely defined interpolant automatically preserves any equivariance the interpolation problem might have. Even with no equivariance, the computational cost to obtain the interpolant is alleviated thanks to the smaller size of the matrices to be inverted.
Symmetry Preserving Interpolation; with
E. Rodriguez Bazan. ISSAC'19.
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation,
Pages 34-41, ACM Press (2019) .
[doi:10.1145/3326229.3326247]
[hal-01994016],[Video]
Comment:
This conference article was developed in the journal article above.
Algorithms for computing cubatures based on moment theory; with
M. Collowald. Studies in Applied Mathematics, 141:501-546 (2018).
[ doi:10.1111/sapm.12240],
[hal-01188290],
[video]
Abstract:
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. In this article, we elaborate algorithms to compute all minimal cubatures for a given domain and a given degree. We propose first algorithm in symbolic computation to characterize all cubatures of a given degree with a fixed number of nodes. The determination of the nodes and weights is then left to the computation of the eigenvectors of the matrix identified at the characterization stage and can be performed numerically. The characterization of cubatures on which our algorithms are based stems from moment theory. We formulate the results there in a basis‐independent way: Rather than considering the moment matrix, the central object in moment problems, we introduce the underlying linear map from the polynomial ring to its dual, the Hankel operator. This makes natural the use of bases of polynomials other than the monomial basis, and proves to be computationally relevant, either for numerical properties or to exploit symmetry.
A moment matrix approach to computing symmetric cubatures; with
M. Collowald.
[hal-01188290],
[video]
Abstract:
Standard domains of integration
are symmetric under the action of a finite group. It is natural to
look for cubatures that respect this symme https://doi.org/10.1016/j.cag.2019.05.018 try.
Introducing adapted bases obtained from representation theory,
the symmetry constraint allows to block diago-nalize the Hankel
operator H. We then deal with smaller-sized 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
Algorithms for fundamental invariants and equivariants
(of finite groups); with E. Rodriguez Bazan. Mathematics of Computation, volume 91 number 337 pages 2459-2488 (2022)
[doi:10.1090/mcom/3749]
[hal-03209117]
Abstract:
For a finite group, we present three algorithms to compute
a generating set of invariant
simultaneously to generating sets of basic equivariants,
i.e., equivariants for the irreducible representations of the group.
The main novelty resides in the exploitation of the orthogonal
complement of the ideal generated by invariants;
Its symmetry adapted basis delivers the fundamental equivariants.
Fundamental equivariants allow to assemble symmetry adapted bases of
polynomial spaces of higher degrees, and these are
essential ingredients in exploiting and preserving symmetry
in computations.
They appear within algebraic computation and beyond,
in physics, chemistry and engineering.
Our first construction applies solely to reflection groups
and consists in applying symmetry preserving
interpolation, as developed by the same authors,
along an orbit in general position.
The fundamental invariants can be read off the H-basis
of the ideal of the orbit
while the fundamental equivariants are obtained
from a symmetry adapted basis of an invariant direct
complement to this ideal in the polynomial ring.
The second algorithm takes as input primary
invariants and the output provides not only
the secondary invariants but also
free bases for the modules of basic equivariants.
These are constructed as the components of
a symmetry adapted basis of the orthogonal complement,
in the polynomial ring,
to the ideal generated by primary invariants.
The third algorithm proceeds degree by degree,
determining the fundamental invariants as forming
a H-basis of the Hilbert ideal,
i.e., the polynomial ideal generated by the invariants of positive degree.
The fundamental equivariants are simultaneously
computed degree by degree as the components of
a symmetry adapted basis of the orthogonal complement of the Hilbert ideal.
Keywords:
finite groups; representation theory; polynomial invariants;
equivariants; covariants; symmetry adapted bases; H-basis; computational invariant theory.
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 B3-equivariance properties. Our explicit construction of these bases should be relevant well beyond the scope of this paper. The expression of the B3-invariants can then be given in a compact form as the composition of two equivariant maps. Instead of providing (cumbersome) explicit expressions for the O3-invariants, we provide efficient algorithms for their evaluation and rewriting. We also use the constructed B3-invariants to determine the O3-orbit 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.
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 3029-3050 (2016).
[doi:10.1090/mcom/3076]
[hal-00921905]
Abstract:
We investigate the computation and applications of rational
invariants of the linear action of a finite abelian group in the
non-modular 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)
[doi:10.5802/ccirm.19],
[HAL]
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.
Rational invariants of scalings from Hermite normal forms;
with G. Labahn. ISSAC 2012, pages 219-226, 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 345-383 (2007)
[doi:10.1007/s10208-006-0219-0]
[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;
cross-section; moving frame method; Groebner basis.
Rational Invariants of a Group Action. Construction and Rewriting;
with I. Kogan. Journal of Symbolic Computation, 42:1-2 pages 203-217 (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
cross-section is added to the ideal of the graph. Zero-dimensionality
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]
Anisotropic convolution surfaces.
with A. Fuentes Suarez and C. Zanni. Computers and Graphics 82:106-116 (2019).
[doi:10.1016/j.cag.2019.05.018]
[HAL]
Abstract:
Convolution surfaces with 1D skeletons have been limited to close-to-circular normal sections. The new formalism presented here allows for ellipsoidal normal sections. Anisotropy is prescribed on G^1 skeletal curves, chosen as circular splines, by a rotation angle and the three radii of an ellipsoid at each extremity. This lightweight model creates smooth shapes that previously required tweaking the skeleton or supplementing it with 2D pieces. The scale invariance of our formalism achieves excellent radii control and thus lends itself to approximate a variety of shapes. The construction of a scaffold is extended to skeletons with G 1 branches. It projects onto the convolution surface as a quad mesh with skeleton bound edge-flow.
Scaffolding skeletons using spherical Voronoi diagrams: feasibility, regularity and symmetry;
with A. Fuentes Suarez. Computer-Aided Design, 102:83-93 (2018).
[doi:10.1016/j.cad.2018.04.016]
[HAL]
Abstract:
Given a skeleton made of line segments we describe how to obtain a coarse quad mesh of a surface that encloses tightly the skeleton and follows its structure-the scaffold. We formalize as an Integer Linear Program the problem of constructing an optimal scaffold that minimizes the total number of quads on the mesh. We prove the feasibility of the Integer Linear Program for any skeleton. In particular we can generate these scaffolds for skeletons with cycles. We additionally show how to obtain regular scaffolds, i.e. with the same number of quad patches around each line segment, and symmetric scaffolds that respect the symmetries of the skeleton. An application to polygonization of skeleton-based implicit surfaces is also presented.
Convolution surfaces with varying radius: Formulae for skeletons made of arcs of circles and line segments;
with A. Fuentes Suarez. Research in Shape Analysis, Springer AWM book series volume 12, pages 37-60 (2018).
[doi:10.1007/978-3-319-77066-6_3]
[HAL]
Abstract:
In skeleton-based geometric modeling, convolution is an established technique: smooth surfaces around a skeleton made of curves are given as the level set of a convolution field. Varying the radius or making the surface scale sensitive along the skeleton are desirable features. This article provides the related necessary closed-form formulae of the convolution fields when the skeleton is made of arcs of circle and line segments. For the family of power inverse kernels, closed-form formulae are exhibited in terms of recurrence relationships. These are obtained by creative telescoping. This novel technique is described from a practitioner point of view so as to be applied to other families of kernels or skeleton primitives. The newly obtained formulae are applied to obtain convolution surfaces around G1 skeleton curves, some of them closed curves. Having arcs of circles in addition to line segments allows to demonstrably improve the visual quality of the generated surface with a lower number of skeleton primitives.
Scaffolding a Skeleton;
with A. Panotopoulou, E. Ross, K. Welker, G. Morin.
Research in Shape Analysis, Springer AWM book series volume 12, pages 17-35 (2018).
[doi:10.1007/978-3-319-77066-6_2]
[HAL]
Abstract:
The goal of this paper is to construct a quadrilateral mesh around a one-dimensional skeleton that is as coarse as possible, the “scaffold.” A skeleton allows one to quickly describe a shape, in particular a complex shape of high genus. The constructed scaffold is then a potential support for the surface representation: it provides a topology for the mesh, a domain for parametric representation (a quad-mesh is ideal for tensor product splines), or, together with the skeleton, a grid support on which to project an implicit surface that is naturally defined by the skeleton through convolution. We provide a constructive algorithm to derive a quad-mesh scaffold with topologically regular cross-sections (which are also quads) and no T-junctions. We show that this construction is optimal in the sense that no coarser quad-mesh with topologically regular cross-sections may be constructed. Finally, we apply an existing rotation minimization algorithm along the skeleton branches, which produces a mesh with a natural edge flow along the shape.
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 1079-1099 (2015).
[doi:10.1007/s10444-014-9401-0]
[HAL]
Abstract:
We reconstruct an n-dimensional 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.
Warp-based 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 skeleton-based primitives has been limited up
to now to planar skeletons elements, since no closed-form solution was
found for convolution along more complex curves. We show that warping
techniques can be adapted to efficiently generate convolution-like
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 680-699 (2012)
[doi:10.1016/j.jsc.2011.12.026]
[HAL]
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 4-dimensional Affine Symplectic space;
with Emilio Musso. Acta Applicandae
Mathematicae, 134:1 pages 133-160 (2014).
[doi:10.1007/s10440-014-9874-3]
[HAL]
Abstract:
Lagrangian curves in 4-space entertain intriguing relationships with
second order deformation of plane curves under the special affine
group and null curves in a 3-dimensional 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.
Abstract:
We show that, for both the conformal and projective groups, all the
differential invariants of a generic surface in three-dimensional
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 1-2, August 2005, Pages 163-190.
[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 triangulation-decomposition 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
triangulation-decomposition 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 triangulation-decomposition 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 triangulation-decomposition algorithms
I: Polynomial systems.
Chapter of Symbolic and Numerical Scientific Computations
Edited by U. Langer and F. Winkler.
LNCS, volume 2630, Springer-Verlag Heidelberg.
[doi:10.1007/3-540-45084-X_1]
[pdf]
Abstract:
This is the first in a series of two tutorial articles devoted to
triangulation-decomposition algorithms.
The value of these notes resides in the
uniform presentation of triangulation-decomposition 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
triangulation-decomposition algorithms II: Differential Systems.
Chapter of Symbolic and Numerical Scientific Computations
Edited by U. Langer and F. Winkler.
LNCS, volume 2630, Springer-Verlag Heidelberg.
[doi:10.1007/3-540-45084-X_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
triangulation-decomposition algorithms. The value of these notes resides in the
uniform presentation of triangulation-decomposition 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, p365-392
[doi:/10.1007/s00200-008-0079-8]
[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 395-425, 2003.
[doi:10.1007/s00200-002-0110-4]
[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(4-5) pp641-662.
[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/0305-4470/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(4-5), 657-680.
[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 Non-Linear Differential Equations of First order
Algebraic Differential Equations
Theoretical Computer Science,1997, vol 187 (1-2), pages 7-25.
[doi:10.1016/S0304-3975(97)00054-6]
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.
Abstract:
We consider in this paper an implicit non-linear 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
Scaling Invariants and Symmetry Reduction of Dynamical Systems; with
G. Labahn. Foundations Computational Mathematics. 13:4 pages
479-516 (2013)
[doi:10.1007/s10208-013-9165-9]
[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.
Constructing stable manifolds of stationary solutions,
with G. Moore,
IMA J. Numer. Anal., 1999, volume 19(3), pp 375-424.
[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 one-step scheme
and then the Liapunov-Perron 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 articles on the subject in the bibliography of my then MSc advisor
Pr. G. Moore.