The numerical solution of partial differential equations (PDE) is a key enabling technology in all disciplines of engineering and science. Nevertheless the numerical solution of three-dimensional PDEs is a critical bottle-neck that prevents this potential from being realized. This proposal advances techniques that can be used to overcome this bottle-neck. Discretized elliptic PDEs are normally solved by iterative schemes since the fill-in during sparse Gaussian elimination is excessive. This proposal observes that the fill-in, in a certain ordering, has low numerical rank in the off-diagonal blocks, and that this structure can be computed and exploited to construct direct solvers that are linear in the number of unknowns. The outcome of the proposed research has the potential to create a novel class of pre-conditioners that in conjunction with iterative solvers can become powerful weapons for solving difficult elliptic PDEs. The intellectual merit of the proposal stems from the complicated structure in the fill-in that must be first inferred from regularity results for Green's functions in elliptic PDE theory and then converted into effective linear-time algorithms to both capture the structure on the fly during sparse Gaussian elimination, and then exploited to speed up the very same Gaussian elimination. The impact of the proposal will be to provide new solvers for difficult PDEs. In particular thesoftware that is developed will be made available to the community, and should enable scientists and engineers to have a new tool for their difficult problems. It will also infuse fresh ideas into the field of sparse direct solvers and unify it with the field of iterative methods.
