Résumé technique : Calcul de solutions singulières de systèmes polynomiaux

Énoncé du problème

L'article traite du calcul numérique de solutions singulières isolées de systèmes d'équations polynomiales $f(z) = 0$ dans le cadre de la Géométrie Algébrique Numérique (GAN). Les approches standards utilisent la continuation par homotopie, en suivant une courbe de solution $z(t)$ définie par $h(z(t), t) = 0$ d'un système de départ connu vers le système cible lorsque $t \to 0$.

Le défi principal survient dans le régime de l'« endgame » (fin de parcours), où $t$ approche de zéro et que la solution $z^* = z(0)$ est singulière (c'est-à-dire que la jacobienne $f_z(z^*)$ est de rang déficient). Dans cette région, les correcteurs de Newton standards échouent en raison de la singularité de la jacobienne, et les méthodes existantes peinent souvent avec les taux de convergence ou nécessitent des dérivées d'ordre supérieur coûteuses en termes de calcul. Les auteurs se concentrent sur des systèmes où la solution est isolée et où l'homotopie satisfait des conditions spécifiques de transversalité et de régularité (Hypothèse 1), garantissant l'existence d'une expansion en série de Puiseux de la courbe de solution.

Méthodologie

L'approche proposée, nommée Arclength Endgame (fin de parcours par longueur d'arc), combine des techniques de continuation par pseudo-longueur d'arc avec l'estimation des paramètres de la série de Puiseux. La méthode est divisée en deux phases : une phase de prédicteur et une phase de correcteur.

1. Phase de prédicteur

L'objectif est d'estimer les termes principaux de la série de Puiseux $z(t) = z^* + \sum a_j t^{k_j/c}$ pour prédire la solution à $t=0$ (ou un petit $t$).

• Estimation des exposants : Les auteurs introduisent une nouvelle méthode, cRATIO, pour estimer le rapport d'exposant fractionnaire principal $k_1/c$. Cette méthode utilise le rapport des normes $\|t \dot{z}(t) - t_1 \dot{z}(t_1)\| / \|z(t) - z(t_1)\|$, qui converge vers $k_1/c$ quand $t \to 0$. Ils comparent cette méthode aux méthodes existantes comme cSORT (par essais et erreurs) et cLOG (échantillonnage de séquences géométriques), notant la stabilité empirique de cRATIO.
• Estimation d'ordre supérieur : Pour les systèmes nécessitant une précision d'ordre supérieur, l'article propose une méthode récursive pour estimer les rapports successifs $k_i/c$ (pour $i \ge 2$) en appliquant la logique d'estimation de $k_1/c$ à des fonctions transformées dérivées de la série originale.
• Estimation des coefficients : Les auteurs présentent un nouveau schéma pour estimer les coefficients $a_{k_i}$ en utilisant l'inversion d'une matrice de Vandermonde scalée. Contrairement à l'interpolation de Hermite classique qui suppose des exposants denses $(1, 2, 3)$, cette méthode accepte des exposants creux et utilise des dérivées d'ordre supérieur (approximées via des différences finies de Hermite pour éviter le calcul de la hessienne).

2. Phase de correcteur

Une fois qu'un point prédit $\hat{x}$ est estimé, le système est augmenté pour restaurer la non-singularité de la méthode de Newton.

• Corank-1 ($\kappa=1$) : Le système $h(x)=0$ est augmenté d'une équation linéaire unique $q \cdot (x - \hat{x}) = 0$, où $q$ est un vecteur orthogonal à la tangente de la courbe de solution (dérivé du noyau de la jacobienne augmentée $[h_z, h_t]$). Cela crée un système carré bien conditionné, soluble par la méthode de Newton.
• Corank $\kappa \ge 2$ (Lifted Arclength Endgame) : Pour des coranks plus élevés, la méthode introduit $\kappa-1$ variables auxiliaires et $\kappa$ hyperplans pour régulariser le système. Étant donné que le point résultant peut ne pas se trouver sur l'homotopie originale, les auteurs proposent une stratégie de « levage » (lifted) : l'homotopie est dynamiquement réinitialisée en une homotopie de Newton $h_v(z, t) = f(z) - t f(v)$, où $v$ est la solution affinée. Cela permet de poursuivre l'affinement de la solution près de la singularité.

Contributions clés

1. Arclength Endgame pour le corank-1 : Les auteurs introduisent un nouvel algorithme pour les systèmes de corank-1 qui atteint une convergence superlinéaire au voisinage de la racine singulière. Crucialement, cette méthode repose uniquement sur les évaluations du système et de sa jacobienne, évitant le calcul des dérivées d'ordre supérieur requis par les méthodes de déflation ayant une convergence superlinéaire prouvée.
2. Lifted Arclength Endgame : Une extension heuristique pour les systèmes avec un corank $\kappa \ge 2$. Bien que des preuves formelles de convergence ne soient pas fournies pour ce cas, les résultats expérimentaux démontrent un comportement de convergence superlinéaire prometteur.
3. Amélioration de l'estimation de la série de Puiseux :
   • Une nouvelle méthode stable (cRATIO) pour estimer l'exposant fractionnaire principal $k_1/c$.
   • Un nouveau cadre récursif pour estimer les exposants fractionnaires d'ordre supérieur ($k_i/c$ pour $i \ge 2$) et leurs coefficients associés, permettant des prédicteurs d'ordre supérieur pour les séries de Puiseux creuses.
4. Garanties théoriques : L'article fournit des preuves formelles (Théorème 1 et Corollaire 2) établissant le taux de convergence superlinéaire pour le cas du corank-1, dépendant de la précision de l'estimation de l'exposant et du voisinage de la racine.

Résultats

Les auteurs comparent leurs méthodes (AL pour le corank-1, LAL pour le corank $\ge 2$) à l'approche classique de la série de puissance (CLASSIC) en utilisant une suite de systèmes polynomiaux, incluant les systèmes Griewank-Osborne, Lecerf et Caprasse, ainsi que des systèmes générés sur mesure avec des coranks et des nombres d'enroulement spécifiques.

• Convergence : Les graphiques (Figures 1–12) illustrent le résidu de suivi $\log_{10} \|f(z)\|$ par rapport au nombre cumulé d'inversions de matrices. Les méthodes proposées démontrent généralement une convergence plus rapide (descente plus raide du résidu) et la capacité d'atteindre des résidus plus profonds avec moins d'inversions de matrices par rapport à l'approche classique, particulièrement dans le régime profond de l'endgame.
• Stabilité : La comparaison des méthodes d'estimation d'exposant (Figures 13–18) suggère que la méthode cRATIO proposée offre une stabilité compétitive ou supérieure à cSORT et cLOG dans diverses instances de tests.
• Robustesse : L'approche de levage (LAL) gère avec succès les systèmes avec des coranks plus élevés là où les endgames standards échouent ou stagnent, maintenant la convergence grâce à la réinitialisation dynamique de l'homotopie.

Signification et revendications

L'article affirme que l'Arclength Endgame constitue une avancée significative dans le calcul de solutions singulières en atteignant une convergence superlinéaire sans la surcharge de calcul des techniques de déflation (qui nécessitent des dérivées d'ordre supérieur et peuvent augmenter considérablement la dimension du système).

Les auteurs soulignent que leur méthode est « consciente de l'endgame » (endgame-aware), utilisant explicitement les propriétés géométriques de la courbe de solution (série de Puiseux) pour régulariser le système. Ils positionnent ce travail comme une amélioration pratique de la Géométrie Algébrique Numérique, fournissant une méthode qui est à la fois théoriquement fondée (pour le corank-1) et empiriquement efficace (pour le corank plus élevé), tout en reposant sur des évaluations standards de la fonction et de la jacobienne. Le travail ne prétend pas résoudre universellement toutes les singularités, mais cible spécifiquement le régime des racines singulières isolées sous des hypothèses d'homotopie génériques.