Solve linear system with bordered positive definite matrix

Question

I want to solve the usual $A x = b$ system. In block form:

$$ \begin{bmatrix} B & c \\ c^{T} & 0 \end{bmatrix} \begin{bmatrix} x' \\ x_{n+1} \end{bmatrix} = \begin{bmatrix} b' \\ b_{n+1} \end{bmatrix}$$

where

• $B \in \mathbb{R}^{n \times n} $ is a positive definite matrix
• $c \in \mathbb{R}^{n}$
• $x,b \in \mathbb{R}^{n+1}$, so $x',b' \in \mathbb{R}^{n}$ and $x_{n+1},b_{n+1} \in \mathbb{R}$

Matrix $A$ is neither positive definite nor positive semidefinite.

I am not aware of well-known methods such as Cholesky or $LDL^T$ to solve this. Is there an efficient method to tackle this problem?

Answer 1

By combining the useful comments of Rodrigo and Todd, the methodology to solve this system is shown here below. One caveat is that the method is probably not very efficient, since you need to use the decomposition of $B$ two times to find the final solution.

1. Build Equations with Schur Complement

By using Schur Complement on the original problem, one can obtain the following system:

$$ \left\{\tag{1} \begin{array}{c} B x' = b' - x_{n+1} c\\ c^T B^{-1} (b' - x_{n+1} c) = b_{n+1} \\ \end{array} \right. $$

2. Compute $\eta^T$

1. Compute $\eta$ using the equation $B \eta = c$. This can be done with Cholesky or similar methods since B is positive definite.
2. Transposing the equation $B \eta = c$ leads to $\eta^T B = c^T$ since $B$ is symmetric. Now it is possible to rewrite the equation as $$\eta^T = c^T B^{-1} \tag{2}$$.

3. Combine

1. Replace $(2)$ in second equation of $(1)$, expand and simplify to compute $x_{n+1}$:

$$ x_{n+1} = \frac{\eta^T b' - b_{n+1}}{\eta^T c} $$

2. Replace the value of $x_{n+1}$ in first equation of $(1)$ to find $x'$ with regular decomposition methods.