H²-matrix preconditioners for integral and elliptic partial differential equations

最近发展起来的H-矩阵方法可以用来构造椭圆型偏微分方程和积分方程的有效求解器。当考虑具有不连续或各向异性系数的微分方程时，这种方法特别鲁棒，例如，出现在复合材料的模拟中。一个H矩阵通常需要O（nk log n）的存储单元，其中n是矩阵维数，k取决于线性系统的条件数和所需的近似精度。H²矩阵联合收割机将H矩阵技术与多级结构相结合，以便将存储需求减少到O（nk），并处理更大的线性系统。数值实验表明，H²-矩阵确实比H-矩阵需要更少的存储空间，但现有的算法的建立时间不如H-矩阵。本研究旨在开发一种新的、更有效的H²-矩阵求解器的构造方法。该方法基于一种新的算法，该算法对线性H²矩阵进行局部低秩更新，即，最优的复杂性这种灵活的新算法可用于更有效地构造微分和积分方程的预条件子，也有望为H²-矩阵集合上其他算术运算的高效技术的发展铺平道路。

The recently developed H-matrix method can be used to construct efficient solvers for elliptic partial differential equations and integral equations. This approach is particularly robust when considering differential equations with discontinuous or anisotropic coefficients, e.g., appearing in simulations of composite materials. An H-matrix usually requires O(n k log n) units of storage, where n is the matrix dimension and k depends on the condition number of the linear system and the desired accuracy of the approximation.H²-matrices combine the H-matrix technique with multilevel structures in order to reduce the storage requirements to O(n k) and handle significantly larger linear systems. Numerical experiments show that H²-matrices indeed require less storage than their H-matrix counterparts, but the setup time of currently existing algorithms compares unfavorably to those for H-matrices.This research project focuses on developing a new, more efficient method for the construction of H²-matrix solvers. The approach is based on a new algorithm that performs local low-rank updates for H²-matrices in linear, i.e., optimal, complexity. This flexible new algorithm can be used to construct preconditioners for differential and integral equations more efficiently and it is also expected to pave the way for the development of efficient techniques for other arithmetic operations in the set of H²-matrices.