Norsk English

Numerisk lineær algebra

Effektiv løsning av store ligningssystemer er avgjørende for mange vitenskapelige og industrielle beregninger. Vi utvikler numeriske metoder og programvare som utnytter problemets matematiske struktur og moderne maskinvare. Vår ekspertise omfatter iterative løsere, prekondisjonering, multigrid og parallelle beregninger på CPU og GPU.

Kontaktpersoner

Når ligningsløsningen blir flaskehalsen

Store simuleringsmodeller kan gi opphav til ligningssystemer med millioner av ukjente. Løsningen av disse systemene står ofte for en vesentlig del av beregningstiden og minnebruken. Valg av algoritmer og implementasjon har derfor stor betydning for hvor detaljerte modeller man kan bruke, og hvor mange beregninger man kan gjennomføre.

Vi kombinerer numerisk lineær algebra med inngående forståelse av modellene som ligningssystemene kommer fra. Det gjør oss i stand til å utvikle løsere som utnytter både matematisk struktur, fysiske egenskaper og tilgjengelig maskinvare.

Vi kan hjelpe med å:

  • Analysere flaskehalser og forbedre løsningen av store glisne ligningssystemer.
  • Velge, tilpasse og utvikle iterative løsere og prekondisjonering.
  • Utnytte blokkstruktur og koblinger mellom fysiske prosesser.
  • Utvikle multigrid-, multiskala- og domenedekomponeringsmetoder.
  • Tilpasse algoritmer og datastrukturer til parallell kjøring på CPU og GPU.
  • Integrere og evaluere løsningsmetoder i eksisterende programvare.

Ta kontakt med vår forskningsgruppe for Anvendt beregningsvitenskap dersom ligningsløsningen begrenser ytelsen eller størrelsen på beregningene dine.

Prekondisjonering tilpasset problemet

Iterative løsere nærmer seg løsningen gjennom gjentatte beregningstrinn. Effektiviteten avhenger i stor grad av prekondisjoneringen, som bruker en forenklet beskrivelse av systemet til å gjøre problemet lettere å løse. En god prekondisjoner må være både effektiv å anvende og presis nok til å redusere antallet iterasjoner.

Vi arbeider blant annet med Krylov-metoder, ufullstendige faktoriseringer, algebraisk multigrid og blokkbaserte strategier. Metodene tilpasses egenskaper som sterke materialkontraster, anisotropi, uregelmessige beregningsnett og forskjeller i skala mellom variablene.

I koblede problemer kan ulike deler av ligningssystemet ha svært forskjellige egenskaper. Vi utvikler løsningsstrategier som behandler delproblemene med egnede metoder og samtidig tar hensyn til koblingene mellom dem. Trykkbasert CPR-prekondisjonering i reservoarsimulering er et viktig eksempel på hvordan fysisk innsikt kan brukes til å konstruere effektive løsere.

Multigrid og multiskalametoder

Informasjon må kunne forplante seg gjennom hele beregningsområdet for at en iterativ metode skal konvergere raskt. Multigrid- og multiskalametoder kombinerer lokale beregninger med korreksjoner på grovere nivåer. Slik kan de håndtere både lokale variasjoner og sammenhenger over store avstander.

Vi har lang erfaring med å utvikle og bruke slike metoder for heterogene problemer og komplekse beregningsnett. Arbeidet omfatter konstruksjon av grove problemer, overføring mellom nivåer og tilpasning til parallelle beregninger. Våre multiskalametoder i MRST gir eksempler på hvordan denne ekspertisen er omsatt til tilgjengelig programvare.

Algoritmer og maskinvare må passe sammen

Metoden med færrest iterasjoner er ikke nødvendigvis den raskeste. Oppsett av prekondisjoneringen, minnetrafikk og kommunikasjon mellom prosessorer kan utgjøre en stor del av kostnaden. På GPU-er er det særlig viktig å ha tilstrekkelig parallellitet og unngå unødvendig overføring av data.

Vi utvikler algoritmer og implementasjoner i sammenheng. Dette omfatter lagring og behandling av glisne matriser, parallelle prekondisjonerere, gjenbruk av beregninger og fordeling av arbeid mellom prosessorer og akseleratorer. Målet er å redusere samlet løsningstid og ressursbruk for de problemene programvaren faktisk skal håndtere.

Fra metodeutvikling til krevende industrimodeller

Vår erfaring spenner fra utvikling og utprøving av nye algoritmer til integrasjon i store simuleringsverktøy. Vi har arbeidet med lineære løsere i både åpen programvare og interne og kommersielle simulatorer hos industrielle samarbeidspartnere.

Ligningssystemene kan endre karakter gjennom en simulering. Derfor vurderer vi metodene over representative beregningsforløp, med vekt på nøyaktighet, robusthet, minnebruk og samlet kjøretid. Vi undersøker også hvordan løsertoleranser og gjenbruk av prekondisjonering påvirker resten av beregningen.

Et samarbeid kan starte med et konkret matriseproblem, en ytelsesutfordring i eksisterende kode eller behov for en ny løsningsstrategi. Vi kan bidra fra analyse og metodevalg til implementasjon og testing i den aktuelle programvaren.

Utvalgte publikasjoner

Mange av våre metodebidrag er utviklet gjennom arbeid med reservoarsimulering, der store, koblede ligningssystemer stiller strenge krav til robusthet og beregningseffektivitet. Arbeidene nedenfor angriper imidlertid utfordringer som også oppstår i andre simuleringsområder: sterke koeffisientkontraster, koblinger mellom fysiske prosesser og effektiv parallellisering. Metodene og erfaringene gir derfor et grunnlag for å utvikle løsere tilpasset andre modeller med tilsvarende matematisk struktur.