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?
3
$\begingroup$
$\endgroup$
-
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 '15 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$ – Max Behr Aug 18 '15 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 '15 at 20:23
-
$\begingroup$ ok this means it is hopeless and we can close $\endgroup$ – Max Behr Aug 18 '15 at 20:51
2
$\begingroup$
$\endgroup$
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$ – Max Behr Aug 20 '15 at 19:14
