Inverse of a small submatrix

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

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

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.
• @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 – Suvrit Apr 11 '18 at 20:49
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.
• When $| \cal I| \sim 1000$, the method seems efficient. But what if $| \cal I| \ll 1000$ ? In this example, $| \cal I| = 3 \ll 1000$. – John Smith Apr 11 '18 at 12:09