0
$\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 Jul 13 '20 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$ – Rodrigo de Azevedo Jul 13 '20 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 Jul 13 '20 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 Jul 13 '20 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$ – Rodrigo de Azevedo Jul 13 '20 at 12:03
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.