Fast Direct Solvers for Structured Linear Systems of Equations

In this dissertation we study a class of fast direct solvers for discretized linear systems by taking advantage of certain low-rank property and using some semi-separable structures. For linear systems arising from certain partial differential equations such as elliptic equations we discover that during the Gaussian eliminations of the matrices with proper ordering, the fill-in has a low-rank property: all off-diagonal blocks have small numerical ranks with proper definition of off-diagonal blocks. Matrices with this low-rank property can be efficiently approximated with some semi-separable structures, including sequentially semi-separable (SSS) representations and hierarchically semi-separable (HSS) representations by Chandrasekaran, Gu, et al. We generalize these semi-separable representations and improve some of their existing operations. We reveal the above low-rank property by ordering the variables with nested dissection and eliminating them with the multifrontal method. The low-rank property arises in various places during the multifrontal method when certain rules are applied in the ordering and elimination of variables. All related matrices are then represented in SSS or HSS forms. We propose efficient ways to naturally build compact semi-separable structures along the elimination. Moreover we develop a complete set of flexible semi-separable matrix operations which can be used in many other applications. These semi-separable matrix operations are very efficient for problems where off-diagonal blocks of matrices have small numerical ranks. By taking advantage of the low-rank property and SSS or HSS structures in the multifrontal method our new solvers can be shown to have linear complexity and to require only linear storage. We therefore call the methods superfast multifrontal methods with SSS or HSS structures. They are especially suitable for large problems, and also have great potential to provide effective preconditioners. We have developed a software package for the semi-separable matrix operations and the fast solvers. Numerical results demonstrate the efficiency.