Accuracy Controlled Structure-Preserving H2-Matrix-Matrix Product in Linear Complexity With Change of Cluster Bases.

H2-matrix constitutes a general mathematical framework for efficient computation of both partial-differential-equation (PDE) and integral-equation (IE)-based operators. Existing linear-complexity H2 matrix-matrix product (MMP) algorithm lacks explicit accuracy control, while controlling accuracy without compromising linear complexity is challenging. In this article, we develop an accuracy controlled H2 MMP algorithm by instantaneously changing the cluster bases during the matrix product computation based on prescribed accuracy. Meanwhile, we retain the computational complexity of the overall algorithm to be linear. Different from the existing H2 MMP algorithm where formatted multiplications are performed using the original cluster bases, in the proposed algorithm, all additions and multiplications are either exact or computed based on prescribed accuracy. Furthermore, the original H2-matrix structure is preserved in the matrix product. While achieving optimal complexity for constant-rank matrices, the computational complexity of the proposed algorithm is also minimized for variable-rank H2-matrices. For example, it has a complexity of O(NlogN) for computing electrically large volume IEs, where N is matrix size. The proposed work serves as a fundamental arithmetic in the development of fast solvers for large-scale electromagnetic analysis. Applications to both large-scale capacitance extraction and electromagnetic scattering problems involving millions of unknowns on a single core have demonstrated the accuracy and efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]