论文标题
亲密关系的几何稀疏：用于计算矩阵函数的特征值聚类
Geometric Sparsification of Closeness Relations: Eigenvalue Clustering for Computing Matrix Functions
论文作者
论文摘要
我们展示了如何在评估矩阵功能的方法中有效解决聚类问题。该问题需要找到图形的连接组件，其顶点是真实或复杂矩阵的特征值，其边缘是彼此最多是ΔAway的成对的特征值。戴维斯（Davies）和海姆（Higham）提出了通过列举图表的边缘来解决此问题的问题，该图形至少需要$ω（n^{2}）$工作。我们表明，可以通过计算特征值的Delaunay三角剖分，从中删除长边，并计算三角调节中其余边缘的连接组件来解决问题。这导致$ O（n \ log n）$算法。我们已经使用CGAL（一个成熟且复杂的计算几何软件库）实现了这两种算法，我们证明了新算法在实践中比幼稚算法要快得多。我们还对幼稚算法进行了严格的分析，表明它执行$θ（n^{2}）$的工作，并在问题的原始陈述中纠正了虚假陈述。据我们所知，这是计算几何形状在数值线性代数中解决现实世界问题的第一个应用。
We show how to efficiently solve a clustering problem that arises in a method to evaluate functions of matrices. The problem requires finding the connected components of a graph whose vertices are eigenvalues of a real or complex matrix and whose edges are pairs of eigenvalues that are at most δaway from each other. Davies and Higham proposed solving this problem by enumerating the edges of the graph, which requires at least $Ω(n^{2})$ work. We show that the problem can be solved by computing the Delaunay triangulation of the eigenvalues, removing from it long edges, and computing the connected components of the remaining edges in the triangulation. This leads to an $O(n\log n)$ algorithm. We have implemented both algorithms using CGAL, a mature and sophisticated computational-geometry software library, and we demonstrate that the new algorithm is much faster in practice than the naive algorithm. We also present a tight analysis of the naive algorithm, showing that it performs $Θ(n^{2})$ work, and correct a misrepresentation in the original statement of the problem. To the best of our knowledge, this is the first application of computational geometry to solve a real-world problem in numerical linear algebra.
