11
$\begingroup$

Let $A$ be a large matrix (say, $1000 \times 1000$), and let $\mathcal I = \{2,3,5\}$ be a set of row/column indices. Let $(A^{-1})_{\cal I \times I}$ denote the submatrix of $A^{-1}$ that consists of the $\{2,3,5\}$ rows and columns of $A^{-1}$.

Is there an efficient way of computing the following $3 \times 3$ matrix inverse $((A^{-1})_{\cal I \times \cal I})^{-1}$ without inverting the large matrix $A$?

$\endgroup$
3
  • $\begingroup$ Couldn't you use Cramer's rule? $\endgroup$
    – abnry
    Apr 11, 2018 at 17:19
  • $\begingroup$ @abnry one can also use Cramer's rule here, if the determinant of $A$ is known (which presumably is not known here). $\endgroup$
    – Suvrit
    Apr 14, 2018 at 0:15
  • $\begingroup$ possibly related question: mathoverflow.net/questions/73028/… $\endgroup$
    – Mahdi
    May 6, 2018 at 18:46

2 Answers 2

11
$\begingroup$

One way to go about this is as follows:

For $i,j \in \mathcal{I}$ Compute $e_i^TA^{-1}e_j$ by using the approach based on Gaussian quadrature; see for instance, a precise algorithm and analysis in our paper "Gauss quadrature for matrix inverse forms with applications."

Now that you have $[A^{-1}]_{\mathcal{I},\mathcal{I}}$, getting its inverse is an easy matter since $|\mathcal{I}|$ is small.

$\endgroup$
2
  • $\begingroup$ Interesting paper! Does this approach work in the case of indefinite or nonsymmetric matrices? $\endgroup$
    – Mahdi
    Apr 11, 2018 at 14:50
  • $\begingroup$ @Mahdi indefinite should be easy as long as symmetry / hermitian property is preserved (by adding $\lambda I$ to the matrix to ensure psd-ness for sufficiently large $\lambda$); for non-symmetric matrices, I don't recall an obvious idea right away, but you may find more related work e.g., on N. Higham's page: maths.manchester.ac.uk/~higham/papers $\endgroup$
    – Suvrit
    Apr 11, 2018 at 20:49
4
$\begingroup$

Let me denote $B=A^{-1}$. The question is how to efficiently compute the inverse of a submatrix of $B$ given the fact that the inverse of the full matrix $B$ is known (since $B^{-1}=A$). An efficient algorithm for this task is given in Relationship between the Inverses of a Matrix and a Submatrix.

$\endgroup$
1
  • 1
    $\begingroup$ When $| \cal I| \sim 1000$, the method seems efficient. But what if $| \cal I| \ll 1000$ ? In this example, $| \cal I| = 3 \ll 1000$. $\endgroup$
    – John Smith
    Apr 11, 2018 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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