Minimum Completion Time Criterion for Parallel Sparse Cholesky Factorization

It is well known that a judicious choice of ordering has great impact on the sparse matrix factorization. Many proposed reordering algorithms attempt to minimize the corresponding elimination tree height, which is, however, not an accurate indication of the actual parallel factorization time. We will illustrate the appalling discrepancy with a contrived example.