Algebraic Solvers for Polynomial Systems
Session Organizers:
Session Abstract:
Polynomial systems are ubiquitous in problem modeling coming from many
scientific domains: Computer Science and Mathematics but also Biology,
Chemistry, Physics, Robotics. Algebraic methods for polynomial system solving
allow one to compute an exact representation of the solutions of the system.
In general, such methods rely on elimination theory, we can cite the
geometric resolution, lexicographic Gröbner bases, regular chains or
multivariate resultants.
As these methods allow the user to compute all the solutions of the system and
since their algorithmic does not depend on the base field, they proved
to be successful in many contexts and applications. In particular,
they are well-suited when one needs to perform computations in
positive characteristic and most computer algebra systems provide solvers based
on them.
This ICMS session is dedicated to these algebraic methods and their
implementations, such as, but not limited to, in a low-level language or in a
CAS.
Session Talks:
msolve
Jérémy Berthomieu (Sorbonne Université),
Christian Eder (Rheinland-Pfälzische Technische
Universität Kaiserslautern--Landau),
Vincent Neiger (Sorbonne Université),
Mohab Safey El Din (Sorbonne Université),
The open-source C library msolve is dedicated to solving multivariate
polynomial systems through computer algebra methods. The core framework
of msolve relies
on Gröbner bases and linear algebra based algorithms.
Ore Algebras in OSCAR
Kamillo Ferry (Technische Universität Berlin)
An Ore algebra is a skew-commutative ring useful for representing
linear differential and recurrence operators.
We present a basic implementation of Ore algebras and D-finite functions in the
computer algebra system OSCAR
as a starting point and discuss avenues for further developments.
Gröbner bases of determinantal ideals
Sriram Gopalakrishnan (Sorbonne Université & University of Waterloo)
Abstract.
A data structure for monomial ideals in signature Gröbner basis
computations
Théo Ternier (Inria & Université Paris-Saclay)
Abstract.
On True Arc-Length Parameterized Splines
Dafna K.Matsegora (Waterloo), Stephen M.Watt (Waterloo)
We present an iterative algorithm to compute arc-length parameterized
splines through a set of points. This differs from other methods
where the parameterization is not by the actual arc-length of the
computed spline and from other spline methods that do not fit the given
points. Our method is applicable to d-dimensional splines for d ≥ 2, and
we illustrate it with numerical results for d = 2.
Stability of Sobolev-Regularized Polynomial Differentiation Matrices
Deepak Singh Kalhan (Waterloo), Robert Corless (Western), Stephen Watt (Waterloo)
Differentiation matrices based on orthogonal polynomial bases grow
rapidly with degree, leading to numerical instability in high-order
approximations. We study the effect of Sobolev regularization, which
introduces derivative information into the inner product, on the
behavior of these operators.
We show that Sobolev regularization reduces the growth rate of
differentiation operators. In particular, for both Legendre–Sobolev
and Chebyshev–Sobolev bases, the operator and Frobenius norms decrease
by one order in the polynomial degree compared to the classical case.
We further characterize a transition between unstable and stabilized
regimes by the parameter $\mu$, with scaling controlled by $\mu N^3$.
Although both polynomial families exhibit the same asymptotic
behavior, their $\mu$-dependent mode mixing differs, reflecting
structural differences in the underlying bases.