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 by separating the graph recursively. This builds a nested block structure where interactions between subdomains pass through their separators. The “nested” part of nested dissection also produces a tree structure that exposes independent subproblems and therefore helps produce 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 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