4
$\begingroup$

Consider the symmetric matrix

$$M = \begin{bmatrix} A & B \\ B^T & -C \end{bmatrix}$$

where $A \in \cal{R}^{n \times n}$ and $C \in \cal{R}^{m\times m}$ are symmetric, positive semidefinite, highly sparse matrices.

Is there an efficient way of checking if the Schur complement

$$S = A + BC^{-1}B^T$$

is invertible by looking at the properties of matrices $M$, $A$, $B$, $C$?

Inverting $C$ is expensive and the inverse of a sparse matrix is a full matrix, which is undesirable.

Thank you all.

Improve this question
$\endgroup$
2
  • $\begingroup$ if $n$ is much smaller than $m$, it would be more efficient to instead invert $A$, and find if $S$ is invertible by means of the identity ${\rm det}\,S={\rm det}(C+B^T A^{-1}B){\rm det}(A)/{\rm det}(C)$ $\endgroup$
    – Carlo Beenakker
    Commented Mar 17, 2017 at 7:05
  • 1
    $\begingroup$ While computing the full inverse $C^{-1}$, for the purpose of later using it in matrix multiplication, is expensive, it should be less expensive to computer the product $D = C^{-1} B^T$, by directly solving the linear system $CD = B^T$. Though, that may depend on the size of $B^T$. Then, use $S = A + BD$. $\endgroup$
    – Igor Khavkine
    Commented Mar 17, 2017 at 7:50

0

Reset to default

You must log in to answer this question.