I'm trying to solve a 2D poisson equation by finite differences.  In the process, I obtain a sparse matrix with only 5 variables in each equation, For example, if the variable were U, then the discretization would yield:  $U_{i-1,j} + U_{i+1,j} -4U_{i,j} + U_{i,j-1} + U_{i,j+1} = f_{i,j}$  I know that I can solve this system by an iterative method, but the thought occurred to me that if I ordered the variables appropriately, I might be able to obtain a banded matrix which could be solved by a direct method (i.e. gaussian elimination w/o pivoting).  Is this possible?  Are there any strategies for doing this for other, perhaps less structured sparse systems?
How to reorder variables to produce a banded matrix of minimum bandwidth?
pde;linear algebra;finite difference;banded matrix
This is a well-studied problem in the field of sparse-direct solvers. I highly recommend reading Joseph Liu's overview of the multifrontal method in order to get a better idea of how reorderings and supernodes effect fill-in and solution time.Nested dissection is an extremely common way to generate the reordering, and essentially consists of recursive graph partitioning. MeTiS is the de facto standard for graph partitioning, and you can read about some of the ideas behind it here. Another commonly used package is SCOTCH, and Chaco is also important, as its authors introduced multi-level graph partitioning, which is also the fundamental idea behind MeTiS.George and Liu showed in their classic book  that 2d sparse-direct solutions only require $O(n^{3/2})$ work and $O(n \log n)$ memory, while 3d sparse-direct requires $O(n^2)$ work and $O(n^{4/3})$ memory.