You are here

Computer Algebra

The computer algebra team develops new computational methods with the goal of obtaining exact symbolic representations, as well as certified qualitative and quantitative information on solutions of differential, polynomial and functional equations. Such theoretical and algorithmic results are implemented in software packages that extend the scope of pre-existing solvers for the modelisation and solution of scientific problems.

Research

The research activity of the group follows two main themes.

1. Differential and Functional Equations

Our group has a well-estabilished expertise not only on linear differential systems, but also, more generally, on functional systems (e.g., q-difference, Ore, PDE systems) and nonlinear systems.

Our work covers all the steps from abstract theory to applications and implementation, therefore establishing a link between theorists and algorithm developers.

  • Linear differential/functional systems. We study linear differential or difference equations/systems, with a focus on the design of effective algorithms and their implementation in a computer algebra environment (Maple and Mathemagix packages).
  • Constructive algebraic analysis and multidimensional systems. The groups works on stability and stabilisation problems for linear multidimensional systems using constructive algebraic analysis (system isomorphisms and equivalence, Serre reduction).
  • Nonlinear problems and applications. We are also interested in applications, which provide motivation for theoretical analysis and benchmarks for designing and testing effective algorithms. Topics include integrability of dynamical and mechanical systems, applications in statistical mechanics and analytic combinatorics, locally nilpotent derivations, covariants of symplectic groups applied to vector fields. 
  • Study of p-adic differential equations. Our team works on the effective study of p-adic differential equations, with applications for counting-points methods and isogeny computations.

2. Symbolic-Numeric Computation

Many problems motivated by practical applications need a combination of symbolic and numerical approaches. Examples include, for instance, boundary parametrisation in the context of shape optimisation, or the computation of series expansions for algebraic functions. In this context, the research work pursued by our team focuses on three main areas.

  • Computing with algebraic functions. The computation of series expansions for algebraic functions uses a symbolic approach to obtain exact information, together with numerical methods for approximate computation of the coefficients. This technique allows us to improve the complexity of the method in the case of finite fields.
  • Numerical linear algebra, structured matrices and applications. Our group works on numerical linear algebra problems for matrices that display a special structure (such as quasiseparable or displacement structure). Such matrices have an important role in several mathematical applications: approximate polynomial gcd, fast eigenvalue computation, behaviour of functions of sparse matrices.
  • Effective algebraic geometry. The group has an estabilished know-how on constructive methods in algebraic geometry and applications, particularly in cryptography and shape optimisation. We are also interested in effective computations in non-archimedean geometry: p-adic Gröbner bases, tropical Gröbner bases.
  • Operations over p-adics. This research theme focuses on the study of the p-adic precision for basic operations over p-adics (in particular over polynomials or in linear algebra), with a view toward p-adic symbolic-numeric methods.

Software

The following Maple and Mathemagix packages belong to the research theme Linear differential/functional systems :

  • ParamInt and PfaffInt (matrix differential systems, singularly perturbed differential systems and formal reduction of PDEs),
  • IntegrableConnections (global solutions of systms of D-finite PDEs),
  • AppSing (desingularisation of differential and Ore systems),
  • miniISOLDE and Lindalg (algorithmics and symbolic solution of functional, differential or q-difference systems),
  • TensorConstructions (effective Galois theory through tensors and reduced forms).

The study of functional linear systems through constructive algebraic analysis has produced the Maple package OreMorphisms and the Mathematica package OreAlgebraicAnalysis.

The Maple package RationalFirstIntegrals has been developed to compute first integrals of polynomial vector fields.

Software pertaining to Symbolic-Numeric Computation includes:

  • Maple and Matlab code to compute invariant pairs for nonlinear eigenvalue problems;
  • Matlab and Fortran code FastQR and FastQZ for fast eigenvalue computation,
  • contributions to the development of the Mathemagix computational environment.

Projects and workgroups

Our team is part of the Computer Algebra workgroup of the GDR IM (Informatique-Mathématique) and of the following projects:

  • COMUE Léonard de Vinci/fédération MIRES: LIE-GALOIS, GEOM-ALG, SATIN and MSDOS,
  • PEPS projects: SADDLES and HOLONOMIX,
  • ANR projects: the ongoing MSDOS project and other projects that have successfully passed the first evaluation step.

Conferences and seminars

Our team organises a weekly seminar. Moreover, it organises every year two international workshops: