3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 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$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes but then your domain of convergence is smaller $\endgroup$
    – Max Behr
    Aug 20 '15 at 19:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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