7.3 Cholesky-Zerlegung im Ring

Sei nun A symmetrisch und positiv definit (d.h. v ^TAv > 0 $\forall$ v $\in$ $\mathbb {R} ^{n}_{}$,v $\neq$ 0).

Idee:

1. Bestimme obere Dreiecksmatrix U mit U ^TU = A .

2. Bestimme y mit U ^T · y = b .

3. Bestimme x mit Ux = y .

Dann gilt Ax = b , denn aus Ux = y folgt U ^TUx = U ^Ty mit U ^TU = A und U ^Ty = b .

zu 1.)

Sei U bis zur Zeile i - 1 bereits bestimmt. Aus

a_ii = $$\sum_{k = 0}^{i}$$(u_ki)²$$\mbox{ und }$$a_ij = $$\sum_{k = 0}^{i}$$(u_ik^T · u_kj)$$\mbox{ folgt}$$

FOR i:= 0 TO n-1 DO (* i-te Zeile *)
   tmp := a[i,i];
   FOR k := 0 TO i-1 DO
      tmp := tmp - u[k,i]*u[k,i]
   END;
   u[i,i] := sqrt(tmp); (* Diagonalelement *)
   FOR j := i+1 TO n-1 DO
      tmp := a[i,j];
      FOR k := 0 TO i-1 DO
         tmp := tmp - u[k,i]*u[k,j];
      END
      u[i,j] := tmp/u[i,i]
   END
END

zu 2.)

$$\mbox{Aus }$$b_i = $$\sum_{j = 0}^{i}$$u_ij^T · y_j$$\mbox{ folgt}$$

y_i : = (b_i - $$\sum_{j = 0}^{i - 1}$$u_ji · y_j)/u_ii

Forward-Substitution

FOR i := 0 TO n-1 DO
   tmp := b[i];
   FOR j := 0 TO i-1 DO
      tmp := tmp - u[j,i]*y[j]
   END;
   y[i] := tmp/u[i,i]
END

zu 3.)

$$\mbox{Aus }$$y_i = $$\sum_{j = i}^{n-i}$$u_ij · x_j$$\mbox{ folgt}$$

x_i : = (y_i - $$\sum_{j =i+1}^{n - 1}$$u_ij · x_j)/u_ii

Backward-Substitution

FOR i := n-1 DOWNTO 0 DO
   tmp := y[i];
   FOR j := i + 1 TO n-1 DO
      tmp := tmp - u[i,j]*x[j]
   END;
   x[i] := tmp/u[i,i]
END

Zur parallelen Cholesky-Zerlegung wird ein Ring von n Prozessoren verwendet. Zu Beginn speichert Prozessor j Spalte j von Matrix A . Während der Rechnung ermittelt Prozessor j die Spalte j von Matrix U . Dabei können die Matrixelemente von A mit denen von U überschrieben werden. Für die parallele Backward-Substitution ist es erforderlich, daß Prozessor i über die i -te Zeile von U verfügt. Dies kann dadurch erreicht werden, daß während der parallelen Zerlegungsphase die entsprechenden Matrixelemente beim Durchreichen einbehalten werden (nicht im Algorithmus berücksichtigt!). Die parallele Forward-Substitution kann vereinfacht werden, indem b als zusätzliche Spalte n von A schon in der Zerlegung behandelt wird (nicht im Algorithmus berücksichtigt).