Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces the fill in of $A + A^{−1}$. Is there some work, or is it hopeless?

  • 2
    $\begingroup$ $A^{-1}$ is often dense even when $A$ is sparse (e.g., tridiagonal matrices have dense inverses, and any general matrix whose graph is strongly connected), in which case there is nothing to reorder in $A+A^{-1}$, it's dense. Can you give more context to make this question more clear/relevant to other people? What are you trying to accomplish? $\endgroup$
    – Kirill
    Aug 18, 2015 at 13:11
  • $\begingroup$ There is an iterative newton scheme to compute the $sign$ of a matrix $A$, where $A$ has no eigenvalues on the imaginary axis. The iteration is as follows: $A_{k+1}=A_{k}+A_{k}^{-1}$. Yes it is true that you take the inverse of $A$ explicitly. $\endgroup$
    – DerZwirbel
    Aug 18, 2015 at 13:58
  • $\begingroup$ With that iteration, $A_k$ (in general) becomes dense after one iteration, and the questions of fill-in and reordering become irrelevant. $\endgroup$
    – Kirill
    Aug 18, 2015 at 20:23
  • $\begingroup$ ok this means it is hopeless and we can close $\endgroup$
    – DerZwirbel
    Aug 18, 2015 at 20:51

1 Answer 1


You can avoid the explicit computation of $A^{-1}$ in the Newton iteration for the sign of $A$.

Refer to chapter 5 from this book by Higham, more specifically equation 5.22.

  • $\begingroup$ yes but then your domain of convergence is smaller $\endgroup$
    – DerZwirbel
    Aug 20, 2015 at 19:14

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.