An Automatic One-Way Dissection Algorithm for Irregular Finite Element Problems
Alan D. George · SIAM Journal on Numerical Analysis · 1980
An algorithm for automatically finding a one-way dissection ordering for irregular finite element problems is described. Numerical experiments suggest that the amount of fill suffered by correspondingly ordered matrices, when factored, is $O(N^{5/4} )$, and that the amount of arithmetic required to perform the factorization is $O(N^{7/4} )$. The corresponding estimates for nested dissection orderings are $O(N\log N)$ and $O(N^{3/2} )$ respectively, so the one-way scheme is asymptotically inferior. However, experiments suggest that unless N is very large indeed, the one-way dissection orderings require considerably less storage than the nested dissection orderings, although the arithmetic requirements are larger.