1
$\begingroup$

Let $A$ be a symmetric matrix. It is then well known that computing the LU factorisation of $PAP^T$ instead of $A$ for a suitably chosen permutation matrix $P$ can greatly reduce fill-in. My question is: Can we show that considering nonsymmetric permutations, i.e. $PAQ^T$, cannot reduce fill-in even further?

$\endgroup$
4
  • 2
    $\begingroup$ If $A$ is a symmetric matrix, then you wouldn't do an LU decomposition, but an $LL^T$ (Cholesky) decomposition. It would make sense to assume that in that case, a symmetric permutation is useful because if you use a different $P$ and $Q$, the resulting matrix is no longer symmetric and you need to go back to an LU decomposition -- spending at least twice the memory and compute time. $\endgroup$ Feb 15 at 14:56
  • $\begingroup$ Which I would happily accept if doing so shaves off a factor 100 for the fill-in. $\endgroup$
    – gTcV
    Feb 16 at 10:05
  • 1
    $\begingroup$ I remember a theorem which basically states that for symmetric matrices A, minimum bandwidth permutation is also symmetric, though I don't remember the source. However, it is the basis of using approximate permutations like symrcm and symamd on symmetricized patterns of non-symmetric matrices to get good approximations. Also, if my memory isn't betraying me, symamd outperforms colamd when tested on matrices from Harwell-Boeing collection and SuiteSparse matrix collection. $\endgroup$ Feb 18 at 4:16
  • $\begingroup$ This paper contains a discussion on ordering symmetric matrices. In general, algorithms designed for symmetric matrices are better than nonsymmetric. He notes an exception when you have specific knowledge of how $A$ was constructed. If $A = M^T M$, where $M$ may be rectangular, then performing the column permutation on $M$ will often yield better results. Its still a symmetric permutation, but uses nonsymmetric algorithms. citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Charlie S
    Feb 19 at 17:09

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.