On the theoretical and practical numerical performance of matrix-decomposition-based fast direct solvers

Fast direct solvers based on matrix-decomposition are studied theoretically and numerically for electromagnetic scattering problems. The study not only goes into the computational complexity of fast solvers, but also further into the coefficient before the computational complexity, which is also important, but often is ignored before. Two representative methods, the hierarchical matrix (H-matrix) and butterfly solvers are studied in detail. We show that although the butterfly solver has the better complexity of both the CPU and memory requirements compared with H-matrix, the actual performance is affected significantly by the coefficients in front of the complexity expressions. We find that the butterfly solver is always memory saving than the H-matrix one in practice, but even when the unknown grows bigger than millions, H-matrix still cost less time. We study the coefficients in front of the complexity expressions, and propose a hybrid matrix decomposition algorithm (HMDA) to compress the impedance matrix and its LU factors. Numerical results demonstrate that HMDA inherits the advantages of both approaches and can be implemented conveniently to make a tradeoff between the CPU and memory resource.