# Fill-reducing ordering for computing the matrix product $A^T A$?

I have found many libraries for reducing filling when dong Cholesky factorisation on sparse matrices. However, I want to do fill-reduction for a different reason - given a $$m\times n$$ matrix $$A,$$ I want to find a permutation matrices $$P,Q$$ such that $$B=PAQ$$ satisfy the property that $$B^\ast B$$ is as sparse as possible. This is useful for, for instance, finding singular values, or solving optimisation problems.

Is there a fill-reduction library for the purpose I describe?

• If $A$ is sparse could you not instead implement the matrix vector product with $A^TA$ through $y=Ax$ and $z=A^Ty$ and then $z=A^TAx$ as desired? As long as you're using iterative methods you can use this. Looking for a sparsity promoting fill-reducing ordering sounds like a much harder and computationally more expensive problem. Commented Feb 29 at 22:17
• @lightxbulb Thank you for the suggestion. But I want to SOLVE linear system of the form $A^TAx = b.$ Does your method here work? Commented Mar 1 at 7:28
• Insofar as you use an iterative solver that requires products with $A^TA$ it does work. Are you by chance solving the normal equations $A^TAx=A^Tc$? If yes then look up CGNR/CGLS/LSQR. If not then you can maybe still use those, you just need to modify the first step to not apply the $A^T$ to $b$. Or you can use just the conjugate gradient solver with the matrix-vector multiplication as described. Commented Mar 1 at 9:02

That is not possible. If $$P$$ and $$Q$$ are permutation matrices, then their inverses, respectively, are $$P^T$$ and $$Q^T$$. Also note that, applying permutations to a matrix $$A$$ doesn't change its number of nonzeros (which is intuitively trivial, but has a slightly long proof which I am going to skip).
Now, let $$B=PAQ$$ and consider $$B^TB = Q^TA^TP^TPAQ = Q^TA^TAQ.$$ So $$B^TB$$ is $$A^TA$$ symmetrically permuted and we can conclude $$B^TB$$ has the same number of nonzeros as $$A^TA$$.