Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
3  
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. –  Zev Chonoles Feb 18 '13 at 16:16
add comment

1 Answer 1

up vote 4 down vote accepted

The sum of the element 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.

share|improve this answer
    
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 –  Gerhard Paseman Feb 18 '13 at 17:55
    
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. –  Federico Poloni Feb 18 '13 at 19:52
    
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. –  Dimitris Dakopoulos Feb 19 '13 at 10:31
    
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? –  Federico Poloni Feb 19 '13 at 10:44
    
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. –  Dimitris Dakopoulos Feb 19 '13 at 13:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.