Estimating the condition number of Chebyshev filtered vectors with application to the ChASE library

Dit artikel presenteert een methode om de voorwaardegetallen van door Chebyshev-gefilterde vectoren nauwkeurig en goedkoop te schatten, waarmee in de ChASE-bibliotheek een efficiëntere keuze voor QR-factorisatie-algoritmen mogelijk wordt gemaakt zonder in te leveren op nauwkeurigheid.

De kern

Stel je voor dat je een gigantische, rommelige bibliotheek hebt (deze bibliotheek is een wiskundig probleem genaamd een "eigenwaardeprobleem"). Je wilt niet alle boeken lezen, maar alleen de 100 meest waardevolle boeken vinden die ergens in de diepte van de collectie liggen.

Dit is precies wat de ChASE-software doet voor wetenschappers die complexe materialen bestuderen, zoals nieuwe batterijen of zonnepanelen. Ze moeten uit een zee van data de belangrijkste patronen (de "eigenvectoren") halen.

Hier is hoe dit papier een oplossing biedt voor een specifiek probleem in die software, vertaald naar alledaags taal:

1. Het Probleem: De "Gedrukte" Boekenstapel

De ChASE-software werkt in rondes. In elke ronde pakt het een stapel boeken (vectoren) en gebruikt een slimme filter (de Chebyshev-filter) om de onbelangrijke boeken weg te gooien en de belangrijke boeken eruit te halen.

Na deze filterbeurt is de stapel boeken echter een beetje in de war. De boeken liggen nu heel dicht op elkaar, ze overlappen en zijn niet meer netjes gesorteerd. Om ze weer bruikbaar te maken, moet de software ze orthonormaliseren.

• In het Nederlands: Dit betekent dat ze de boeken moeten "opfrissen" zodat ze weer perfect recht en los van elkaar staan, klaar voor de volgende ronde.

Vroeger deed de software dit met de Householder QR-methode. Dit is als een zeer zorgzame bibliothecaris die elk boek één voor één perfect rechtzet met een liniaal. Het is heel nauwkeurig, maar het is ook traag. Het kost veel tijd en energie, vooral als je duizenden boeken tegelijk hebt.

2. Het Snellere Alternatief: De "Snelwerkende" Methode

Er bestaat een snellere methode, genaamd CholeskyQR. Dit is als een team van robots dat de boeken in één keer in een rechte rij duwt. Het is enorm snel en past perfect op moderne computers (zoals supercomputers met duizenden processors).

Maar hier zit de addertje onder het gras:
Deze robots zijn niet zo nauwkeurig als de bibliothecaris. Als de stapel boeken al te rommelig is (in wiskundetaal: als de "conditienummer" te hoog is), dan maken de robots een fout. De boeken staan dan niet meer perfect recht, en de hele berekening kan mislukken.

3. De Oplossing: Een Slimme Schatting

De auteurs van dit papier hebben een slimme truc bedacht. Ze zeggen: "Laten we niet eerst de hele stapel boeken tellen en meten (dat duurt te lang), maar laten we een slimme schatting maken van hoe rommelig de stapel is."

Ze hebben een formule bedacht die kijkt naar:

1. Hoeveel de filter heeft gedaan.
2. Hoe ver de boeken al op hun plek zijn gekomen.

Met deze formule kunnen ze schattingen maken van de "rommeligheid" (het conditienummer) in een flits.

4. De Dynamische Keuze: De "Verkeersregelaar"

Op basis van deze snelle schatting kiest de software nu slim welke methode ze gebruiken:

• Scenario A: De stapel is netjes.
  De schatting zegt: "Geen probleem, de boeken liggen prima."
  👉 Actie: De software gebruikt de snelle robots (CholeskyQR). Resultaat: Alles gaat razendsnel.

• Scenario B: De stapel is erg rommelig.
  De schatting zegt: "Oeps, hier is het te chaotisch, de robots maken fouten."
  👉 Actie: De software schakelt over naar de zorgzame bibliothecaris (Householder QR) of een iets robuustere versie van de robots. Resultaat: Het duurt iets langer, maar de resultaten blijven 100% betrouwbaar.

• Scenario C: Ergens tussenin.
  De software kiest een tussenversie van de robots die twee keer over de stapel gaat om zekerheid te krijgen.

Waarom is dit belangrijk?

Vroeger moest de software altijd de "zorgzame bibliothecaris" gebruiken, omdat ze niet wisten of de stapel rommelig was of niet. Dat was als een auto die altijd op de laagste versnelling rijdt, uit angst dat de weg glad is.

Met deze nieuwe methode rijdt de software nu als een sportauto met een slim navigatiesysteem:

• Op een rechte, droge weg (stabiele situatie) gaat hij vol gas (snelle methode).
• Bij een gladde weg of bocht (rommelige situatie) schakelt hij automatisch over naar veilige rijmodi (stabiele methode).

Het resultaat: De ChASE-bibliotheek wordt veel sneller (tot wel 6 keer sneller in sommige gevallen) zonder dat de nauwkeurigheid in gevaar komt. Wetenschappers kunnen dus sneller nieuwe materialen ontwerpen en ontdekken.

Kortom: Ze hebben een slimme "waarschuwingslamp" bedacht die de software vertelt wanneer ze kunnen racen en wanneer ze voorzichtig moeten zijn, zodat ze altijd op de snelste manier mogelijk hun werk doen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Estimating the Condition Number of Chebyshev Filtered Vectors with Application to the ChASE Library" in het Nederlands.

Titel: Schatting van de conditienummer van Chebyshev-gefilterde vectoren met toepassing op de ChASE-bibliotheek

Auteurs: Edoardo Di Napoli en Xinzhe Wu
Context: Numerieke lineaire algebra, High-Performance Computing (HPC), eigensolvers.

---

1. Het Probleem

Chebyshev-gefilterde subspace-iteratie is een gevestigde en krachtige algoritme voor het oplossen van grote, symmetrische (of Hermitische) algebraïsche eigenwaardeproblemen, met name in toepassingen zoals elektronische structuurtheorie. Het algoritme bestaat uit twee hoofdcomponenten:

1. Filterstap: Het toepassen van een Chebyshev-polynoom om de componenten van de zoekruimte die corresponderen met de gewenste eigenwaarden te versterken.
2. Orthogonalisatiestap: Het orthonormaliseren van de gefilterde vectoren via een QR-factorisatie, gevolgd door een Rayleigh-Ritz-projectie.

De uitdaging:
De matrix van gefilterde vectoren heeft vaak een onbekend en hoog conditienummer ($\kappa_2$). Dit conditienummer is cruciaal voor de keuze van het QR-factorisatie-algoritme:

• Householder QR: Biedt uitstekende numerieke stabiliteit maar is computatief zwaar en communicatie-intensief (vooral op GPU's en gedistribueerde systemen), wat het een performance-bottleneck maakt.
• CholeskyQR: Is zeer efficiënt en rijk aan BLAS-3 operaties (goed voor parallelisme), maar is numeriek instabiel als het conditienummer te hoog is (verlies van orthogonaliteit).
• Varianten: Er bestaan robuustere varianten zoals CholeskyQR2 en shifted CholeskyQR2 (s-CholeskyQR2), maar deze zijn alleen veilig toepasbaar binnen specifieke bereiken van het conditienummer.

Het probleem is dat het direct berekenen van het exacte conditienummer van de gefilterde vectoren te duur is (te veel FLOPs), waardoor de performance-winst van CholeskyQR teniet wordt gedaan. Er is dus behoefte aan een goedkope, nauwkeurige schatting van dit conditienummer om dynamisch het juiste QR-algoritme te kiezen.

---

2. Methodologie

De auteurs ontwikkelen een theoretisch kader en een praktische schattingsmethode gebaseerd op de spectrale eigenschappen van de Chebyshev-filtering.

Theoretische Analyse:

• Ze analyseren de spectrale decompositie van de matrix $V^{(i)}$ na toepassing van de Chebyshev-polynoom $p_m(A)$.
• Ze definiëren een convergentieverhouding $|\rho_a|$ voor elke eigenwaarde buiten het gewenste interval. Hoe verder een eigenwaarde van het filterinterval ligt, hoe sneller de bijbehorende component wordt onderdrukt.
• Ze leiden een bovengrens af voor het conditienummer $\kappa_2(V^{(i)})$ gebaseerd op deze convergentieverhoudingen en de graad van het polynoom ($m$).
  • Voor een uniforme graad $m$: $\kappa_2 \lesssim \eta |\rho_1|^m$.
  • Voor geoptimaliseerde graad (verschillende $m$ per vector): De exponent wordt vervangen door de hoogste graad.
  • Voor het geval van "locked" (geconvergeerde) vectoren: De formule wordt aangepast om rekening te houden met de reeds geconvergeerde deelruimte en de overige vectoren.

Dynamische Selectie (Algorithm 1.3):
Op basis van deze schatting ($\kappa_{est}$) implementeren ze een heuristiek in de ChASE-bibliotheek om het QR-algoritme dynamisch te kiezen:

• Laag conditienummer (< 20): Gebruik standaard CholeskyQR (snelst).
• Gemiddeld conditienummer: Gebruik CholeskyQR2 (twee iteraties voor stabiliteit).
• Hoog conditienummer (> $10^8$): Gebruik shifted CholeskyQR2 (voegt een verschuiving toe aan de Gram-matrix om stabiliteit te garanderen).
• Fail-safe: Als zelfs de verschuiving faalt, wordt er automatisch teruggeschakeld naar de stabiele Householder QR.

---

3. Belangrijkste Bijdragen

1. Analytische Bovengrens: Een rigoureuze afleiding van een bovengrens voor het conditienummer van Chebyshev-gefilterde vectoren, die alleen afhankelijk is van reeds bekende parameters (spectrale grenzen, Ritz-waarden, en polynoomgraden).
2. Kostenloze Schatting: Een methode om dit conditienummer te schatten zonder extra matrix-berekeningen, wat de performance-winst van CholeskyQR behoudt.
3. Dynamische QR-Selectie: Een implementatie in de ChASE-library die automatisch de meest efficiënte QR-variant kiest op basis van de geschatte stabiliteit, zonder de numerieke nauwkeurigheid te compromitteren.
4. Validatie: Uitgebreide numerieke tests op realistische problemen uit de materiaalkunde (DFT en Bethe-Salpeter vergelijkingen).

---

4. Resultaten

De methoden zijn getest op het JURECA-DC cluster (AMD EPYC CPU's, InfiniBand) met diverse matrices (FLEUR, FHI-aims, BSE UIUC).

• Nauwkeurigheid van de schatting: De geschatte conditienummers ($\kappa_{est}$) blijken consistent een bovengrens te vormen voor het werkelijke conditienummer ($\kappa_2$). In de meeste gevallen is de ratio tussen schatting en werkelijkheid kleiner dan 2.
• Performance Winst:
  • Het vervangen van Householder QR door de dynamisch geselecteerde CholeskyQR-varianten leidt tot een 2x tot 6x versnelling van de QR-stap zelf, afhankelijk van de probleemgrootte.
  • De totale tijd tot oplossing (Time-to-Solution) neemt af met 10% tot 20%.
  • Voor grote problemen (bijv. >2000 eigenparen) is de versnelling in de QR-stap het grootst (tot 6x).
• Numerieke Stabiliteit: Het aantal iteraties en het aantal matrix-vector vermenigvuldigingen (MatVecs) blijven identiek aan die van Householder QR. Dit bevestigt dat de numerieke stabiliteit en convergentiegedrag van ChASE niet worden aangetast.
• Strong Scaling: De CholeskyQR-varianten tonen betere parallelle schaalbaarheid binnen de communicatie-communicatoren dan Householder QR, vooral omdat ze minder synchronisatiepunten vereisen.

---

5. Betekenis en Conclusie

Dit werk lost een kritiek probleem op in moderne eigensolvers voor HPC: het vinden van de balans tussen numerieke stabiliteit en rekenperformance.

• Voor de ChASE-bibliotheek: De implementatie van deze schattingsmethode maakt ChASE robuuster en sneller, waardoor het beter geschikt is voor exascale computing en GPU-architecturen waar communicatie een bottleneck is.
• Algemene Impact: Het bewijst dat het mogelijk is om de stabiliteit van Householder QR te benaderen met de snelheid van CholeskyQR, mits men een betrouwbare, goedkope schatting van het conditienummer heeft. Dit opent de deur voor het gebruik van snellere, communicatie-vermijdende algoritmen in andere iteratieve methoden waar polynoomfiltering wordt gebruikt.

Kortom, de auteurs hebben een brug geslagen tussen theoretische numerieke analyse en praktische high-performance implementatie, waardoor de ChASE-library een significante stap voorwaarts maakt in efficiëntie zonder in te leveren op nauwkeurigheid.