Sintesi Tecnica: Calcolo di Soluzioni Singolari di Sistemi Polinomiali

Definizione del Problema

Il documento affronta il calcolo numerico di soluzioni singolari isolate di sistemi di equazioni polinomiali $f(z) = 0$ nell'ambito della Geometria Algebrica Numerica (NAG). Gli approcci standard utilizzano la continuazione di omotopia, tracciando una curva di soluzione $z(t)$ definita da $h(z(t), t) = 0$ da un sistema iniziale noto verso il sistema target al tendere di $t \to 0$.

La sfida principale sorge nel regime di "endgame", dove $t$ si avvicina a zero e la soluzione $z^* = z(0)$ è singolare (ovvero, il Jacobiano $f_z(z^*)$ è a rango deficitaria). In questa regione, i correttori standard basati su Newton falliscono a causa della singolarità del Jacobiano, e i metodi esistenti spesso faticano con i tassi di convergenza o richiedono derivate di ordine superiore computazionalmente costose. Gli autori si concentrano su sistemi in cui la soluzione è isolata e l'omotopia soddisfa specifiche condizioni di trasversalità e regolarità (Assunzione 1), garantendo l'esistenza di un'espansione in serie di Puiseux della curva di soluzione.

Metodologia

L'approccio proposto, denominato Arclength Endgame, combina tecniche di continuazione di pseudo-lunghezza d'arco con la stima dei parametri della serie di Puiseux. Il metodo è diviso in due fasi: una fase di predizione e una fase di correzione.

1. Fase di Predizione (Predictor Phase)

L'obiettivo è stimare i termini principali della serie di Puiseux $z(t) = z^* + \sum a_j t^{k_j/c}$ per predire la soluzione a $t=0$ (o un $t$ piccolo).

• Stima degli Esponenti: Gli autori introducono un nuovo metodo, cRATIO, per stimare il rapporto dell'esponente frazionario principale $k_1/c$. Questo metodo utilizza il rapporto delle norme $\|t \dot{z}(t) - t_1 \dot{z}(t_1)\| / \|z(t) - z(t_1)\|$, che converge a $k_1/c$ quando $t \to 0$. Lo confrontano con metodi esistenti come cSORT (tentativo ed errore) e cLOG (campionamento di sequenze geometriche), rilevando la stabilità empirica di cRATIO.
• Stima di Ordine Superiore: Per sistemi che richiedono un'accuratezza di ordine superiore, il documento propone un metodo ricorsivo per stimare i successivi rapporti $k_i/c$ (per $i \ge 2$) applicando la logica di stima di $k_1/c$ a funzioni trasformate derivate dalla serie originale.
• Stima dei Coefficienti: Gli autori presentano un nuovo schema per stimare i coefficienti $a_{k_i}$ utilizzando l'inversione di una matrice di Vandermonde scalata. A differenza dell'interpolazione di Hermite classica che assume esponenti densi $(1, 2, 3)$, questo metodo accoglie esponenti sparsi e utilizza derivate di ordine superiore (approssimate tramite Differenze Finite di Hermite per evitare il calcolo dell'Hessiana).

2. Fase di Correzione (Corrector Phase)

Una volta stimato un punto di predizione $\hat{x}$, il sistema viene aumentato per ripristinare la non-singolarità per il metodo di Newton.

• Corank-1 ($\kappa=1$): Il sistema $h(x)=0$ viene aumentato con una singola equazione lineare $q \cdot (x - \hat{x}) = 0$, dove $q$ è un vettore ortogonale alla tangente della curva di soluzione (derivato dallo spazio nullo del Jacobiano aumentato $[h_z, h_t]$). Ciò crea un sistema quadrato ben condizionato risolvibile con il metodo di Newton.
• Corank $\kappa \ge 2$ (Lifted Arclength Endgame): Per corank più elevati, il metodo introduce $\kappa-1$ variabili ausiliarie e $\kappa$ iperpiani per regolarizzare il sistema. Poiché il punto risultante potrebbe non trovarsi sull'omotopia originale, gli autori propongono una strategia "lifted" (sollevata): l'omotopia viene dinamicamente resettata a un'omotopia di Newton $h_v(z, t) = f(z) - t f(v)$, dove $v$ è la soluzione raffinata. Ciò consente di continuare a raffinare la soluzione vicino alla singolarità.

Contributi Chiave

1. Arclength Endgame per Corank-1: Gli autori introducono un nuovo algoritmo per sistemi di corank-1 che raggiunge una convergenza superlineare in un vicinato della radice singolare. Fondamentalmente, questo metodo si basa solo sulle valutazioni del sistema e del suo Jacobiano, evitando il calcolo delle derivate di ordine superiore richieste dai metodi di deflazione con convergenza superlineare provata.
2. Lifted Arclength Endgame: Un'estensione euristica per sistemi con corank $\kappa \ge 2$. Sebbene non siano fornite prove formali di convergenza per questo caso, i risultati sperimentali dimostrano un promettente comportamento di convergenza superlineare.
3. Miglioramento della Stima della Serie di Puiseux:
   • Un nuovo metodo stabile (cRATIO) per stimare l'esponente frazionario principale $k_1/c$.
   • Un nuovo framework ricorsivo per stimare gli esponenti frazionari di ordine superiore ($k_i/c$ per $i \ge 2$) e i loro coefficienti associati, consentendo predittori di ordine superiore per serie di Puiseux sparse.
4. Garanzie Teoriche: Il documento fornisce prove formali (Teorema 1 e Corollario 2) che stabiliscono il tasso di convergenza superlineare per il caso corank-1, dipendente dall'accuratezza della stima dell'esponente e dal vicinato della radice.

Risultati

Gli autori confrontano i loro metodi (AL per corank-1, LAL per corank $\ge 2$) con l'endgame classico della serie di potenze (CLASSIC) utilizzando una suite di sistemi polinomiali, inclusi i sistemi Griewank-Osborne, Lecerf e Caprasse, nonché sistemi generati su misura con corank e numeri di winding specifici.

• Convergenza: I grafici (Figure 1–12) illustrano il residuo di tracciamento $\log_{10} \|f(z)\|$ rispetto al numero cumulativo di inversioni di matrici. I metodi proposti dimostrano generalmente una convergenza più rapida (discesa più ripida nel residuo) e la capacità di raggiungere residui più profondi con meno inversioni di matrici rispetto all'approccio classico, particolarmente nel regime di endgame profondo.
• Stabilità: Il confronto tra i metodi di stima degli esponenti (Figure 13–18) suggerisce che il metodo cRATIO proposto offre una stabilità competitiva o superiore rispetto a cSORT e cLOG in varie istanze di test.
• Robustezza: L'approccio lifted (LAL) gestisce con successo sistemi con corank più elevati dove gli endgame standard tipicamente falliscono o si bloccano, mantenendo la convergenza attraverso il reset dinamico dell'omotopia.

Significato e Rivendicazioni

Il documento sostiene che l'Arclength Endgame rappresenti un avanzamento significativo nel calcolo di soluzioni singolari, raggiungendo una convergenza superlineare senza l'onere computazionale delle tecniche di deflazione (che richiedono derivate di ordine superiore e possono aumentare significativamente la dimensione del sistema).

Gli autori sottolineano che il loro metodo è "consapevole dell'endgame" (endgame-aware), utilizzando esplicitamente le proprietà geometriche della curva di soluzione (serie di Puiseux) per regolarizzare il sistema. Posizionano il lavoro come un miglioramento pratico per la Geometria Algebrica Numerica, fornendo un metodo che è sia teoricamente fondato (per il corank-1) che empiricamente efficace (per corank più elevati), pur basandosi su valutazioni standard di funzione e Jacobiano. Il lavoro non pretende di risolvere universalmente tutte le singolarità, ma mira specificamente al regime di radici singolari isolate sotto assunzioni di omotopia generiche.