This is really a matrix problem, but the theory I believe lies in graphs. Consider some matrix $A$ and permutation matrix $P$, where we define $\tilde{A}:= PAP^T$. I want to pick $P$ such that if $\tilde{A} = L + D + U$, for (strictly) lower triangular, diagonal, and (strictly) upper triangular pieces, respectively, I minimize $\|U\|/\|L\|$ in some norm (Frobenius, $\ell^2$,...). In some cases, $A$ may be a DAG (with self-loops on the diagonal), and so a topological sort would yield $\|U\| = 0$. In other cases, $A$ is symmetric, so regardless of $P$, we should always have $\|U\|/\|L\| = 1$. To solve this exactly I believe is NP-hard, but I just need a reasonable approximation that is cheap to compute (at least as cheap as computing direct $A^{-1}$, preferably much cheaper).

This is essentially a minimum feedback arc set problem, but approximating the FAS problem is typically posed by eliminating cycles. Here, $A$ is usually going to be dense/fully connected. Broadly, my question is if using FAS approximation algorithms makes sense on a fully connected graph, if certain methods may make more sense than others, or if there is a different/better way to pose this problem?

  • $\begingroup$ In case this is of use to anyone else, I implemented one of the early algorithms from Eades et al. (citeseerx.ist.psu.edu/viewdoc/…) and applied it to random matrices, where I scale the lower and upper triangular parts by some constant, then randomly shuffle the matrix $P^TAP$. Overall it is quite reliable in providing good approximations and has the correct limiting behavior of doing a topological sort if $A$ is a DAG and of course having a ratio of 1 for a symmetric matrix. There are probably better more recent options, but this works well. $\endgroup$ – Ben Southworth Oct 8 '20 at 22:54

Your Answer

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

Browse other questions tagged or ask your own question.