1
$\begingroup$

Given a large (say 10x10) sparse Hermitian matrix with symbolic entries, I need four specific entries of the inverse matrix. It seems wasteful to me to compute 100 entries of which I only need a few in the end.

Is there a way to compute a small number of specific entries of the inverse matrix that is significantly more efficient than finding the inverse matrix and then extracting the elements?

Here's an example. N is half the dimension of the matrix. For N = 8, inverting takes 51 seconds on my university's computer, and we would ideally like to reach much larger N.

A = Table[If[Abs[i - j] == 1, (j - i) a, 0], {i, #}, {j, #}] &;
B = Table[If[Abs[i - j] == 1, b, 0], {i, #}, {j, #}] &;

σ1[N_] := B@N + Table[
    If[Abs[i - j] == 0, 2 μ, 0] + If[i == j == 1, -x, 0] + 
     If[i == j == N, -x, 0]
    , {i, N}, {j, N}];
σ2[N_] := -B@N + Table[
    +If[i == j == 1, -y, 0] + If[i == j == N, -y, 0]
    , {i, N}, {j, N}];

(* Elements of M *)
el[N_, i_, j_] := Which[i <= N && j <= N,
  σ1[N][[i, j]], i > N && j > N,
  σ2[N][[i - N, j - N]], i > N && j <= N,
  A[N][[i - N, j]], i <= N && j > N,
  -A[N][[i, j - N]]] 

M[N_] := Table[el[N, i, j], {i, 2 N}, {j, 2 N}];

Daniel Lichtblau's idea LinearSolve[M@8,UnitVector[16,8]] takes 4.1 seconds, so it is certainly much faster than inverting the entire matrix, even if it has to be done seperately for each entry.

$\endgroup$
7
  • 2
    $\begingroup$ If you have ACM access, search for Lin Lin et al SelInv paper. $\endgroup$
    – ciao
    Commented Mar 24, 2014 at 21:22
  • 1
    $\begingroup$ As it is stated, the Q is off-topic. $\endgroup$
    – Sektor
    Commented Mar 24, 2014 at 21:43
  • 1
    $\begingroup$ @bobthechemist I have to disagree here. It is clear that you can do an Inverse matrix calculation in Mathematica, and checking to see whether a fast version of Inverse[m][[{3,4},{2,1}]] exists is not unreasonable. It can be very advantageous. Many functions in Mathematica can be 'cut-off' to stop early and give a restricted set of solutions. Take, for instance, Ordering or Position. $\endgroup$ Commented Mar 24, 2014 at 22:28
  • 6
    $\begingroup$ LinearSolve[mat,ej] will give the jth column only of the inverse, when ej is the jth coordinate axis unit vector. I would expect that to be 2-3 times faster than using Inverse. $\endgroup$ Commented Mar 24, 2014 at 22:37
  • 1
    $\begingroup$ For multiple right hand sides, maybe do 'LinearSolve[mat]' and use the resulting 'LinearSolveFunction' on different vectors. $\endgroup$ Commented Mar 31, 2014 at 3:22

1 Answer 1

3
$\begingroup$

Looking at http://en.wikipedia.org/wiki/Matrix_inverse, the lines below avoid calculating more than needed (less than 1 sec on M[8]):

Cofactor[mat_,i_,j_]/;(And@@Thread[{i,j}<=Dimensions[mat]]):=(-1)^(i+j)*Det[Drop[#,{j}]&/@Drop[mat,{i}]];   
inverseElement[mat_, i_,  j_] /; (And @@ Thread[{i, j} <= Dimensions[mat]]) := 
 Cofactor[mat, j, i]/Det[mat];
$\endgroup$

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.