$$
\newcommand{\RR}{\mathbb{R}}
\newcommand{\GG}{\mathbb{G}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\PS}{\mathcal{P}}
\newcommand{\SS}{\mathbb{S}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\HH}{\mathbb{H}}
\newcommand{\ones}{\mathbb{1\hspace{-0.4em}1}}
\newcommand{\alg}[1]{\mathfrak{#1}}
\newcommand{\mat}[1]{ \begin{pmatrix} #1 \end{pmatrix} }
\renewcommand{\bar}{\overline}
\renewcommand{\hat}{\widehat}
\renewcommand{\tilde}{\widetilde}
\newcommand{\inv}[1]{ {#1}^{-1} }
\newcommand{\eqdef}{\overset{\text{def}}=}
\newcommand{\block}[1]{\left(#1\right)}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\trace}[1]{\mathrm{tr}\block{#1}}
\newcommand{\norm}[1]{ \left\| #1 \right\| }
\newcommand{\argmin}[1]{ \underset{#1}{\mathrm{argmin}} }
\newcommand{\argmax}[1]{ \underset{#1}{\mathrm{argmax}} }
\newcommand{\st}{\ \mathrm{s.t.}\ }
\newcommand{\sign}[1]{\mathrm{sign}\block{#1}}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\inner}[1]{\langle #1 \rangle}
\newcommand{\dd}{\mathrm{d}}
\newcommand{\ddd}[2]{\frac{\partial #1}{\partial #2} }
\newcommand{\db}{\dd^b}
\newcommand{\ds}{\dd^s}
\newcommand{\dL}{\dd_L}
\newcommand{\dR}{\dd_R}
\newcommand{\Ad}{\mathrm{Ad}}
\newcommand{\ad}{\mathrm{ad}}
\newcommand{\LL}{\mathcal{L}}
\newcommand{\Krylov}{\mathcal{K}}
\newcommand{\Span}[1]{\mathrm{Span}\block{#1}}
\newcommand{\diag}{\mathrm{diag}}
\newcommand{\tr}{\mathrm{tr}}
\newcommand{\sinc}{\mathrm{sinc}}
\newcommand{\cat}[1]{\mathcal{#1}}
\newcommand{\Ob}[1]{\mathrm{Ob}\block{\cat{#1}}}
\newcommand{\Hom}[1]{\mathrm{Hom}\block{\cat{#1}}}
\newcommand{\op}[1]{\cat{#1}^{op}}
\newcommand{\hom}[2]{\cat{#1}\block{#2}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\Set}{\mathbb{Set}}
\newcommand{\Cat}{\mathbb{Cat}}
\newcommand{\Hask}{\mathbb{Hask}}
\newcommand{\lim}{\mathrm{lim}\ }
\newcommand{\funcat}[1]{\left[\cat{#1}\right]}
\newcommand{\natsq}[6]{
\begin{matrix}
& #2\block{#4} & \overset{#2\block{#6}}\longrightarrow & #2\block{#5} & \\
{#1}_{#4} \hspace{-1.5em} &\downarrow & & \downarrow & \hspace{-1.5em} {#1}_{#5}\\
& #3\block{#4} & \underset{#3\block{#6}}\longrightarrow & #3\block{#5} & \\
\end{matrix}
}
\newcommand{\comtri}[6]{
\begin{matrix}
#1 & \overset{#4}\longrightarrow & #2 & \\
#6 \hspace{-1em} & \searrow & \downarrow & \hspace{-1em} #5 \\
& & #3 &
\end{matrix}
}
\newcommand{\natism}[6]{
\begin{matrix}
& #2\block{#4} & \overset{#2\block{#6}}\longrightarrow & #2\block{#5} & \\
{#1}_{#4} \hspace{-1.5em} &\downarrow \uparrow & & \downarrow \uparrow & \hspace{-1.5em} {#1}_{#5}\\
& #3\block{#4} & \underset{#3\block{#6}}\longrightarrow & #3\block{#5} & \\
\end{matrix}
}
\newcommand{\cone}[1]{\mathcal{#1}}
$$
Saddle-Point Systems
General saddle-point systems factor as:
\[\mat{K & -A^T\\ -A & -C} =
\mat{I & \\ -A\inv{K} & I} \mat{K & \\ & -A\inv{K}A^T -C } \mat{I & -\inv{K}A^T \\ & I}\]
We denote the Schur complement by \(S=A\inv{K}A^T +C\). Letting \(C =
0\), a general dual preconditionner \(W\) acts on \(-A\inv{K}A^T\) and
expands to:
\[\mat{I & \\ -A\inv{K} & I} \mat{I & \\ & W} \mat{I & \\ A\inv{K} & I} = \mat{I & \\ (W - I) A\inv{K} & W}\]
The preconditioned saddle-point system has dual part
\(-WA\inv{K}A^T\), which expands to:
\[\mat{I & \\ (W - I) A\inv{K} & W}\mat{K & -A^T\\ -A & 0} = \mat{K & -A^T \\ -A & (I-W)A\inv{K}A^T}\]
It is positive definite whenever \(-W A\inv{K}A^T > 0\)
Cholesky
From the above, a \(LDL^T\) Cholesky decomposition of a KKT system is the following:
\[\mat{K & -A^T\\ -A & -C} =
\mat{I & \\ -A\inv{K} & I} \mat{L_K D_K L_K^T & \\ & -L_S D_S L_S^T } \mat{I & -\inv{K}A^T \\ & I}\]
In other words, we get:
\[\begin{align}
\mat{K & -A^T\\ -A & -C} &=
\mat{L_K & \\ -A\inv{K}L_K & L_S} \mat{D_K & \\ & -D_S} \mat{L_K^T & -L_K^T \inv{K}A^T \\ & L_S^T} \\
&= \mat{L_K & \\ -A L_K^{-T} & L_S} \mat{D_K & \\ & -D_S} \mat{L_K^T & -L_K^{-1} A^T \\ & L_S^T} \\
\end{align}\]
Misc.
The inverted system is:
\[\mat{K & -A^T\\ -A & -C}^{-1} =
\mat{I & \inv{K}A^T \\ & I} \mat{K^{-1} & \\ & -\block{A\inv{K}A^T + C}^{-1} } \mat{I & \\ A\inv{K} & I}\]
Also:
\[\mat{K & -A^T \\ -A & -C} \mat{0 \\ -z} = \mat{A^Tz \\ Cz}\]
can be used to optimize solves where the right-hand side has the above
form in order to optimize \(A^Tz\) computation.
e-mail comments/suggestions