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

Improve this question
$\endgroup$
3
  • $\begingroup$ Couldn't you use Cramer's rule? $\endgroup$
    – abnry
    Commented 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
    Commented Apr 14, 2018 at 0:15
  • $\begingroup$ possibly related question: mathoverflow.net/questions/73028/… $\endgroup$
    – Mahdi - Free Palestine
    Commented May 6, 2018 at 18:46

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Interesting paper! Does this approach work in the case of indefinite or nonsymmetric matrices? $\endgroup$
    – Mahdi - Free Palestine
    Commented 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
    Commented 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.

Improve this answer
$\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
    Commented Apr 11, 2018 at 12:09

You must log in to answer this question.

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