Multigrid -metode - Multigrid method

I numerisk analyse er en multigrid -metode ( MG -metode ) en algoritme for å løse differensialligninger ved hjelp av et hierarki av diskretiseringer . De er et eksempel på en klasse teknikker som kalles multiresolution -metoder , veldig nyttige i problemer som viser flere atferdsskalaer. For eksempel viser mange grunnleggende avslapningsmetoder forskjellige konvergenshastigheter for komponenter med kort og lang bølgelengde, noe som tyder på at disse forskjellige skalaene blir behandlet annerledes, som i en Fourier-analysemetode for multigrid. MG -metoder kan brukes som løsere så vel som forkondisjonatorer .

Hovedideen med multigrid er å akselerere konvergensen av en grunnleggende iterativ metode (kjent som avslapning, som vanligvis reduserer kortbølgelengdefeil) ved en global korreksjon av tilnærmingen til finnettløsningen fra tid til annen, oppnådd ved å løse et grovt problem . Det grove problemet, selv om det er billigere å løse, ligner på problemet med fint nett ved at det også har kort- og langbølgelengdefeil. Det kan også løses ved en kombinasjon av avslapning og appell til fortsatt grovere rutenett. Denne rekursive prosessen gjentas til et rutenett er nådd der kostnaden for direkte løsning der er ubetydelig sammenlignet med kostnaden for ett avslapningsfei på det fine rutenettet. Denne multigrid -syklusen reduserer vanligvis alle feilkomponenter med en fast mengde begrenset godt under en, uavhengig av finrutenettstørrelsen. Den typiske applikasjonen for multigrid er i den numeriske løsningen av elliptiske partielle differensialligninger i to eller flere dimensjoner.

Multigrid -metoder kan brukes i kombinasjon med hvilken som helst av de vanlige diskretiseringsteknikkene. For eksempel kan den endelige elementmetoden omformes som en multigrid -metode. I disse tilfellene er multigridmetoder blant de raskeste løsningsteknikkene som er kjent i dag. I motsetning til andre metoder er multigridmetoder generelle ved at de kan behandle vilkårlige regioner og grensebetingelser . De er ikke avhengige av likbarhetens separasjon eller andre spesielle egenskaper ved ligningen. De har også vært mye brukt i mer-kompliserte ikke-symmetrisk og ikke-lineære ligningssystemer, som de Lame ligninger av elastisitet eller Navier-Stokes ligninger .

Algoritme

Visualisering av iterativ Multigrid -algoritme for rask O (n) konvergens.

Det er mange varianter av multigrid -algoritmer, men fellestrekkene er at et hierarki med diskretiseringer (rutenett) vurderes. De viktige trinnene er:

Utjevning - reduserer høyfrekvente feil, for eksempel ved å bruke noen få iterasjoner av Gauss – Seidel -metoden .
Residual Computation - beregning av restfeil etter utjevning (er).
Begrensning - nedsampling av gjenværende feil til et grovere rutenett.
Interpolasjon eller forlengelse - interpolering av en korreksjon beregnet på et grovere rutenett til et finere rutenett.
Korreksjon - Legge til forlenget grovere rutenettløsning på det finere rutenettet.

Det er mange valg av multigridmetoder med varierende avveininger mellom hastigheten på å løse en enkelt iterasjon og konvergenshastigheten med nevnte iterasjon. De tre hovedtypene er V-syklus, F-syklus og W-syklus. For et diskret 2D-problem tar F-Cycle 83% mer tid å beregne enn en V-Cycle-iterasjon mens en W-Cycle-iterasjon tar 125% mer. Hvis problemet er konfigurert i et 3D-domene, tar en F-Cycle-iterasjon og en W-Cycle-iterasjon henholdsvis omtrent 64% og 75% mer tid enn en V-Cycle-iterasjon som ignorerer overhead . Vanligvis produserer W-Cycle lignende konvergens som F-Cycle. Imidlertid, i tilfeller av konveksjonsdiffusjonsproblemer med høye Péclet-tall , kan W-Cycle vise overlegenhet i sin konvergensrate per iterasjon i forhold til F-Cycle. Valget av utjevningsoperatorer er ekstremt mangfoldig, ettersom de inkluderer Krylov -underromsmetoder og kan forhåndsbetinges .

Enhver geometrisk multigrid syklus iterasjon utføres på et hierarki av rutenett, og derfor kan den kodes ved hjelp av rekursjon. Siden funksjonen kaller seg selv med mindre (grovere) parametere, er det groveste rutenettet der rekursjonen stopper. I tilfeller der systemet har et høyt tilstandsnummer , endres korreksjonsprosedyren slik at bare en brøkdel av den forlengede, grovere rutenettløsningen legges til det finere rutenettet.

Disse trinnene kan brukes som vist i pseudokoden i MATLAB-stil for 1 iterasjon av V-Cycle Multigrid :

function phi = V_Cycle(phi,f,h)
    % Recursive V-Cycle Multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-Smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-Smoothing
    phi = smoothing(phi,f,h);
end

Følgende representerer F-syklus multigrid . Denne multigrid-syklusen er tregere enn V-syklus per iterasjon, men resulterer i raskere konvergens.

function phi = F_Cycle(phi,f,h)
    % Recursive F-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = F_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

På samme måte kan prosedyrene endres som vist i pseudokoden i MATLAB-stil for 1 iterasjon av W-syklus multigrid for en enda bedre konvergens i visse tilfeller:

function phi = W_cycle(phi,f,h)
    % Recursive W-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

Beregningskostnad

Forutsatt et todimensjonalt problemoppsett, beveger beregningen seg over rutenetthierarkiet annerledes for forskjellige multigrid-sykluser.

Denne tilnærmingen har fordelen fremfor andre metoder at den ofte skaleres lineært med antall diskrete noder som brukes. Med andre ord kan den løse disse problemene til en gitt nøyaktighet i en rekke operasjoner som er proporsjonal med antall ukjente.

Anta at man har en differensialligning som kan løses omtrent (med en gitt nøyaktighet) på et rutenett med en gitt rutenetttetthet . Anta videre at en løsning på et hvilket som helst rutenett kan oppnås med en gitt innsats fra en løsning på et grovere rutenett . Her er forholdet mellom rutenettpunkter på "nærliggende" rutenett og antas å være konstant gjennom rutenetthierarkiet, og er en konstant modell for innsatsen for å beregne resultatet for ett rutenett. ${\ displaystyle i}$ ${\ displaystyle N_ {i}}$ ${\ displaystyle N_ {i}}$ ${\ displaystyle W_ {i} = \ rho KN_ {i}}$ ${\ displaystyle i+1}$ ${\ displaystyle \ rho = N_ {i+1}/N_ {i} <1}$ ${\ displaystyle K}$

Følgende gjentagelsesrelasjon oppnås deretter for innsatsen for å skaffe løsningen på nettet : ${\ displaystyle k}$

{\ displaystyle W_ {k} = W_ {k+1}+\ rho KN_ {k}}

Eksempel på konvergenspriser for multigrid -sykluser sammenlignet med andre utjevningsoperatører.

Og spesielt, finner vi for de fineste rutenett som ${\ displaystyle N_ {1}}$

{\ displaystyle W_ {1} = W_ {2}+\ rho KN_ {1}}

Å kombinere disse to uttrykkene (og bruke ) gir ${\ displaystyle N_ {k} = \ rho ^{k-1} N_ {1}}$

{\ displaystyle W_ {1} = KN_ {1} \ sum _ {p = 0} ^{n} \ rho ^{p}}

Ved å bruke den geometriske serien finner vi (for endelig ) ${\ displaystyle n}$

{\ displaystyle W_ {1} <KN_ {1} {\ frac {1} {1- \ rho}}}

det vil si at en løsning kan oppnås i tide. Det skal nevnes at det er ett unntak fra ie W-syklus multigrid som brukes på et 1D-problem; det ville resultere i kompleksitet. ${\ displaystyle O (N)}$ ${\ displaystyle O (N)}$ ${\ displaystyle O (Nlog (N))}$

Multigrid forkondisjonering

En multigrid -metode med en bevisst redusert toleranse kan brukes som en effektiv forutsetning for en ekstern iterativ løsningsmiddel, f.eks. Løsningen kan fremdeles oppnås i tide så vel som i tilfellet der multigrid -metoden brukes som en løsning. Multigrid forkondisjonering brukes i praksis selv for lineære systemer, vanligvis med en syklus per iterasjon, f.eks. I Hypre . Hovedfordelen kontra en rent multigrid -løsning er spesielt tydelig for ikke -lineære problemer, f.eks. Egenverdi -problemer . ${\ displaystyle O (N)}$

Hvis matrisen til den opprinnelige ligningen eller et egenverdi -problem er symmetrisk positiv definit (SPD), er forkondisjoneringen vanligvis også konstruert for å være SPD, slik at standard konjugatgradient (CG) iterative metoder fremdeles kan brukes. Slike pålagte SPD-begrensninger kan komplisere konstruksjonen av forkondisjoneringsanlegget, f.eks. Krever koordinert for- og etterutjevning. Imidlertid er forhåndskondisjonerte bratteste nedstigninger og fleksible CG -metoder for lineære SPD -systemer og LOBPCG for symmetriske egenverdiproblemer alle vist å være robuste hvis forkondisjoneringen ikke er SPD.

Bramble – Pasciak – Xu forkondisjonering

Opprinnelig beskrevet i Xus Ph.D. avhandlingen og senere publisert i Bramble-Pasciak-Xu, er BPX-forkondisjoneringen en av de to store multigrid-tilnærmingene (den andre er den klassiske multigrid-algoritmen som V-syklus) for å løse store algebraiske systemer som oppstår ved diskretisering av modeller innen vitenskap og ingeniørfag beskrevet av partielle differensialligninger. Med tanke på delromskorrigeringsrammeverket, er BPX-forkondisjonering en parallell korreksjonsmetode for underrom der den klassiske V-syklusen er en påfølgende metode for korreksjon av underrom. BPX-forkondisjoneringen er kjent for å være naturlig mer parallell og i noen applikasjoner mer robust enn den klassiske V-syklus multigrid-metoden. Metoden har blitt mye brukt av forskere og praktikere siden 1990.

Generaliserte multigrid -metoder

Multigrid -metoder kan generaliseres på mange forskjellige måter. De kan brukes naturlig i en tidsskridende løsning av parabolske partielle differensialligninger , eller de kan brukes direkte på tidsavhengige partielle differensialligninger . Forskning på flernivåsteknikker for hyperboliske partielle differensialligninger pågår. Multigrid -metoder kan også brukes på integrerte ligninger , eller for problemer i statistisk fysikk .

Et annet sett med multiresolution -metoder er basert på bølger . Disse wavelet -metodene kan kombineres med multigrid -metoder. For eksempel er en bruk av bølger å omformulere den endelige elementmetoden når det gjelder en flernivåmetode.

Adaptiv multigrid viser adaptiv mesh -forfining , det vil si at den justerer rutenettet etter hvert som beregningen fortsetter, på en måte som er avhengig av selve beregningen. Tanken er å øke oppløsningen av nettet bare i områder av løsningen der det er nødvendig.

Algebraisk multigrid (AMG)

Praktisk viktige utvidelser av multigridmetoder inkluderer teknikker der ingen delvis differensialligning eller geometrisk problembakgrunn brukes for å konstruere flernivåhierarkiet. Slike algebraiske multigridmetoder (AMG) konstruerer sitt hierarki av operatører direkte fra systemmatrisen. I klassisk AMG er hierarkiets nivåer ganske enkelt delsett av ukjente uten noen geometrisk tolkning. (Mer generelt kan grove rutenett ukjente være spesielle lineære kombinasjoner av fine rutenettet ukjente.) Dermed blir AMG-metoder black-box-løsninger for visse klasser av sparsomme matriser . AMG anses hovedsakelig som fordelaktig der geometrisk multigrid er for vanskelig å bruke, men brukes ofte bare fordi den unngår kodingen som er nødvendig for en sann multigrid -implementering. Mens klassisk AMG ble utviklet først, er en relatert algebraisk metode kjent som smoothed aggregation (SA).

I en oversiktsartikkel av Jinchao Xu og Ludmil Zikatanov forstås de "algebraiske multigrid" -metodene fra et abstrakt synspunkt. De utviklet et enhetlig rammeverk og eksisterende algebraiske multigridmetoder kan utledes sammenhengende. Abstrakt teori om hvordan man konstruerer optimal grov plass så vel som kvasi-optimale mellomrom ble avledet. De beviste også at under passende forutsetninger konvergerer den abstrakte to-nivå AMG-metoden jevnt med hensyn til størrelsen på det lineære systemet, koeffisientvariasjonen og anisotropien. Deres abstrakte rammeverk dekker de fleste eksisterende AMG-metoder, for eksempel klassisk AMG, energiminimerings-AMG, uslettet og utjevnet aggregerings-AMG og spektral AMGe.

Multigrid i tidsmetoder

Multigrid -metoder er også vedtatt for løsning av opprinnelige verdiproblemer . Av spesiell interesse her er parallelle-i-tid multigrid-metoder: i motsetning til klassiske Runge-Kutta eller lineære flertrinnsmetoder , kan de tilby samtidighet i tidslig retning. Den velkjente Parareal parallelle-i-tid-integrasjonsmetoden kan også omformuleres som en to-nivå multigrid i tid.

Multigrid for nesten unike problemer

Nesten unike problemer oppstår i en rekke viktige fysiske og tekniske applikasjoner. Enkle, men viktige eksempler på nesten unike problemer kan bli funnet ved forskyvningsformuleringen av lineær elastisitet for nesten ukomprimerbare materialer. Vanligvis kommer det store problemet med å løse slike nesten enkeltstående systemer ned for å behandle den nesten entydige operatøren gitt av robust i forhold til den positive, men lille parameteren . Her er en symmetrisk semidefinitt operator med stort nullrom , mens den er en symmetrisk positiv bestemt operator. Det var mange arbeider for å prøve å designe en robust og rask multigrid -metode for slike nesten unike problemer. En generell veiledning er gitt som et designprinsipp for å oppnå parametere (f.eks. Maskestørrelse og fysiske parametere som Poissons forhold som vises i den nesten entall operatøren) uavhengig konvergenshastighet for multigrid -metoden som brukes på slike nesten unike systemer, dvs. hvert rutenett, en romnedbrytning basert på hvilken utjevningen påføres, må konstrueres slik at nullrommet til entalldelen til den nesten entall operatøren må inkluderes i summen av de lokale nullrommene, skjæringspunktet mellom nullen plass og de lokale mellomrom som skyldes romspaltninger. ${\ displaystyle A+\ varepsilon M}$ ${\ displaystyle \ varepsilon}$ ${\ displaystyle A}$ ${\ displaystyle M}$

Merknader

Referanser

GP Astrachancev (1971), En iterativ metode for å løse elliptiske nettproblemer . USSR Comp. Matte. Matte. Fys. 11, 171–182.
NS Bakhvalov (1966), Om konvergens av en avslapningsmetode med naturlige begrensninger for den elliptiske operatøren . USSR Comp. Matte. Matte. Fys. 6, 101–13.
Achi Brandt (april 1977), " Multi-Level Adaptive Solutions to Boundary-Value Problems ", Mathematics of Computation , 31 : 333–90.
William L. Briggs, Van Emden Henson og Steve F. McCormick (2000), A Multigrid Tutorial (2. utg.), Philadelphia: Society for Industrial and Applied Mathematics , ISBN 0-89871-462-1 .
RP Fedorenko (1961), En avslapningsmetode for å løse elliptiske differensialligninger . USSR Comput. Matte. Matte. Fys. 1, s. 1092.
RP Fedorenko (1964), Konvergenshastigheten til en iterativ prosess. USSR Comput. Matte. Matte. Fys. 4, s. 227.
Trykk, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Del 20.6. Multigrid -metoder for problemer med grenseverdier" . Numeriske oppskrifter: The Art of Scientific Computing (3. utg.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.

Languages

In other projects