Perturbation Analysis for Preconditioned Normal Equations in Mixed Precision

Sintesi Tecnica: Analisi delle Perturbazioni per Equazioni Normali Precondizionate in Precisione Mista

1. Il Problema

Il lavoro affronta la risoluzione di problemi ai minimi quadrati lineari $\min_x \|Ax - b\|_2$, dove $A \in \mathbb{R}^{m \times n}$ è una matrice a rango completo ($rank(A)=n$).

• Sfida principale: Le equazioni normali standard $A^T A x = A^T b$ sono spesso sconsigliate perché il numero di condizione della matrice del sistema diventa $\kappa(A^T A) = \kappa(A)^2$. Se $\kappa(A)$ è elevato (es. $> 10^7$), le equazioni normali diventano numericamente singolari in doppia precisione (IEEE 754).
• Contesto attuale: L'uso di precondizionatori randomizzati (come quelli basati su sketching) può migliorare il condizionamento di $A$, rendendo le equazioni normali ben condizionate. Tuttavia, calcolare questi precondizionatori in doppia precisione è costoso.
• Domanda di ricerca: È possibile calcolare il precondizionatore in precisione inferiore (es. singola o metà precisione) per accelerare il calcolo, mantenendo un'accuratezza della soluzione comparabile a quella ottenuta con metodi diretti stabili (come mldivide di MATLAB)? Inoltre, come si comportano le nuove stime di errore (bound) in questo contesto di precisione mista?

2. Metodologia

Gli autori analizzano quattro varianti di equazioni normali precondizionate, derivando nuovi limiti di perturbazione che tengono conto degli errori introdotti dal calcolo del precondizionatore in bassa precisione.

Le equazioni analizzate sono:

1. PNE (Preconditioned Normal Equations): $A_p^T A_p y = A_p^T b$, dove $A_p = A R_s^{-1}$. Si risolve per $y$ e poi si recupera $x = R_s y$.
2. HPNE (Half-Preconditioned Normal Equations): $A_p^T A x = A_p^T b$. Si evita la risoluzione del sistema triangolare finale, ma il sistema risultante è non simmetrico.
3. Equazioni Seminormali: $R^T R x = A^T b$ (dove $A=QR$).
4. Equazioni "Not-Normal": $B^T A x = B^T b$, dove $B$ ha lo stesso spazio colonna di $A$.

Approccio Teorico:

• Si estendono i risultati esistenti (da [12]) al caso di precisione mista, dove il precondizionatore $R_s$ è calcolato con un errore di arrotondamento significativo rispetto alla precisione di lavoro principale.
• Vengono derivati nuovi limiti di perturbazione (Theorems 3.2 e 4.2) che mostrano come l'errore relativo dipenda dal residuo ai minimi quadrati e dal numero di condizione del precondizionatore, ma solo debolmente dalla precisione con cui è stato calcolato il precondizionatore stesso.
• Si dimostra che, se il precondizionatore è efficace ($\kappa(A_p) \lesssim 10$), le equazioni precondizionate sono ben condizionate quanto la matrice originale $A$, indipendentemente dalla precisione di calcolo del precondizionatore (purché non singolare).

Approccio Algoritmico:

• Viene proposto un algoritmo (Algorithm 6.1) per la selezione automatica della precisione.
• Si stima il numero di condizione di $A$ in singola precisione. In base a questa stima:
  • Se $\kappa(A)$ è basso, si usa la metà precisione (half precision).
  • Se $\kappa(A)$ è medio, si usa la singola precisione.
  • Se $\kappa(A)$ è alto, si usa la doppia precisione.
• Il precondizionatore viene calcolato in bassa precisione, poi promosso a doppia precisione prima di essere applicato alla matrice $A$ per garantire la stabilità.
• Viene utilizzato uno sketching randomizzato (trasformata trigonometrica campionata) per costruire il precondizionatore in modo efficiente e parallelizzabile.

3. Contributi Chiave

1. Nuovi Limiti di Perturbazione Realistici: I nuovi bound per PNE e HPNE (Teoremi 3.2 e 4.2) sono informativi anche in precisione mista. A differenza dei bound precedenti, non dipendono in modo dominante dall'errore del precondizionatore, ma mostrano una dipendenza cruciale dal residuo ai minimi quadrati ($\|Ax - b\|$).
2. Analisi delle Equazioni Seminormali e "Not-Normal":
   • Si dimostra che le equazioni seminormali non offrono un vantaggio di condizionamento rispetto alle normali equazioni (dipendono da $\kappa(A)^2$).
   • Le equazioni "not-normal" sono ben condizionate solo quando sono vicine alle HPNE.
3. Selezione Automatica della Precisione: Un metodo pratico per scegliere la precisione del precondizionatore basandosi su una stima rapida del numero di condizione, ottimizzando il compromesso tra velocità e accuratezza.
4. Implementazione GPU: Dimostrazione pratica dell'efficienza su GPU NVIDIA H100, sfruttando la parallelizzazione massiccia per il calcolo dello sketch e la risoluzione in precisione mista.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su matrici "tall and skinny" ($m \approx 10^5, n \le 2000$) con numeri di condizione fino a $10^{10}$.

• Validità dei Bound:
  • I nuovi bound (Teoremi 3.2 e 4.2) riflettono accuratamente il comportamento dell'errore numerico, specialmente in precisione mista.
  • I vecchi bound (basati su [12]) sovrastimavano drasticamente l'errore quando il precondizionatore era calcolato in bassa precisione, risultando poco informativi.
• Accuratezza:
  • Per residui ai minimi quadrati sufficientemente grandi, le soluzioni ottenute con PNE e HPNE in precisione mista sono comparabili a quelle di mldivide di MATLAB.
  • Per residui molto piccoli, l'errore relativo può essere leggermente superiore (fino a 100 volte) rispetto a mldivide, ma rimane accettabile per molte applicazioni.
• Prestazioni su GPU (NVIDIA H100):
  • L'approccio in precisione mista offre un speedup moderato rispetto alla risoluzione in doppia precisione pura, poiché la parte dominante del costo computazionale rimane la risoluzione del sistema lineare (che è in doppia precisione).
  • Tuttavia, il beneficio principale è la riduzione dell'footprint di memoria (memoria HBM3) e la possibilità di gestire problemi più grandi o di ridurre i tempi di trasferimento dati.
  • Per $n \le 2000$, i metodi PNE/HPNE (sia misti che doppi) sono più veloci dei solver basati su QR standard.

5. Significato e Implicazioni

Questo lavoro è significativo per l'alta performance computing (HPC) e l'apprendimento automatico su larga scala per i seguenti motivi:

• Robustezza Teorica: Fornisce una giustificazione matematica solida per l'uso di precondizionatori calcolati in bassa precisione, un'area dove spesso si faceva affidamento solo su evidenze empiriche.
• Efficienza Pratica: Dimostra che è possibile ottenere soluzioni di alta qualità per problemi mal condizionati sfruttando l'hardware moderno (GPU) e le precisioni ridotte, senza sacrificare la stabilità numerica.
• Guida alla Scelta: L'algoritmo di selezione automatica della precisione offre una strategia pratica per gli ingegneri che devono bilanciare velocità e accuratezza in ambienti eterogenei.
• Limiti Chiari: Identifica chiaramente che l'accuratezza finale dipende dal residuo del problema, non solo dal condizionamento della matrice, fornendo un criterio di arresto o di valutazione più realistico per gli algoritmi iterativi o precondizionati.

In sintesi, il paper stabilisce che le equazioni normali precondizionate, calcolate con precondizionatori in precisione mista, sono un metodo robusto, efficiente e teoricamente fondato per risolvere problemi ai minimi quadrati su larga scala, specialmente su architetture GPU.