Diskretiseringsmatriser från PDE: Spektralanalys med hög precision, matrislösa egenvärdeslösare och effektiva lineära lösare

Tidsperiod:: 1 juli 2019 – 1 februari 2021
Projektledare:: Sven-Erik Ekström
Finansiär:: Vetenskapsrådet
Bidragstyp:: Bidrag för anställning eller stipendier
Budget:: 1 662 500 SEK

Fysikaliska fenomen beskrivs ofta matematiskt med partiella differential-ekvationer (PDE) eller fraktionella differential-ekvtioner (FDE). Oftast måste man lösa ekvationerna med hjälp av datorer, och man behöver då diskretisera ekvationerna, d.v.s. man delar upp problemet i många små delproblem. Detta leder ofta till ett lineärt ekvationssystem, Au=b, där u är en sökt kvantitet, och A är en matris med viss struktur givet av diskretiseringen.Kunskap om det så kallade spektrumet för matrisen A, d.v.s. dess egenvärden (eller singulärvärden), är viktigt inom många tillämpningar. I vissa fall kan egenvärdena i sig själva vara den sökta lösningen på problemet; egenvärdena kan t.ex. beskriva resonansfrekvenser inom strukturmekanik, uppkomst av turbulens inom fluidmekanik och och energinivåer inom kvantmekanik. I andra fall behövs en beskrivning av spektrumet för att analysera och utveckla effektiva lösningsmetoder för att kunna hitta u; t.ex. prekonditionerade iterativa metoder, multigrid, eller deflation. Det är därför viktigt att kunna beskriva spektrumet för olika matriser A med stor noggrannhet, då de flesta problem från tillämpningar är av dessa två typer, och det finns ett stort behov av effektivare lösningmetoder.Genom att identifiera en funktion f(θ), den så kallade spektrala symbolen, för en given matris A har vi ett kraftfullt verktyg för att beskriva dess spektrum.För att göra detta använder vi teorin om generaliserade lokala Toeplitz (GLT) sekvenser, introducerat på slutet av 1990-talet av S. Serra-Capizzano, som är rik och avancerad form av Fourier-analys som hanterar Toeplitz och Toeplitz-lika matriser, vilket inkluderar i princip alla former av matriser från PDE-diskretiseringar, t.ex. finita differenser, finita volymer, finita element, diskontinuerlig Galerkin, eller isogeometrisk analys.När man ska analysera spektrumet för en ny typ av matris A, så identifieras först dess symbol, f(θ). Vi kan sedan approximera matrisen A:s egenvärden, som vi betecknar λ(A), genom att evaluera symbolen f(θ) med n valda punkter Θ={θ1, θ2,..., θn}. Felen för dessa approximationer, E=λ(A)-f(Θ), beror normalt linjärt på matrisens storlek, d.v.s. om man dubblerar matrisens storlek så skalas felet E/2 d.v.s det halveras.I den sökandes avhandling introducerades en helt ny typ av egenvärdeslösare, så kallade matrislösa metoder, för att beräkna egenvärdena för Toeplitz-lika matriser. Namnet, som inte ska sammanblandas med matrisfria metoder, kommer sig av att man aldrig behöver skapa matrisen vars egenvärden man söker. De är parallelliserbara, extremt effektiva jämfört med konventionella metoder, och minskar felet radikalt jämfört med E. Metoderna bygger på att vi kan beskriva felet som E=Eα-1+Eα, för en vald parameter α, och de kan med stor noggrannhet räkna ut Eα-1. Då blir det nya totala felet Eα, som är mycket mindre än E. Om man dubblerar matrisens A:s storlek, så skalas felet Eα/2α+1, d.v.s. det minskar mycket snabbare än ursprungliga felet E som bara halverades.Matrislösa metoder är många ordningar effektivare än konventionella egenvärdeslösare; se t.ex. exekveringstid på tio minuter mot över tio timmar för ett exempel i den sökandes avhandling.I projektet vill vi använda och utveckla dessa nya resultat för att nå tre övergripande mål.Tillämpa och utveckla GLT-teorin och matrislösa metoder på matriser från olika typer av diskretiseringar av olika typer av PDE och FDE;Utveckling av kunskapen om så kallade icke-symmetriska Toeplitz-lika matriser, både från modellproblem och PDE-diskretiseringar. Även applicering av matrislösa metoder på denna typ av matriser, då standardlösare har problem med dessa;Utveckling av effektiva PDE och FDE-lösare, intitialt så kallad deflation där vi även behöver utveckla bättre approximationer av egenvektorer för matriserna. Prekonditionerare för så kallade iterativa metoder och multigrid är