Reducing Internal State in Eigenvalue-Only Divide-and-Conquer Tridiagonal Eigensolvers

Riepilogo Tecnico: Riduzione dello Stato Interno nei Risolutori di Autovalori Tridiagonali Divide-and-Conquer Basati Solo su Autovalori

1. Enunciato del Problema

La decomposizione agli autovalori (EVD) di matrici simmetriche è un'operazione fondamentale nel calcolo scientifico. Sebbene la pipeline standard riduca una matrice simmetrica densa a una forma tridiagonale $T$ prima della risoluzione, la scelta del risolutore per la fase tridiagonale dipende fortemente dalla necessità degli autovettori.

• Metodi QR/QL: Per il calcolo degli autovalori esclusivamente, le librerie standard (ad esempio xSTERF di LAPACK) utilizzano di default algoritmi basati su QR. Questi sono efficienti in termini di memoria ($O(n)$ di spazio) ma intrinsecamente sequenziali, limitando le prestazioni sulle moderne CPU multicore e GPU.
• Divide-and-Conquer (D&C): D&C offre un parallelismo e una velocità superiori per sistemi di grandi dimensioni. Tuttavia, le implementazioni convenzionali di D&C (ad esempio xSTEDC di LAPACK) mantengono un footprint di memoria quadratico ($O(n^2)$) anche quando sono richiesti solo gli autovalori. Questo perché l'algoritmo deve memorizzare o "riprodurre" matrici di autovettori densi per costruire i vettori di aggiornamento di rango uno necessari per fondere i sottoproblemi.
• Il Divario: Le formulazioni esistenti di "ripetizione pigra" (lazy-replay) riducono le moltiplicazioni eager non necessarie ma mantengono ancora il footprint di memoria quadratico delle trasformazioni ortogonali accumulate. Ciò costringe le librerie a ricorrere di default a metodi QR più lenti per compiti basati solo su autovalori per evitare l'esaurimento della memoria, in particolare sulle GPU dove la memoria del dispositivo è vincolata.

2. Metodologia: D&C a Riga di Confine (Boundary-Row)

Il documento propone un algoritmo D&C a Riga di Confine (BR) che altera fondamentalmente la dipendenza dei dati del processo D&C basato solo su autovalori.

• Osservazione Principale: Il passo di fusione in D&C risolve un'equazione secolare per una matrice diagonale più rango uno. Il vettore di aggiornamento di rango uno $v$ dipende solo dall'ultima riga della matrice degli autovettori del figlio sinistro e dalla prima riga della matrice degli autovettori del figlio destro. Non richiede le intere matrici degli autovettori.
• Invariante Algoritmico: Invece di propagare intere matrici di autovettori o riprodurre storie di trasformazioni dense, l'algoritmo BR propaga solo le righe di confine (la prima e l'ultima riga dei blocchi di autovettori) richieste dalle fusioni degli antenati.
• Propagazione dello Stato:
  • Ad ogni nodo nell'albero di ricorsione, l'algoritmo calcola le righe di confine del blocco di autovettori del genitore direttamente dalle righe di confine dei figli e dall'autovettore secolare locale.
  • Ciò è ottenuto tramite aggiornamenti di righe selezionate: $(Q_{parent})_{\sigma} = (Q_{child})_{\sigma} S$, dove $\sigma$ rappresenta le specifiche righe di confine necessarie.
  • L'algoritmo evita di materializzare i blocchi completi di autovettori seculari $K \times K$ o le matrici di trasformazione dense.
• Correttezza e Stabilità:
  • Correttezza: Il Teorema 3.3 dimostra che, in aritmetica esatta, BR costruisce gli stessi problemi seculari esatti e restituisce autovalori identici rispetto al D&C convenzionale.
  • Stabilità: La propagazione dell'errore è condizionata dalle interfacce di stabilità locale standard (risolutori di equazioni seculari e gestione della deflazione). La propagazione delle righe di confine non amplifica gli errori oltre la norma della concatenazione.

3. Analisi della Complessità

• Complessità Spaziale: Il miglioramento più significativo riguarda l'archiviazione ausiliaria.
  • D&C Convenzionale: $O(n^2)$ di spazio di lavoro reale per lo stato denso degli autovettori/ripetizione.
  • D&C BR: $O(n)$ di spazio di lavoro ausiliario. L'algoritmo memorizza solo array di poli, dati seculari compatti e le righe di confine selezionate.
• Complessità Temporale:
  • Il costo asintotico della risoluzione delle radici seculari rimane $O(n^2)$ nel caso peggiore (quando la deflazione è debole).
  • Tuttavia, BR elimina il costo $O(n^2)$ associato alla ricostruzione e materializzazione di blocchi densi locali di vettori seculari e metadati di ripetizione.
  • Il costo principale del percorso di fusione è ridotto di un fattore costante: $T_{BR}(n) \approx (2c_{sec} + 4)n^2$ rispetto a $T_{lazy}(n) \approx (2c_{sec} + 2c_{rep} + 8)n^2$.

4. Implementazione e Valutazione

Gli autori hanno implementato l'algoritmo sia su CPU (utilizzando OpenMP) che su GPU (CUDA), confrontandolo con baseline standard.

• Implementazione CPU:

  • È stato creato un driver privato in stile LAPACK (DSTEDC_DC_BR) per isolare la fase tridiagonale.
  • Risultati: Su un sistema Intel Xeon a 56 core, BR è stato significativamente più veloce della routine QR/QL standard (DSTERF), raggiungendo accelerazioni da 4.000x a 5.000x per $N=65.536$ su input casuali.
  • Rispetto al percorso interno D&C solo-valori di MKL (che utilizza memoria quadratica), BR è stato da 3,1x a 6,1x più veloce utilizzando ordini di grandezza meno memoria (ad esempio, 2,44 MiB contro 6,0 GiB per $N=16.384$).
  • BR è riuscito a eseguire su $N=134.000.000$, raggiungendo il limite di spazio di lavoro a 32 bit, mentre il percorso D&C interno ha fallito (OOM) a dimensioni molto più piccole.

• Implementazione GPU:

  • Implementato come kernel CUDA residente su una NVIDIA H100.
  • Risultati: Rispetto a cusolverDnXstedc di NVIDIA (modalità solo autovalori), il prototipo BR è stato da 1,74x a 5,73x più veloce su $N=49.152$.
  • Memoria: Lo spazio di lavoro di cuSOLVER è cresciuto quadraticamente, raggiungendo 54,0 GiB per $N=49.152$, mentre il prototipo BR ha utilizzato circa 1,5 GiB.

5. Contributi Chiave

1. Identificazione della Dipendenza: Il documento identifica che il D&C basato solo su autovalori richiede solo righe di confine, non intere matrici di autovettori, per eseguire le fusioni.
2. Algoritmo a Riga di Confine: Un nuovo algoritmo che propaga solo queste righe di confine, riducendo la memoria ausiliaria da $O(n^2)$ a $O(n)$.
3. Garanzie Teoriche: Prove di correttezza (autovalori identici al D&C convenzionale) e stabilità dell'errore condizionata.
4. Implementazioni ad Alte Prestazioni: Prototipi CPU e GPU che espongono il parallelismo D&C senza la penalità di memoria quadratica.
5. Validazione Empirica: Estesi benchmark che dimostrano come BR renda il D&C pratico per carichi di lavoro basati solo su autovalori vincolati dalla memoria, superando sia QR/QL che le routine D&C interne esistenti in velocità e scalabilità.

6. Significato e Affermazioni

Il documento afferma che la variante D&C basata solo su autovalori non dovrebbe essere trattata come un algoritmo di autovettori degenerato. Sfruttando la dipendenza dai dati più ridotta (solo righe di confine), è possibile mantenere la struttura di fusione parallela di D&C eliminando la ragione principale per cui le librerie ricorrono ai metodi QR.

• Affermazioni Modeste: Gli autori dichiarano esplicitamente che BR non è un risolutore di autovettori subquadratico universale. Nei casi con deflazione debole (ad esempio, spettri di Toeplitz o raggruppati), il lavoro di risoluzione delle radici seculari rimane $O(n^2)$, e l'accelerazione rispetto a QR è limitata a fattori costanti e benefici di threading.
• Valore Primario: Il significato risiede nel rendere il punto di progettazione D&C disponibile ai carichi di lavoro basati solo su autovalori senza trasportare lo stato completo degli autovettori. Ciò è particolarmente critico per il calcolo GPU, dove lo spazio di lavoro quadratico può impedire che problemi di grandi dimensioni entrino interamente nella memoria del dispositivo. Il lavoro colma il divario tra l'efficienza di memoria di QR e le prestazioni parallele di D&C.