Research in Progress: Nested Dissection Sparse QR Factorization

I am especially curious about sparse QR factorization because it works effectively on nonsymmetric matrices, does not usually require pivoting for numerical stability, and does not break down merely because a matrix is indefinite. Conditioning still matters for accuracy, but indefiniteness alone does not cause the small-pivot failures seen in some other factorizations. I have some questions about the algorithm which I am actively working to answer:

1. Can a nested dissection approach improve parallelism and data locality for sparse QR factorization?
2. Can I use nested dissection to define a sparse QR factorization recursively? (This may lead to easier proofs of key facts.)
3. Can large blocks of fill-in be compressed, for example with randomized SVD?
4. Can a compressed/approximate version of this factorization function as a good preconditioner to GMRES?

My preliminary answers to these questions are:

1. Yes
2. I think so
3. It seems so, but needs more experimentation on different matrices
4. If (1) and (3) are true, then very likely.

Answering these questions requires a hefty dose of not just numerical linear algebra, but graph theory. Direct methods require deep graph theory on top of numerical linear algebra. “Divide and conquer” strategies common for dense linear algebra simply will not work in the sparse case because applying them naively results in explosively large memory requirements. Judicious use of graph theory algorithms can help preserve sparsity and keep memory needs under control.

I have not fully answered all the above questions, but I continue to work on them. I may upload a paper to arXiv describing my findings. In the meantime I made a movie of a sparse QR factorization as it processes a 2D Laplacian matrix which has already been reordered by a few steps of nested dissection. These movies can help explain what is going on and why fill-in occurs where it does.

I will update my blog as I learn more.