1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Feb 29 at 22:17
  • $\begingroup$ @lightxbulb Thank you for the suggestion. But I want to SOLVE linear system of the form $A^TAx = b.$ Does your method here work? $\endgroup$
    – Ma Joad
    Commented Mar 1 at 7:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – lightxbulb
    Commented Mar 1 at 9:02

1 Answer 1

Reset to default
5
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Wow, great answer. That's so obvious and yet not very intuitive at the first thought. $\endgroup$
    – Ma Joad
    Commented Mar 1 at 7:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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