Accelerating a restarted Krylov method for matrix functions with randomization

Titel: Versnelling van een herstartte Krylov-methode voor matrixfuncties met randomisatie

Auteurs: Nicolas L. Guidotti, Per-Gunnar Martinsson, Juan A. Acebrón, José Monteiro.

---

1. Het Probleem

In veel wetenschappelijke toepassingen, zoals het oplossen van partiële differentiaalvergelijkingen (PDE's), netwerkanalyse en kwantumchromodynamica, is het nodig om de werking van een matrixfunctie $f(A)$ op een vector $b$ te evalueren (d.w.z. $f(A)b$). Voor grote matrices is het expliciet vormen van $f(A)$ onhaalbaar; daarom worden vaak Krylov-onderruimte-methoden gebruikt.

De klassieke aanpak (zoals de Arnoldi-iteratie) bouwt een orthogonale basis op voor de Krylov-onderruimte. Dit kent echter twee grote nadelen:

1. Geheugeneisen: De volledige basis moet in het geheugen worden opgeslagen, wat de probleemgrootte beperkt.
2. Rekenkosten: Voor niet-Hermitische matrices groeit de kost van orthogonalisatie kwadratisch met de grootte van de basis ($O(m^2n)$).

Om dit op te lossen, worden herstartte Krylov-methoden gebruikt, waarbij de iteratie na een vast aantal stappen ($m$) wordt herstart met een nieuwe startvector. Hoewel dit het geheugengebruik beperkt, leidt herstarten vaak tot een tragere convergentie, stagnatie of zelfs divergentie.

2. Methodologie

Het artikel introduceert een nieuwe versnellingsmethode die randomisatie (random sketching) combineert met herstartte Krylov-methoden.

• Randomized Arnoldi (RGS): In plaats van de klassieke Arnoldi-iteratie met volledige orthogonalisatie, gebruiken de auteurs een Randomized Gram-Schmidt (RGS) proces. Hierbij wordt een "sketch" (een gereduceerde projectie) van de basisvectoren berekend met behulp van een willekeurige projectiematrix $S$ (vaak een dunne tekenmatrix).
• Orthogonalisatie in de Sketch: De orthogonalisatie vindt plaats op de kleine gesketste matrix $SW_m$ in plaats van op de volledige basis $W_m$. Dit zorgt ervoor dat de basis $W_m$ goed geconditioneerd blijft zonder de hoge kosten van volledige orthogonalisatie.
• Herstartprocedure: De methode past een herstartstrategie toe waarbij de schatting van $f(A)b$ wordt bijgewerkt aan het einde van elke cyclus. De auteurs tonen aan dat de blokgewijze structuur van de gereduceerde Hessenberg-matrix $R_m$ het mogelijk maakt om de oplossing te updaten zonder de basis van de vorige cyclus te hoeven opslaan.
• Vergelijking: De methode wordt vergeleken met klassieke Arnoldi, incomplete orthogonalisatie, en eerdere gerandomiseerde benaderingen zoals sFOM (sketched FOM) en rand-ls.

3. Belangrijkste Bijdragen

1. Nieuwe Versnellingstechniek: De ontwikkeling van een herstartte Krylov-methode die gebruikmaakt van random sketching om een goed geconditioneerde, niet-orthogonale basis te construeren.
2. Verbeterde Convergentie: Het aantonen dat randomisatie niet alleen de rekenkosten verlaagt, maar in sommige gevallen de convergentiesnelheid van herstartte methoden daadwerkelijk verbetert ten opzichte van de klassieke methode.
3. Analyse van Ill-Conditioned Problemen: Een uitgebreide studie van het gedrag van gerandomiseerde methoden op zeer grote, slecht geconditioneerde matrices (zoals die voortkomen uit FEM-discretisaties van PDE's en graf-Laplacianen), waar eerdere studies beperkt waren tot goed geconditioneerde problemen.
4. Schalbaarheid: Het aantonen dat randomisatie geen negatief effect heeft op de schaalbaarheid van de methode over meerdere CPU-kernen.

4. Resultaten en Experimenten

De auteurs hebben hun methode getest op drie verschillende scenario's:

• Convectie-Diffusie (3D PDE):

  • De gerandomiseerde herstartmethode (restart-rand) convergerde aanzienlijk sneller dan de klassieke herstartmethode (restart), vooral bij brede spectra.
  • De randomisatie verbrak het "discrete" gedrag van de Ritz-waarden (eigenwaardenbenaderingen) dat vaak optreedt bij herstarten, wat leidde tot een betere dekking van het spectrum.
  • Bij een lage dichtheid van de sketch-matrix ($\zeta=1$) was de methode stabiel en snel.

• Circulaire Membraan (Oscillerend Probleem):

  • Bij dit oscillerende probleem vertoonde de klassieke sFOM-methode instabiliteit en divergentie.
  • De voorgestelde restart-rand methode bleef stabiel en bereikte een hoge nauwkeurigheid, hoewel de convergentie in de eerste cycli wat onregelmatig was.

• Graf-Laplacianen (Netwerkanalyse):

  • Getest op grote netwerken (Kronecker, Orkut, UK-2002).
  • Voor netwerken met een breed spectrum (Kronecker, Orkut) was restart-rand sneller dan de klassieke herstartmethode vanwege een betere verdeling van de Ritz-waarden.
  • Voor netwerken met een smal spectrum (UK-2002) was de gerandomiseerde methode zonder herstart (rand) zelfs sneller dan de herstartmethoden, mede door lagere orthogonalisatiekosten.

Prestaties:

• Snelheid: De gerandomiseerde Arnoldi-iteratie was tot 2,92 keer sneller dan de klassieke Arnoldi-iteratie voor niet-herstartte methoden.
• Herstartte methoden: In complexe scenario's was restart-rand tot 1,56 keer sneller dan de klassieke herstartmethode, terwijl het tegelijkertijd een hogere nauwkeurigheid bereikte.
• Geheugen: Herstartmethoden verbruiken aanzienlijk minder geheugen dan volledige methoden (bijv. 11,1 GB vs 18,8 GB voor het Kronecker-netwerk).
• Parallelle schaalbaarheid: De randomisatie heeft geen negatief effect op de strong scaling; de parallelle efficiëntie blijft vergelijkbaar met klassieke methoden.

5. Betekenis en Conclusie

Dit artikel biedt een robuuste oplossing voor het evalueren van matrixfuncties op zeer grote en slecht geconditioneerde systemen. De kernboodschap is dat randomisatie niet alleen een techniek is om kosten te besparen door het verminderen van orthogonalisatie, maar dat het ook de kwaliteit van de convergentie kan verbeteren bij herstartte methoden.

De methode overwint de beperkingen van eerdere gerandomiseerde benaderingen (zoals sFOM) die instabiel bleken bij grote, ill-conditioned problemen. Door de Ritz-waarden beter te spreiden over het spectrum, voorkomt de methode stagnatie die vaak optreedt bij klassieke herstarttechnieken. Dit maakt de methode uiterst waardevol voor toepassingen in de natuurkunde, engineering en datawetenschap waar grote, schaarse matrices een centrale rol spelen.