Visualizing Nested Dissection

Sparse direct solvers involve a lot of graph theory on top of numerical linear algebra. The addition of graph theory can make it very challenging to build intuition. To help build my intuition for how things work I built a sequence of visualizations for different steps of nested dissection, a very useful matrix reordering strategy that reduces fill-in for factorizations. Nested dissection builds in a nested block structure where all potential fill-in from a factorization algorithm gets confined to the blocks and no fill-in can occur outside of the blocks. The “nested” part of nested dissection also produces a tree structure that helps for producing a parallel algorithm. I visualize both the tree structure and block structure here. I take a 2D Laplacian matrix and do 5 levels of nested dissection, visualizing each level.

Visualizing block structure and tree structure together

I visualize these together first

Dissection Level	Tree Diagram	Block Structure
0	Base case
1
2
3
4

Since the tree diagrams start to take a lot of space I also visualize both the trees and blocks separately below

Visualizing tree structure alone

Next I visualize the tree structure alone - to give the images more space

Dissection Level	Tree Diagram
0	Base case
1
2
3
4

Visualizing block structure alone

Similarly I visualize the block structure alone - to give the images more space

Dissection Level	Block Structure
0
1
2
3
4