Computing the set of asymptotic critical values of polynomial mappings from smooth algebraic sets - Sorbonne Université
Preprints, Working Papers, ... Year : 2022

Computing the set of asymptotic critical values of polynomial mappings from smooth algebraic sets

Jérémy Berthomieu
Andrew Ferguson
  • Function : Author
  • PersonId : 1076496
Mohab Safey El Din

Abstract

Let $\mathbf{f} = (f_1, \dots, f_p) \in \mathbb{Q}[z_1, \dots, z_n]$ be a polynomial tuple. Define the polynomial mapping $\mathbf{f}: X \to \mathbb{C}^p$, where $X$ is a smooth algebraic set defined by the simultaneous vanishing of the reduced regular sequence $g_1, \dots, g_m$, with $m+p \leq n$. Let $d = \max(\deg f_1, \dots, \deg f_p, \deg g_1, \dots, \deg g_m)$, $\operatorname{d} \mathbf{f}$ be the differential of $\mathbf{f}$ and $\kappa$ be the function measuring the distance of a linear operator to the set of singular linear operators from $\mathbb{C}^n$ to $\mathbb{C}^p$. We consider the problem of computing the set of asymptotic critical values of $\mathbf{f}$. This is the set of values $c$ in the target space of $\mathbf{f}$ such that there exists a sequence of points $(\mathbf{x}_i)_{i\in \mathbb{N}}$ tending to $\infty$ for which $\mathbf{f}(\mathbf{x}_i)$ tends to $c$ and $\|\mathbf{x}_i\|\kappa(\operatorname{d} \mathbf{f}(\mathbf{x}_i))$ tends to $0$ when $i$ tends to infinity. The union of the classical and asymptotic critical values contains the so-called bifurcation set of a polynomial mapping. Thus, by computing both the critical values and the asymptotic critical values, one can utilise generalisations of Ehresmann's fibration theorem in non-proper settings for applications in polynomial optimisation and computational real algebraic geometry. We design new efficient algorithms for computing the set of asymptotic critical values of a polynomial mapping restricted to a smooth algebraic set. By investigating the degree of the objects constructed in our algorithms, we give the first bound on the degree of this set of values of $pD$, where $D = d^{n-p-1} \sum_{i = 0}^{p+1} \binom{n+p-1}{m+2p+i} d^i$. We also give the first complexity analysis of this problem, showing that it requires at most $\tilde{O}\left( p (p+1) D^{p+5} + (n+m+2p)^{d+3} D^{p+4}\right)$ operations in the base field. Moreover, in the special case $p=1$, we give another complexity estimate of $\tilde{O}((n+m+2)^{d+3} D^5)$ arithmetic operations. Additionally, we show how to apply these algorithms to polynomial optimisation problems and the problem of computing sample points per connected component of a semi-algebraic set defined by a single inequality/inequation. We provide implementations of our algorithms and use them to test their practical capabilities. We show that our algorithms significantly outperform the current state-of-the-art algorithms by tackling previously out of reach benchmark examples.
Fichier principal
Vignette du fichier
main.pdf (444.71 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03598352 , version 1 (04-03-2022)

Identifiers

  • HAL Id : hal-03598352 , version 1

Cite

Jérémy Berthomieu, Andrew Ferguson, Mohab Safey El Din. Computing the set of asymptotic critical values of polynomial mappings from smooth algebraic sets. 2022. ⟨hal-03598352⟩
169 View
106 Download

Share

More