Ofullständig LU-faktorisering

I numerisk linjär algebra är en ofullständig LU-faktorisering (förkortad som ILU ) av en matris en sparsam approximation av LU-faktoriseringen som ofta används som förkonditionering .

Introduktion

Betrakta ett glest linjärt system $Ax=b$ . Dessa löses ofta genom att beräkna faktoriseringen $A=LU$ , med L nedre enhetstriangulär och U övre triangulär . Man löser då $Ly=b$ , $Ux=y$ , vilket kan göras effektivt eftersom matriserna är triangulära.

För en typisk gles matris kan LU-faktorerna vara mycket mindre glesa än den ursprungliga matrisen - ett fenomen som kallas fill-in . Minneskraven för att använda en direktlösare kan då bli en flaskhals vid lösning av linjära system. Man kan bekämpa detta problem genom att använda fyllningsreducerande omordningar av matrisens okända, till exempel algoritmen Minimum grad .

En ofullständig faktorisering söker istället triangulära matriser L , U så att $A\approx LU$ snarare än $A=LU$ . Att lösa för $LUx=b$ kan göras snabbt men ger inte den exakta lösningen till $Ax=b$ . Så vi använder istället matrisen $M=LU$ som en förkonditionering i en annan iterativ lösningsalgoritm såsom konjugatgradientmetoden eller GMRES .

Definition

För en given matris $\displaystyle A\in \mathbb {R} ^{n\times n}}$$) {\displaystyle G(A)}$ definierar man grafen som

$G(A):=\left\lbrace (i,j)\in \mathbb {N} ^{2 }:A_{ij}\neq 0\right\rbrace \,,$

som används för att definiera de villkor som ett sparsitetsmönster $S$ behöver uppfylla

$S\subset \left\lbrace 1,\dots ,n\right\rbrace ^{2}\,,\quad \left\lbrace (i,i):1\leq i\leq n\right\rbrace \subset S\,,\quad G(A)\subset S\,.$

En sönderdelning av formen $A=LU-R$ där följande

• $L\in \mathbb {R} ^{n\times n}$ är en lägre entriangulär matris
• $U\in \mathbb {R} ^{n\times n}$ är en övre triangulär matris
• $L,U$ är noll utanför sparsitetsmönstret: $L_{ij}=U_{ij}=0\quad \forall \;(i,j)\notin S$
• $R\in \mathbb {R} ^{n\ gånger n}$ är noll inom sparsitetsmönstret: $R_{ij }=0\quad \forall \;(i,j)\in S$

kallas en ofullständig LU-sönderdelning (med avseende på sparsitetsmönstret ${\displaystyle S} )$ .

Sparsitetsmönstret för L och U väljs ofta att vara detsamma som sparsitetsmönstret för den ursprungliga matrisen A . Om den underliggande matrisstrukturen kan refereras av pekare istället för att kopieras, är det enda extra minne som krävs för inmatningarna av L och U. Denna förkonditionering kallas ILU(0).

Stabilitet

När det gäller ILU:s stabilitet bevisades följande teorem av Meijerink och van der Vorst.

Låt $A$ vara en M-matris , den (fullständiga) LU-sönderdelningen ges av ${\displaystyle A={\hat {L}}{\hat {U}}} ,$ och ILU med ${\displaystyle A=LU-R$ } Sedan

$|L_{ij}|\leq |{\hat {L}}_{ij}|\quad \forall \;i,j$

håller. Således är ILU minst lika stabil som den (fullständiga) LU-sönderdelningen.

Generaliseringar

Man kan få en mer exakt förkonditionering genom att tillåta en viss nivå av extra fyllning i faktoriseringen. Ett vanligt val är att använda sparsitetsmönstret för A ² istället för A ; denna matris är avsevärt tätare än A , men fortfarande gles överallt. Denna förkonditionering kallas ILU(1). Man kan sedan generalisera denna procedur; ILU(k)-förkonditioneraren för en matris A är den ofullständiga LU-faktoriseringen med sparsitetsmönstret för matrisen Ak ⁺¹ .

Noggrannare ILU-prekonditioneringsmedel kräver mer minne, i en sådan utsträckning att algoritmens körtid till slut ökar även om det totala antalet iterationer minskar. Följaktligen finns det en avvägning mellan kostnad och noggrannhet som användarna måste utvärdera, vanligtvis från fall till fall beroende på familjen av linjära system som ska lösas.

ILU-faktoriseringen kan utföras som en fixpunktsiteration på ett mycket parallellt sätt.

Se även

• Inkomplett Cholesky-faktorisering

•   Saad, Yousef (1996), Iterativa metoder för glesa linjära system (1:a upplagan), Boston: PWS, ISBN 978-0-534-94776-7 . Se avsnitt 10.3 och vidare.

externa länkar

• Ofullständig LU-faktorisering på CFD Wiki