论文标题
有效地构建HSS预处理，用于对称正定确定$ \ MATHCAL {H}^2 $矩阵
Efficient construction of an HSS preconditioner for symmetric positive definite $\mathcal{H}^2$ matrices
论文作者
论文摘要
在求解具有不良条件的，对称正定（SPD）内核矩阵的迭代方法中，需要快速矩阵矢量产物和快速的预处理操作。通过在$ \ MATHCAL {H}^2 $表示或等效的快速多极方法表示中表达内核矩阵，可以通过表达内核矩阵来获得快速（线性尺度）矩阵矢量产物。但是，对此类矩阵的预处理需要一个结构化的矩阵近似值，该矩阵近似比$ \ Mathcal {h}^2 $表示更常规，例如层次上的半序列（HSS）矩阵表示，该表示提供快速求解操作。以前，提出了一种算法，以构建与SPD的SPD内核矩阵构建HSS近似值。但是，该算法具有二次成本，仅用于定义内核矩阵的点的递归二元分区。本文提出了一种用于构建SPD HSS近似值的一般算法。重要的是，该算法使用SPD矩阵的$ \ MATHCAL {H}^2 $表示，以将其计算复杂性从二次降低到Quasilinear。数值实验说明了该SPD HSS近似如何作为求解由一系列内核函数引起的线性系统的预处理。
In an iterative approach for solving linear systems with ill-conditioned, symmetric positive definite (SPD) kernel matrices, both fast matrix-vector products and fast preconditioning operations are required. Fast (linear-scaling) matrix-vector products are available by expressing the kernel matrix in an $\mathcal{H}^2$ representation or an equivalent fast multipole method representation. Preconditioning such matrices, however, requires a structured matrix approximation that is more regular than the $\mathcal{H}^2$ representation, such as the hierarchically semiseparable (HSS) matrix representation, which provides fast solve operations. Previously, an algorithm was presented to construct an HSS approximation to an SPD kernel matrix that is guaranteed to be SPD. However, this algorithm has quadratic cost and was only designed for recursive binary partitionings of the points defining the kernel matrix. This paper presents a general algorithm for constructing an SPD HSS approximation. Importantly, the algorithm uses the $\mathcal{H}^2$ representation of the SPD matrix to reduce its computational complexity from quadratic to quasilinear. Numerical experiments illustrate how this SPD HSS approximation performs as a preconditioner for solving linear systems arising from a range of kernel functions.
