LOBPCG

Lokaal optimaal blokkeergradiënt (Lobpcg) is een matrixvrije methode voor het vinden van de grootste (of kleinste) eigenwaarden en de daarbij behorende eigenvectoren van een symmetrische Gegeneraliseerd eigenwaardeprobleem

${\ displaystyle ax = \ lambda bx,}$

voor een bepaald paar ${\ displaystyle (a, b)}$ complex Hermitiaans of echt symmetrisch matrices, waar de matrix ${\ displaystyle b}$ wordt ook aangenomen positief gedefineerd.

Achtergrond

Kantorovich in 1948 stelde voor om het kleinste te berekenen eigenwaarde ${\ DisplayStyle \ Lambda _ {1}}$ van een symmetrische matrix ${\ displaystyle a}$ door steilste afdaling Een richting gebruiken ${\ displaystyle r = ax- \ lambda (x) x}$ van een geschaalde gradiënt van een Rayleigh quotiënt ${\ displaystyle \ lambda (x) = (x, ax)/(x, x)}$ in een scalair product ${\ displaystyle (x, y) = x'y}$, met de stapgrootte berekend door het Rayleigh -quotiënt in de lineaire spanwijdte van de vectoren ${\ displaystyle x}$ en ${\ DisplayStyle w}$, d.w.z. op een lokaal optimale manier.Samokish^[1] Voorgesteld om een voorwaarde ${\ displaystyle t}$ naar de resterende vector ${\ displaystyle r}$ Om de vooraf geconditioneerde richting te genereren ${\ displaystyle w = tr}$ en afgeleid asymptotisch, als ${\ displaystyle x}$ benadert de eigenvector, convergentiesnelheidsgrenzen. D'Yakonov suggereerde^[2] spectraal equivalent voorwaarde en afgeleide niet-asymptotische convergentiesnelheidsgrenzen.Blokkeer lokaal optimale meerstaps steilste afdaling voor eigenwaardeproblemen werd beschreven in.^[3] Lokale minimalisatie van het Rayleigh -quotiënt op de subruimte overspanning door de huidige benadering, de huidige rest en de vorige benadering, evenals de blokversie, verschenen erin.^[4] De vooraf geconditioneerde versie werd geanalyseerd in ^[5] en.^[6]

Hoofdkenmerken^[7]

• Matrixvrij, d.w.z. hoeft niet expliciet de coëfficiëntmatrix op te slaan, maar heeft geen toegang tot de matrix door matrix-vectorproducten te evalueren.
• Factorisatie-Vrij, d.w.z. vereist geen matrixontleding Zelfs voor een Gegeneraliseerd eigenwaardeprobleem.
• De kosten per iteratie en het geheugengebruik zijn concurrerend met die van de Lanczos -methode, het berekenen van een enkele extreme eigenpair van een symmetrische matrix.
• Lineaire convergentie is theoretisch gegarandeerd en praktisch waargenomen.
• Versnelde convergentie vanwege direct voorwaarde, in tegenstelling tot Lanczos -methode, inclusief variabel en niet-symmetrisch en vast en positief definitief voorwaarde.
• Maakt triviale opname van efficiënt mogelijk domeinontleding en multigrid Technieken via voorconditionering.
• Warm begint en berekent een benadering van de eigenvector bij elke iteratie.
• Meer numeriek stabiel in vergelijking met de Lanczos -methode, en kan werken in rekenkunde met een laag nauwkeurige computer.
• Gemakkelijk te implementeren, met veel versies verschenen al.
• Blokkering maakt het gebruik van zeer efficiënte matrix-matrix-bewerkingen, b.v. Blas 3.
• De blokgrootte kan worden afgestemd om de convergentiesnelheid versus computerkosten van orthogonalisaties in evenwicht te brengen en de Rayleigh-Ritz-methode bij elke iteratie.

Algoritme

Enkele vectorversie

Voorafleidingen: Gradiëntafkomst voor eigenwaardeproblemen

De methode voert een iteratief maximalisatie (of minimalisatie) van de gegeneraliseerde Rayleigh quotiënt

${\ displaystyle \ rho (x): = \ rho (a, b; x): = {\ frac {x^{t} ax} {x^{t} bx}},}$

wat resulteert in het vinden van de grootste (of kleinste) eigenpairs van ${\ displaystyle ax = \ lambda bx.}$

De richting van de steilste beklimming, die de gradiënt, van de gegeneraliseerde Rayleigh quotiënt is positief evenredig met de vector

${\ displaystyle r: = ax- \ rho (x) bx,}$

De eigenvector genoemd restant.Als een voorwaarde ${\ displaystyle t}$ is beschikbaar, het wordt toegepast op de rest en geeft de vector

${\ displaystyle w: = tr,}$

de voorgeconditioneerde residu genoemd.Zonder voorconditionering hebben we ons ingesteld${\ displaystyle t: = i}$ en dus ${\ displaystyle w: = r}$.Een iteratieve methode

${\ displaystyle x^{i+1}: = x^{i}+\ alpha^{i} t (ax^{i}-\ rho (x^{i}) bx^{i}),}$

of, kortom,

${\ displaystyle x^{i+1}: = x^{i}+\ alpha^{i} w^{i}, \,}$

${\ displayStyle w^{i}: = tr^{i}, \,}$

${\ displaystyle r^{i}: = ax^{i}-\ rho (x^{i}) bx^{i},}$

staat bekend als vooraf geconditioneerd steilste beklimming (of afdaling), waar de scalair${\ DisplayStyle \ Alpha ^{i}}$ wordt de stapgrootte genoemd.De optimale stapgrootte kan worden bepaald door het Rayleigh -quotiënt te maximaliseren, d.w.z.

${\ displaystyle x^{i+1}: = \ arg \ max _ {y \ in span \ {x^{i}, w^{i} \}}} \ rho (y)}$

(of ${\ displaystyle \ arg \ min}$ In het geval van minimaliseren), in welk geval de methode lokaal optimaal wordt genoemd.

Recidief op drie jaar

Om de convergentie van de lokaal optimale vooraf geconditioneerde steilste beklimming (of afkomst) drastisch te versnellen, kan één extra vector worden toegevoegd aan de twee-termijn Herstelrelatie Om het op drie termijn te maken:

${\ displaystyle x^{i+1}: = \ arg \ max _ {y \ in span \ {x^{i}, w^{i}, x^{i-1}}}} \ rho (y (y)}$

(gebruiken ${\ displaystyle \ arg \ min}$ In geval van minimaliseren).De maximalisatie/minimalisatie van het Rayleigh-quotiënt in een driedimensionale subruimte kan numeriek worden uitgevoerd door de Rayleigh -Ritz -methode.Meer vectoren toevoegen, zie b.v. Richardson extrapolatie, leidt niet tot aanzienlijke versnelling^[8] maar verhoogt de berekeningskosten, dus wordt over het algemeen niet aanbevolen.

Numerieke stabiliteitsverbeteringen

Naarmate de iteraties samenkomen, de vectoren ${\ displaystyle x^{i}}$ en ${\ displaystyle x^{i-1}}$ Bijna worden lineair afhankelijk, resulterend in een precisieverlies en het maken van de Rayleigh -Ritz -methode Numeriek onstabiel in aanwezigheid van afronde fouten.Het verlies van precisie kan worden vermeden door de vector te vervangen ${\ displaystyle x^{i-1}}$ met een vector ${\ displaystyle p^{i}}$, dat kan verder weg zijn van ${\ displaystyle x^{i}}$, op basis van de driedimensionale subruimte ${\ displaystyle span \ {x^{i}, w^{i}, x^{i-1} \}}$, terwijl de subruimte ongewijzigd blijft en vermijden orthogonalisatie of andere extra bewerkingen.^[8] Bovendien kan de orthogonalisering van de basis van de driedimensionale subruimte nodig zijn voor slecht geconditioneerd eigenwaarde problemen om de stabiliteit te verbeteren en de bereikbare nauwkeurigheid te bereiken.

Krylov subruimte analogen

Dit is een versie met één vector van de LOBPCG-methode-een van de mogelijke generalisatie van de vooraf aangelegd geconjugeerde gradiënt lineaire oplossers voor het geval van symmetrisch eigenwaarde problemen.^[8] Zelfs in het triviale geval ${\ displaystyle t = i}$ en ${\ displaystyle b = i}$ de resulterende benadering met ${\ DisplayStyle i> 3}$ zal verschillen van die verkregen door de Lanczos -algoritme, hoewel beide benaderingen tot hetzelfde zullen behoren Krylov subruimte.

Praktisch gebruiksscenario's

Extreme eenvoud en hoge efficiëntie van de enkele vectorversie van LOBPCG maken het aantrekkelijk voor eigenwaarde-gerelateerde toepassingen onder ernstige hardwarebeperkingen, variërend van spectrale clustering Basis realtime onregelmatigheidsdetectie via Grafiekpartitie op ingebed ASIC of FPGA het modelleren van fysieke fenomenen van recordcomplexiteit op exascale Top500 supercomputers.

Blokversie

Overzicht

Daaropvolgende eigenparen kunnen één voor één worden berekend via LOBPCG met één vector, aangevuld met een orthogonale deflatie of tegelijkertijd als een blok.In de vorige aanpak beïnvloeden de onnauwkeuringen in reeds berekende eigenvectoren additief de nauwkeurigheid van de vervolgens berekende eigenvectoren, waardoor de fout bij elke nieuwe berekening wordt vergroot.Verschillende bij benadering itereren eigenvectoren Samen op een blok op een lokaal optimale manier in de blokversie van de LOBPCG.^[8] maakt een snelle, nauwkeurige en robuuste berekening van eigenvectoren mogelijk, inclusief die welke overeenkomen met bijna-multiple eigenwaarden waarbij de lobpcg met één vector lijdt aan langzame convergentie.De blokgrootte kan worden afgestemd om numerieke stabiliteit te balanceren versus convergentiesnelheid versus computerkosten van orthogonalisaties en de Rayleigh-Ritz-methode bij elke iteratie.

Kernontwerp

De blokbenadering in LOBPCG vervangt enkele vectoren ${\ displaystyle x^{i}, \, w^{i},}$ en ${\ displaystyle p^{i}}$ met blokvectoren, d.w.z. matrices ${\ displaystyle x^{i}, \, w^{i},}$ en ${\ displaystyle p^{i}}$, waar bijvoorbeeld elke kolom van ${\ displaystyle x^{i}}$ Benadert een van de eigenvectoren.Alle kolommen worden tegelijkertijd herhaald en de volgende matrix van geschatte eigenvectoren ${\ displaystyle x^{i+1}}$ wordt bepaald door de Rayleigh -Ritz -methode Op de subruimte overspannen door alle kolommen van matrices ${\ displaystyle x^{i}, \, w^{i},}$ en ${\ displaystyle p^{i}}$. Elke kolom van ${\ displayStyle w^{i}}$ wordt eenvoudig berekend als de voorgeconditioneerde rest voor elke kolom van ${\ displaystyle x^{i}.}$ De matrix ${\ displaystyle p^{i}}$ wordt zodanig vastgesteld dat de subruimten die worden overgebracht door de kolommen van ${\ displaystyle [x^{i}, \, p^{i}]}$ en van ${\ displaystyle [x^{i}, \, x^{i-1}]}$ zijn hetzelfde.

Numerieke stabiliteit versus efficiëntie

De uitkomst van de Rayleigh -Ritz -methode wordt bepaald door de subruimte die wordt overspannen door alle kolommen van matrices ${\ displaystyle x^{i}, \, w^{i},}$ en ${\ displaystyle p^{i}}$, waar een basis van de subruimte theoretisch willekeurig kan zijn.In onaf onectieve computer rekent echter de Rayleigh -Ritz -methode wordt numeriek onstabiel als sommige basisvectoren ongeveer lineair afhankelijk zijn.Numerieke instabiliteiten komen meestal voor, bijvoorbeeld als sommige van de eigenvectoren in het iteratieve blok al bereikbare nauwkeurigheid bereiken voor een bepaalde computerprecisie en vooral prominent aanwezig zijn in lage precisie, b.v. enkele precisie.

De kunst van meerdere verschillende implementatie van LOBPCG is om de numerieke stabiliteit van de Rayleigh -Ritz -methode tegen minimale rekenkosten door een goede basis van de subruimte te kiezen.De aantoonbaar meest stabiele benadering van het maken van de basisvectoren orthogonaal, bijvoorbeeld door de Gram -Schmidt -proces, is ook de meest computationele duur.Bijvoorbeeld LOBPCG -implementaties,^[9][10] gebruik onstabiel maar efficiënt Cholesky -ontleding van de normale matrix, die alleen op individuele matrices wordt uitgevoerd ${\ displayStyle w^{i}}$ en ${\ displaystyle p^{i}}$, in plaats van op de hele subruimte.De constant toenemende hoeveelheid computergeheugen maakt tegenwoordig typische blokgroottes mogelijk in de ${\ DisplayStyle 10^{3} -10^{4}}$ Bereik, waar het percentage van de rekentijd besteedt aan orthogonalisaties en de Rayleigh-Ritz-methode begint te domineren.

Vergrendeling van eerder geconvergeerde eigenvectoren

Blokmethoden voor eigenwaardeproblemen die herhalen subsspaces meestal hebben dat sommige van de iteratieve eigenvectoren sneller worden geconvergeerd dan andere die motiveert dat het vergrendelen van de reeds geconvergeerde eigenvectoren, d.w.z. ze uit de iteratieve lus verwijdert, om onnodige berekeningen te elimineren en de numerische stabiliteit te verbeteren.Een eenvoudige verwijdering van een eigenvector kan waarschijnlijk ertoe leiden dat het duplicaat is in nog steeds itererende vectoren.Het feit dat de eigenvectoren van symmetrische eigenwaardeproblemen paarsgewijze orthogonaal zijn, suggereert dat alle iteratieve vectoren orthogonaal voor de vergrendelde vectoren worden gehouden.

Vergrendeling kan anders worden geïmplementeerd met het handhaven van numerieke nauwkeurigheid en stabiliteit, terwijl de rekenkosten worden geminimaliseerd.Bijvoorbeeld LOBPCG -implementaties,^[9][10] volgen,^[8][11] Harde vergrendeling scheiden, d.w.z. een deflatie door beperking, waarbij de vergrendelde eigenvectoren dienen als een code -invoer en niet veranderen, van zachte vergrendeling, waarbij de vergrendelde vectoren niet deelnemen aan de typisch duurste iteratieve stap om de residuen te berekenen,Neem deel aan de Rayleigh - Ritz -methode en mogen dus door de Rayleigh worden gewijzigd - RITZ -methode.

Convergentietheorie en praktijk

Lobpcg per bouw is gegarandeerd^[8] om de Rayleigh quotiënt niet langzamer dan het blok steilst gradiëntafkomst, die een uitgebreide convergentietheorie heeft.Elk eigenvector is een stationair punt van de Rayleigh quotiënt, waar de gradiënt verdwijnt.Dus de gradiëntafkomst kan vertragen in een nabijheid van elke eigenvectorHet is echter gegarandeerd om te convergeren naar de eigenvector met een lineaire convergentiesnelheid of, als deze eigenvector een is zadelpunt, het iteratief Rayleigh quotiënt is meer kans om onder de overeenkomstige eigenwaarde te vallen en lineair te convergeren naar de volgende eigenwaarde hieronder.De slechtste waarde van de lineaire convergentiesnelheid is bepaald^[8] en hangt af van de relatieve kloof tussen de eigenwaarde en de rest van de matrix spectrum en de kwaliteit van de voorwaarde, indien aanwezig.

Voor een algemene matrix is er duidelijk geen manier om de eigenvectoren te voorspellen en dus de initiële benaderingen te genereren die altijd goed werken.De iteratieve oplossing door LOBPCG kan gevoelig zijn voor de initiële eigenvectorsbenaderingen, bijvoorbeeld die langer duurt om te vertragen als het passeren van tussenliggende eigenparen.Bovendien kan men in theorie geen convergentie garanderen voor de kleinste eigenpair, hoewel de waarschijnlijkheid van de Miss nul is.Een goede kwaliteit willekeurig Gaussiaans Functie met de nul gemeen is meestal de standaardinstelling in LOBPCG om de initiële benaderingen te genereren.Om de initiële benaderingen te repareren, kan men een vast zaadje selecteren voor de willekeurig nummer generator.

In tegenstelling tot Lanczos -methode, Lobpcg vertoont zelden asymptotisch superlineaire convergentie in praktijk.

Gedeeltelijk Hoofdcomponentanalyse (PCA) en Singuliere waarden ontbinding (SVD)

Lobpcg kan triviaal worden aangepast voor het berekenen van verschillende grootste enkelvoudige waarden en de overeenkomstige enkelvoudige vectoren (gedeeltelijke SVD), bijvoorbeeld voor iteratieve berekening van PCA, voor een gegevensmatrix D met nul gemiddeld, zonder expliciet de covariantie Matrix D^TD, d.w.z. in matrix-vrije mode.De belangrijkste berekening is evaluatie van een functie van het product D^T(D x) van de covariantiematrix D^TD en de blokvector X Dat benadert iteratief de gewenste enkelvoudige vectoren.PCA heeft de grootste eigenwaarden van de covariantiematrix nodig, terwijl LOBPCG meestal wordt geïmplementeerd om de kleinste te berekenen.Een eenvoudige work-around is om de functie te ontkennen, te vervangen -D^T(D x) voor D^T(D x) en zo de volgorde van de eigenwaarden omkeren, omdat LOBPCG het niet kan schelen of de matrix van het eigenwaardeprobleem positief is of niet.^[9]

LOBPCG voor PCA en SVD is geïmplementeerd in Scipy sinds Revision 1.4.0^[12]

Algemene software -implementaties

Lobpcg's uitvinder, Andrew Knyazev, een referentie -implementatie gepubliceerd genaamd Block lokaal optimale vooraf geconditioneerde eigenwaarde Xolvers (BLOPEX)^[13][14] met interfaces naar PETSC, hypreen parallelle hiërarchische adaptieve multilevel -methode (PHAML).^[15] Andere implementaties zijn beschikbaar in, b.v. GNU -octaaf,^[16] Matlab (inclusief voor gedistribueerde of betegelingsarrays),^[9] Java,^[17] Anasazi (Trilinos),^[18] SLEPC,^[19][20] Scipy ,,^[10] Julia,^[21] MAGMA,^[22] Pytorch,^[23] Roest,^[24] Openmp en OpenACC,^[25] Cupy (EEN Numpy-Compatible Array Library versneld door Cuda),^[26] Google Jax,^[27] en Nvidia AMGX.^[28] Lobpcg is geïmplementeerd,^[29] maar niet inbegrepen, in Tensorflow.

Toepassingen

Datamining

Softwarepakketten Scikit-Learn en Megaman^[30] Gebruik lobpcg om te schalen spectrale clustering^[31] en Mevendeel leren^[32] via Laplacian Eigenmaps naar grote gegevenssets. Nvidia heeft geïmplementeerd^[33] Lobpcg in zijn nvgraph -bibliotheek geïntroduceerd in Cuda 8. sphynx,^[34] Een hybride gedistribueerde- en gedeelde-geheugen-compatibele parallelle grafische partitioner- de eerste grafiekpartitie-tool die werkt op GPU's op gedistribueerde geheugeninstellingen- gebruikt spectrale clustering voor Grafiekpartitie, het berekenen van eigenvectoren op de Laplaciaanse matrix van de grafiek met behulp van lobpcg van de Anasazi pakket.

Materiële wetenschappen

Lobpcg wordt geïmplementeerd in Abinit^[35] (inclusief Cuda versie) en Octopus.^[36] Het is gebruikt voor multi-miljard maat matrices door Gordon Bell -prijs finalisten, op de Earth Simulator supercomputer in Japan.^[37][38] Hubbard -model voor sterk gecorreleerde elektronensystemen om het mechanisme achter de supergeleiding gebruikt LOBPCG om de grondstaat van de Hamiltoniaans op de K computer^[39] en multi-GPU-systemen.^[40]

Er zijn Matlab^[41] en Julia^{[42][43] [44]} Versies van lobpcg voor Kohn-sham Vergelijkingen en Dichtheid functionele theorie (DFT) met behulp van de gewone basis.Recente implementaties zijn onder meer TTPY,^[45] Platypus -qm,^[46] Mfdn,^[47] Aas-molecuul,^[48] Laconieke.^[49]

Mechanica en vloeistoffen

Lobpcg van BLOPEX wordt gebruikt voor voorwaarde instellen op multilevel Balancerende domeinontleding door beperkingen (BDDC) Solver Library BDDCML, die is opgenomen in OpenFTL (Open Eindelement Sjabloonbibliotheek) en flow123d simulator van ondergrondse waterstroom, opgeloste stof en Warmtransport in een gebroken poreuze media.Lobpcg is geïmplementeerd^[50] in LS-DYNA.

Maxwell's vergelijkingen

LOBPCG is een van de kern EigenValue -oplossers in Pyfemax en hoge prestaties multiphysics eindelement Software netgen/ngsolve.Lobpcg van hypre is opgenomen in open source lichtgewicht schaalbaar C ++ bibliotheek voor eindelement methoden Mfem, die in veel projecten wordt gebruikt, waaronder ONTPLOFFING, Xbraid, Op bezoek komen, XSDK, het FastMath Institute in SCIDAC, en het co-designcentrum voor efficiënte exascale discretisaties (ceed) in de Exascale computing Project.

Denoiserend

Iteratieve lobpcg-gebaseerde bij benadering low-pass filter kan worden gebruikt voor denoiserend;zien,^[51] bijv. om te versnellen Totale variatie denoising.

Beeldsegmentatie

Beeldsegmentatie via spectrale clustering voert een lage dimensie uit inbedden een affiniteit matrix tussen pixels, gevolgd door clustering van de componenten van de eigenvectoren in de lage dimensionale ruimte, bijvoorbeeld met behulp van de Grafiek Laplacian voor de bilateraal filter. Beeldsegmentatie via spectral Grafiekpartitie door lobpcg met multigrid voorwaarde is voor het eerst voorgesteld in ^[52] en eigenlijk getest in ^[53] en.^[54] De laatste aanpak is later geïmplementeerd in Python Scikit-Learn^[55] dat gebruikt lobpcg van Scipy met Algebraïsche multigridvoorconditionering Voor het oplossen van het eigenwaardeprobleem voor de grafiek Laplacian.

Referenties

Externe links

• Lobpcg in Matlab
• Lobpcg in Octaaf
• Lobpcg in Scipy
• Lobpcg in Java Bij Google Code
• Lobpcg in blok lokaal optimale vooraf geconditioneerde eigenwaarde xolvers (BLOPEX) Bij Gitub en gearchiveerd Bij Google Code