# Sparse Matrix Reordering

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?

• $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? – Kirill Aug 18 '15 at 13:11
• 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. – Max Behr Aug 18 '15 at 13:58
• With that iteration, $A_k$ (in general) becomes dense after one iteration, and the questions of fill-in and reordering become irrelevant. – Kirill Aug 18 '15 at 20:23
• ok this means it is hopeless and we can close – Max Behr Aug 18 '15 at 20:51

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