When solving a system of linear equations $Ax = b$, where $A$ is square and sparse, I've seen an almost 3x speedup in Matlab when the Approximate Minimum Degree (AMD) reordering is used before doing the LU decomposition.
I'm wondering if there has been any developments on better reordering schemes than AMD, or any "pre-processing" step in general that accelerates the LU decomposition. In my work $A$ is usually not positive definite or perfectly symmetric, so I can't just use Cholesky instead.
An example of an $A$ I'm dealing with is shown below (before and after AMD):
Thanks in advance!
Finding the fill-in minimizing ordering is NP-Hard, which means that it is extremely unlike that there exists an algorithm which is guaranteed to find the best reordering of a sparse matrix efficiently in every case. For nonsymmetric problems, the issue is even more severe as one has to reorder the rows and columns of the matrix both to reduce fill-in and to maintain numerical stability (as using a small pivot can significantly erode the accuracy of an $LU$ factorization). (There are some nonsymmetric problems like row-column diagonally dominant ones where this issue is less important.) There are some problems which provably don't have an ordering so that $A = LU$ can be computed in time proportional to $\operatorname{nnz}(A)$.
That said, very good software exists to find good elimination orderings for sparse matrices (e.g. Metis). Well-written sparse direct solvers like UMFPACK (which is the backend behind MATLAB's \ operation) are very efficient for most sparse problems and balance both the accuracy and fill-in reducing aspects of nonsymmetric $LU$. For any "real life computation", I would use a well-established software library as rapidly and accurately solving a sparse linear system is a delicate subject.