# Efficiently factorize a KKT system with block diagonal upper corner

I have a system resulting from a quadratic energy minimization with linear equality constraints enforced with Lagrange multipliers which has the form:

\begin{equation} A = \left[\begin{array}{c|c} \tilde{Q}&B^T \\ \hline B&*\\ \end{array}\right] = \left[\begin{array}{ccccc|c} Q & *& *& *&* \\ *& Q &*&*&* \\ *&*& \ddots&*&*& B^T\\ *&*&*& Q& * \\ *&*&*& *&Q \\ \hline & &B& & &*\\ \end{array}\right] , \end{equation} where $*$ means all zeros.

Let's say that $Q$ is a symmetric positive-definite $n$ by $n$ matrix and $B$ is $n*k$ by $m$ and full column rank. Both are sparse (small number of non-zeros per row).

I can factorize $A$ using sparse LDL decomposition but this doesn't take advantage of the repeated nature of the upper left corner.

Knowing that a factorization of $\tilde{Q}$ will just be a repeated block diagonal made up of factorizations of $Q$, I tried using the Schur complement method, but then it seems I need to factorize $B \tilde{Q}^{-1} B^T$ which could be dense.

Is there a way to build a LU-style factorization for $A$ (for efficient solving) which takes advantage of both the sparsity of $Q$ and $B$ and the repeated block diagonal in $\tilde{Q}$?

• I don't see why a Schur complement involves $BA^{-1}B^T$; shouldn't it be $B\tilde{Q}^{-1}B^T$, which should be computable efficiently? I assume that $m$ is small enough that you can store it densely? – Victor Liu Apr 24 '14 at 16:07
• You're right, that was a typo. But no, $m$ could be large perhaps even $m=n$ which for us could be >100,000. Where the number of non-zeros per row would be more like 10. – Alec Jacobson Apr 24 '14 at 18:11
• You might consider looking on this Acta Numerica paper and find what suits your problem the most. If the Schur complement $B\tilde{Q}^{-1}B^T$ is well-conditioned, you can try to solve $B\tilde{Q}^{-1}B^T$ iteratively. Note that as you need to implement only the matrix-vector product for the Schur complement, you don't need to form it explicitly. Also, if $B\tilde{Q}^{-1}B^T$ is dense, then the $LDL^T$ factorisation will most likely compute dense $L$ factor too. – Algebraic Pavel May 5 '14 at 16:25
• @PavelJiranek, the about $LDL^T$ being dense, won't the reordering (try to) mitigate this? – Alec Jacobson May 5 '14 at 16:37
• It's possible. There are some references, e.g., here and here. It really depends on the application (in particular, the structure of $B$. – Algebraic Pavel May 5 '14 at 16:45