3
$\begingroup$

Hello all,

Assume NxN matrix A of complex values. I want to calculate the sum of all elements of its inverse.

The problem is that calculating the inverse is computationally expensive and since I am looking only for the sum of its elements, I thought there might be something smarter to do.

Note: the real part of A is a diagonal matrix while the imaginary is a 2x2 block matrix of symmetric submatrices.

Thank you

Improve this question
$\endgroup$
1
  • 6
    $\begingroup$ This was crossposted to math.SE: math.stackexchange.com/questions/307177 . In the future, please wait some time before posting your question in multiple fora, and when you do, provide links to the other posts - as you can imagine, it would be frustrating for someone to put time into answering your question here, only to see hear from you that you'd already gotten the solution elsewhere. $\endgroup$
    – Zev Chonoles
    Commented Feb 18, 2013 at 16:16

1 Answer 1

Reset to default
11
$\begingroup$

The sum of the elements of a matrix $M$ is $e^T M e$, where $e$ is the vector of all ones.

So, instead of computing the inverse, you should solve the system $Ax=e$ and then compute $e^Tx$. This might look like a simple trick, but solving linear systems is faster than computing inverses in basically all settings.

Of course you should then use a method to solve this linear system which is appropriate to the matrix that you are dealing with (but there is a large amount of literature on that).

I don't think that you can get the quantity you want any faster than this, unless your matrix has very special properties.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Are there formulas which handle things like (D + iA)^-1 which might help? Or do you think solving the system will be quicker than such formulas on block matrices? Gerhard "Ask Me About System Design" Paseman, 2013.02.18 $\endgroup$
    – Gerhard Paseman
    Commented Feb 18, 2013 at 17:55
  • $\begingroup$ Good point. Probably in this case you can use an algebraic identity to decouple the real and imaginary part and so use real arithmetic instead of complex. Similarly, maybe the fact that the blocks are symmetric can be used to save some work in the solution of the linear system. But no, I don't think there is something substantially simpler than solving the linear system. $\endgroup$
    – Federico Poloni
    Commented Feb 18, 2013 at 19:52
  • $\begingroup$ Thank you for your suggestions. I guess, I should have mentioned that I do not calculate the inverse but I do solve the system $Ax=e$ using various LAPACK routines (e.g. ZGETRF for LU decomposition and ZGETRI for solving. Using this trick makes things faster. I also take advantage of the block symmetry in one of the multiplication. I will now check Federico's solution. $\endgroup$
    – Dimitris Dakopoulos
    Commented Feb 19, 2013 at 10:31
  • $\begingroup$ Ok, so it seems you already use the optimization I suggested. I don't expect any substantial speedup. I am quite dubious of your trick to avoid complex arithmetic though --- are you sure it really pays off? $\endgroup$
    – Federico Poloni
    Commented Feb 19, 2013 at 10:44
  • 1
    $\begingroup$ The trick does help, especially for larger matrices. In my case I deal with matrices approx 1000 x 1000. The trick is ~20-30% faster than the LU+Inversion. Summary: * Method A: LU factorization (zgetrf) and calculation of inverse (zgetri) * Method B: The trick that avoid complex number but I use LU and inversion for reals. * Method C (suggested): LU factorization, solution of system with identiy vectors $e$ and $e_T$ and calculation of sum as: $e_T x$ Some quick timings for 1000x1000 random matrix (with specific symmetries): A: 1.13", B: 0.81", C: 0.40" which is very decent speedup. $\endgroup$
    – Dimitris Dakopoulos
    Commented Feb 19, 2013 at 13:50

You must log in to answer this question.

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