Cyklisk reduktion

Cyklisk reduktion är en numerisk metod för att lösa stora linjära system genom att upprepade gånger dela upp problemet. Varje steg eliminerar jämna eller udda rader och kolumner i en matris och förblir i en liknande form. Elimineringssteget är relativt dyrt men att dela upp problemet tillåter parallell beräkning.

Tillämplighet

Metoden gäller endast matriser som kan representeras som en (block) Toeplitz-matris , sådana problem uppstår ofta i implicita lösningar för partiella differentialekvationer på ett gitter. Till exempel snabba lösare för Poissons ekvation uttrycker problemet som att lösa en tridiagonal matris, diskretisera lösningen på ett vanligt rutnät.

Noggrannhet

System som har god numerisk stabilitet tenderar initialt att bli bättre för varje steg till en punkt där en bra ungefärlig lösning kan ges, men eftersom den speciella matrisformen måste bevaras kan inte svängning utföras för att förbättra numerisk noggrannhet.

Jämförelse med multigrid

Metoden är inte iterativ, den söker en exakt lösning på det linjära problemet som överensstämmer med de givna gränsvärdena, i motsats till den liknande men beräkningsmässigt billigare multigrid-metoden som sprider felkorrigeringsuppskattningar nedåt och tillåter olika relaxationsparametrar i olika skalor, iterativ aspekt som möjliggör bättre inkorporering av icke-linjära egenskaper.

Kombination med snabb Fouriertransform FFT

Att transformera från den rumsliga domänen och återställa PDE kallas en spektral metod , Fourieranalys och cyklisk reduktion kombineras i FACR-algoritmen som förklaras i Numeriska recept – se 19.4 Fourier- och cykliska reduktionsmetoder för gränsvärdeproblem.