Let $A$ be a square $n \times n$ matrix, which is invertible. Now we want to find the $i$-th column of $A^{-1}$ and one $(i,j)-$ entry of $A^{-1}$. Is there any way to compute only a small of portion of the entries in $A^{-1}$?
-
1$\begingroup$ Peter, do you want an exact method or an approximate one? $\endgroup$– SuvritApr 15, 2011 at 14:07
-
1$\begingroup$ It is the solution of a system of linear equations. $\endgroup$– Gerald EdgarApr 15, 2011 at 14:16
-
1$\begingroup$ Peter, if you want specific suggestions how to do what you want to do efficiently, it will be inevitable that you specify at least how large n is (roughly), what type of matrix A is (say, many zeros, yes or no), and perhaps what the entries of A are (reals, complex, rationals, something else). Otherwise, you can an only expect general information, which you already got. $\endgroup$– user9072Apr 15, 2011 at 14:28
-
1$\begingroup$ A is a real, large, sparse matrix whose entries are between 0 and 1. $\endgroup$– peterApr 15, 2011 at 16:43
4 Answers
The inverse of a matrix is the adjoint divided by the determinant. So what you want to compute is the determinant of an $(n-1) \times (n-1)$ submatrix, divided by the determinant of your original matrix.
Asymptotically, this won't be much saving, if any, over just inverting $A$, but it might be easier to think about, or might be simpler for matrices with a special form.
Also, if you care about efficiency, remember that you should never compute a determinant, or an inverse, by summing over all $n!$ permutations! Use row reduction or, better, use a good linear algebra library.
-
$\begingroup$ yeah, computing $|A|$ is unwise, too costly. Any other efficient way? $\endgroup$– peterApr 15, 2011 at 13:33
If you are willing to settle for an approximate answer, then have a look at the paper:
Z. Bai, M. Fahey and G. Golub, Some large-scale matrix computation problems Journal of Computational and Applied Mathematics, Volume 74, Issues 1-2, 5 November 1996, Pages 71-89. Link to PDF
That paper studies simple randomized methods for estimating
$$u^Tf(X)v,$$
where $f(X)$ is a matrix function. In your case, $f(X) = X^{-1}$. If you choose $u=e_i$ and $v=e_j$ (the standard basis vectors), then you can extract an approximation to $(X^{-1})_{ij}$.
In the meanwhile there is more related work, but if you are happy with these types of results that I can expand my answer to provide some more citations.
The ith column of $A^{-1}$ is $A^{-1}$ applied to the ith unit vector. So you can obtain it by solving a linear system. This question does not appear suitable for this site.
-
-
3$\begingroup$ actually, the question is suitable. Imagine the matrix $A$ is huge (say $10^6 \times 10^6$), then you do not necessarily want to solve a linear system if you just want to extract a few elements of the inverse. Of course, now the onus is on Peter to refine his question with more details of what exactly he is seeking. $\endgroup$– SuvritApr 15, 2011 at 14:16
To amplify on @Michael Renardi's answer: finding $x$ such that $A x = y$ (in this case, $y$ is a unit vector) is generally much faster than finding $A^{-1},$ the key words are "conjugate gradient algorithm. I do not understand the question about the $(i, j)$th entry, since once you fiund the column (or the row, by taking transposes) you can find your element.
-
$\begingroup$ In fact, the key words are "conjugate gradient if it is symmetric, GMRES otherwise". $\endgroup$ Apr 15, 2011 at 17:12