1
$\begingroup$

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?

$\endgroup$
10
  • $\begingroup$ @RodrigodeAzevedo my original question was related to the vector with all ones, but then I forgot to specify it. I can keep the question I posted and keep it general like it is. $\endgroup$
    – fusiled
    Commented Jul 13, 2020 at 10:08
  • $\begingroup$ Have you tried using the Schur complement to "triangularize" the block matrix? Then, one would find $x_{n+1}$ and solve the smaller, $n$-dimensional linear system. Perhaps very inefficient. $\endgroup$ Commented Jul 13, 2020 at 10:11
  • $\begingroup$ @RodrigodeAzevedo Normal Schur complement cannot be applied because $0$ and $c$ are not invertible. Probably a Generalized Schur complement may help? But It requires to find the proper generalized inverse for $c$ $\endgroup$
    – fusiled
    Commented Jul 13, 2020 at 11:14
  • $\begingroup$ @RodrigodeAzevedo OK, I see your point, I have to rearrange the matrix a little to obtain the positive definite matrix in the form like here: en.wikipedia.org/wiki/…. Anyway it is also possible to use the pseudo-inverse (en.wikipedia.org/wiki/Generalized_inverse#Types) for the Schur complement, but it looks a bit more complicated. I am going to work evaluate your suggestion soon. $\endgroup$
    – fusiled
    Commented Jul 13, 2020 at 11:42
  • $\begingroup$ You can find $x_{n+1}$ using the Schur complement — of Cramer's rule, if you prefer. Then you have a linear system in $n$ unknowns. No need to invert anything. $\endgroup$ Commented Jul 13, 2020 at 12:03

1 Answer 1

2
$\begingroup$

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} $$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .