Nested Dissection for Sparse QR Factorization (video)

February 07, 2021

I have wondered whether we can use nested dissection for QR factorization even though it is most commonly introduced for Cholesky or LU factorizations. It turns out the answer is yes: apply it to the column-intersection graph, which has the structure of the normal-equations matrix without requiring us to form the normal equations numerically. The resulting QR algorithm has really challenged me. I made a video outlining how and why it works. This does not represent the conclusion so much as a starting place for many more questions which I hope to answer.