Robust Structured Multifrontal Preconditioning For Discretized

We present a preconditioning technique based on an approximate structured factoriza-tion method which is efficient, robust, and also relatively insensitive to ill conditioning, high frequencies, or wave numbers for some discretized PDEs. The factorization fully integrates graphical sparse matrix techniques, rank structures of fill-in, and automatic robustness enhancement techniques. The factorization has controllable accuracy and can work as an effective black-box preconditioner. In iterative methods for solving large discretized PDEs arising from practical problems, classical preconditioners such as incomplete factorization or orthogonalization methods can break down due to numerical instability. In this work, we present a reliable and effective preconditioner based on structured data compression with any specified accuracy. Consider a symmetric positive definite matrix A arising from the discretization of certain PDEs. A is usually large and sparse. In the Cholesky factorization A = LLT, new nonzeros or fill-in are introduced into L. One way to reduce fill-in is to reorder the rows and columns of A. For example, for an N ×N regular mesh, the factorization with the nested dissection ordering [8] and its generalizations take O(n3/2) flops and O(n log n) storage