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$
  • $\begingroup$ Couldn't you use Cramer's rule? $\endgroup$ – abnry Apr 11 '18 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 '18 at 0:15
  • $\begingroup$ possibly related question: mathoverflow.net/questions/73028/… $\endgroup$ – Mahdi May 6 '18 at 18:46
10
$\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$
  • $\begingroup$ Interesting paper! Does this approach work in the case of indefinite or nonsymmetric matrices? $\endgroup$ – Mahdi Apr 11 '18 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 '18 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
    $\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 '18 at 12:09

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.