# Nonsymmetric permutations for LU factorisation of symmetric matrix

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?

• 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. Feb 15 at 14:56
• Which I would happily accept if doing so shaves off a factor 100 for the fill-in.
– gTcV
Feb 16 at 10:05
• 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. Feb 18 at 4:16
• 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/… Feb 19 at 17:09