\documentclass{slides}
\usepackage{amsmath,amssymb}
\begin{document}
\slide

Zur Komplexit\"at von
\begin{center}
Inversion von Matrizen \\ 
L\"osen von linearen Gleichungssystemen
\end{center}

$C(f_{A^{-1}}^{(n)})$ : arithmetische Komplexit\"at\\
(Schaltkreisgr\"osse) f\"ur das Invertieren\\ 
von $n \times n$-Matrizen

$D(f_{A^{-1}}^{(n)})$ : arithmetische Komplexit\"at\\
(Schaltkreistiefe) f\"ur das Invertieren\\
 von $n \times n$-Matrizen

$M_{matrix}(n,k)$ : Gr\"osse des kleinsten
arithmeti\-schen Schaltkreises mit Tiefe
$k \cdot \log_2 n$ f\"ur die Multiplikation
von zwei $(n \times n)$-Matrizen \"uber einem Ring $R$

\slide

\begin{itemize}

\item
Verfahren mittels LDU-Zerlegung zeigt
\begin{eqnarray*}
C(f_{A^{-1}}^{(n)}) & \leq &
4 M_{matrix}(n,k) + n^2 \\
D(f_{A^{-1}}^{(n)}) & \in &\mathcal{O}(n \cdot \log^2 n)
\end{eqnarray*}
\item
Verfahren von \textsc{Csanky}, beruhend auf dem
Satz von \textsc{Cayley-Hamilton}, zeigt
\begin{eqnarray*}
C(f_{A^{-1}}^{(n)}) &\in &
\mathcal{O} (n \cdot M_{matrix}(n,k))\\
D(f_{A^{-1}}^{(n)}) & \in & \mathcal{O}(\log^2 n)
\end{eqnarray*}
\end{itemize}

\slide
Das Verfahren mittels LDU-Zerlegung

\begin{enumerate}
\item
Inversion ist einfach f\"ur Dreicksmatrizen
\item
symmetrische, positive-definite Matrizen (SPD) lassen sich
in ein LDU-Produkt zerlegen:
\[
M = L \cdot C \cdot L^t
\]
wobei $L$ untere Dreiecksmatrix und \\
$D$ Diagonalmatrix.
Mittels 
\[
M^{-1} = (L^t)^{-1} \cdot D^{-1} \cdot L^{-1}
\]
hat man die Inversion von $M$ auf die Inversion
von Dreiecksmatrizen zur\"uckgef\"uhrt
\item
Inverse beliebiger nicht-singul\"arer Matrizen $M$
lassen sich mittels Inversen von SPD-Matrizen berechnen:
\[
P  = M^t \cdot M ~~\text{ist SPD},~~
M^{-1} = P^{-1} \cdot M^t
\]
\end{enumerate}

\slide

Rekursive Berechnung der LDU-Zerlegung f\"ur SPD-Matrizen
\begin{itemize}
\item[--]
sei $M$ SPD-Matrix von Format $2n \times 2n$,
\[
M = 
\begin{pmatrix}
A & B \cr
B^t & C
\end{pmatrix}
\]
wobei $A,B,C,D$ $n \times n$-Matrizen
\item[--]
berechne (rekursiv) LDU-Zerlegung von A, d.h.
Matrizen $L_1, D_1$ mit $A = L_1 \cdot D_1 \cdot L_1^t$
\item[--]
aus
\begin{eqnarray*}
B^t  A^{-1}  L_1 & =  &
B^t  (L_1^{-1})^t  D_1^{-1} \\
S = C - B^t  A^{-1}  B &=&
C - B^t  (L_1^{-1})^t  D_1^{-1}
 L_1^{-1}  B
\end{eqnarray*}
erh\"alt man das Schur-Komplement $S$
\item[--]
berechne (rekursiv) LDU-Zerlegung von $S$, d.h.
Matrizen $L_2, D_2$ mit $A = L_2 \cdot D_2 \cdot L_2^t$

\slide

\item[--]
die LDU-Zerlegung von $M$:
\begin{align*}
&M = \\
&
\underbrace{\begin{pmatrix}
L_1 & 0 \cr
B^t A^{-1} L_1  & L_2
\end{pmatrix}}_L
\underbrace{\begin{pmatrix}
D_1 & 0 \cr
0 & D_2
\end{pmatrix}}_D
\underbrace{\begin{pmatrix}
L_1^t & L_1^t A^{-1} B \cr
0 & L_2^t
\end{pmatrix}}_{L^t}
\end{align*}
\end{itemize}

\slide

Schnelle parallele Matrix-Inversion (Csanky)

\begin{itemize}
\item

Algebraische Hilfsmittel I: \\
Symmetrische Funktionen,
Newton-Gleichung

$\lambda_1,\lambda_2, \ldots ,\lambda_n \in \mathbb{C}$
(oder Variable)

elementarsymmetrische Funktionen
\begin{eqnarray*} 
e_k & = & 
e_k(\lambda_1,\ldots,\lambda_n) \\
& = &\sum_{1 \leq i_1<i_2<\ldots<i_k\leq n}
\lambda_{i_1} \lambda_{i_2} \ldots \lambda_{i_k}
\end{eqnarray*}

erzeugende Funktion
\begin{eqnarray*}
E(t) &=& \sum_{k=0}^n e_k \, t^k \\
&=&
(1+\lambda_1 t)(1+\lambda_2 t) \cdots(1+\lambda_n t)\\
&=&
\prod_{j=1}^n  (1 + \lambda_j t)
\end{eqnarray*}

Potenzsummen
\begin{eqnarray*}
s_k &=& s_k (\lambda_1, \lambda_2, \ldots,\lambda_n) \\
&=&
\lambda_1^k + \lambda_2^k + \ldots + \lambda_n^k
\end{eqnarray*}


\slide

erzeugende Funktion
\begin{eqnarray*}
S(t) &=& \sum_{k=0}^\infty s_{k+1} t^k \\
&=&
\sum_{i=1}^n \sum_{k=0}^\infty 
\lambda_i^{k+1} t^k =
\sum_{i=1}^n \frac{\lambda_i}{1-\lambda_i t}
\end{eqnarray*}

Newton-Gleichung
\begin{eqnarray*}
S(-t) \, E(t) &=&
\sum_{i=1}^n \lambda_i \cdot
\prod_{j \neq i} (1+\lambda_j t) \\
&=&
\frac{d}{dt} \prod_{j=1}^n (1 + \lambda_j t) \\
&=&
\frac{d}{dt} \, E(t)
\end{eqnarray*}

Koeffizientenvergleich liefert Rekursion f\"ur die $e_k$ mit den
$s_\ell$ als Koeffizienten, d.h.
f\"ur $k=1,2,\ldots, n$
\[
k e_k = s_1 e_{k-1} - s_2 e_{k-2} + \ldots +
(-1)^{k-1} s_k e_0
\]

\slide

\item
Algebraische Hilfsmittel II: \\
charakteristisches Polynom
einer Matrix und Theorem von Cayley-Hamilton

Matrix $A = [a_{i,j}]_{1 \leq i,j \leq n}$ mit $a_{i,j} \in \mathbb{C}$

die Eigenwerte $\lambda_1, \ldots , \lambda_n$ von $A$
sind die Nullstellen des charakteristischen Polynoms
$\det(xI - A)$, d.h.
\begin{align*}
&\det(x I - A)  =
\prod_{i=1}^n (x - \lambda_i) \cr
&=
x^n - e_1 x^{n-1} + e_2 x^{n-2} - \ldots \pm e_n
\end{align*}
d.h. die Koeffizienten des charakteristischen Polynoms
von $A$ sind (bis auf das Vorzeichen) die
elementarsymmetrischen\\
Funktionen der Eigenwerte von $A$\\
insbesondere:
\begin{itemize}
\item
$e_1 = \sum_i a_{i,i} =: tr(A)$ ist die ``Spur'' von $A$ ,

\item
$e_n$ ist ($\pm$) die Determinante von $A$
\end{itemize}

\slide

\item
ist $\lambda$ ein Eigenwert von $A$ (mit Vielfachheit $k$, so ist
$\lambda^m$ Eigenwert von $A^m$ (ebenfalls mit Vielfachheit
$k$), d.h. 
\[
tr(A^m) = \sum \lambda_i^m = s_m
\]
\item
\textit{Theorem von Cayley-Hamilton}:\\ 
eine Matrix erf\"ullt die
Gleichung ihres \\
charakteri\-stischen Polynoms
\[
A^n - e_1 A^{n-1} + e_2 A^{n-2} - \ldots \mp e_{n-1} A \pm
e_n I = 0
\]

\item
eine Folgerung f\"ur die Berechnung der \\
inversen Matrix
\[
A^{-1} =
\frac{1}{e_n}
\left(
e_{n-1}I -e_{n-2} A + \ldots \mp e_1 A^{n-2} \pm A^{n-1}
\right)
\]
\end{itemize}

\slide

\textit{Algorithmus von Csanky}

\begin{enumerate}
\item
berechne $A$, $A^{2}$, \ldots ,$A^n$ mittels Pr\"afix-Schema
\[
C:~ M(n,k)(2n \!-\! \log n\!-\!2),~ D:~k \log n \cdot 2 \log n
\]
\item
berechne $s_k = tr(A^k)~~~(1 \leq k \leq n)$
\[
C:~\mathcal{O}(n^2),~D:~\log n
\]
\item
berechne $e_k~(1 \leq k \leq n)$ mittels Newton-Gleichungen
\[
C: M(n,k),~D:~\log^2 n
\]
\item
berechne $A^{-1}$ mittels der Cayley-Hamilton-Formel
\[
C:~n^3,~D:~\log n
\]
\end{enumerate}

\slide
L\"osen linearer Gleichungssysteme

\begin{itemize}
\item[--]
falls $M$ SPD-Matrix vom Format $n \times n$ und 
$M \cdot \mathbf{x} = \mathbf{b}$ zu l\"osen:\\
\begin{enumerate}
\item
berechne LDU-Zerlegung $M = L \cdot D \cdot L^t$
\item
l\"ose nacheinander die Systeme
\begin{enumerate}
\item (Vorw\"arts-Elimination)
\[
L \cdot \mathbf{u} = \mathbf{b}
\]
\item  (Normierung)
\[
D \cdot \mathbf{v} = \mathbf{u}
\]
\item (R\"uckw\"arts-Elimination)
\[
L^t \cdot \mathbf{x} = \mathbf{v}
\]
\end{enumerate}
\end{enumerate}
\item[--]
falls $M$ nicht SPD:
\[
M^t \cdot M \cdot \mathbf{x} = M^t \cdot \mathbf{b} = \mathbf{b}^*
\]
\end{itemize}


\slide

Komplexit\"at f\"ur das \\
L\"osen linearer Gleichungssysteme:

\begin{itemize}
\item
falls $M$ SPD-Matrix
\begin{eqnarray*}
C_{SPD-solve}(n) \leq C_{SPD}(n) + \mathcal{O}(n^2)\\
D_{SPD-solve}(n) \leq C_{SPD}(n) + \mathcal{O}(n)\
\end{eqnarray*}
\item
falls $M$ nicht SPD, Mehraufwand $M(n,k)$ an
Gr\"osse und $k \log n$ an Tiefe
\end{itemize}
\end{document}