论文标题
关于Hermitian特征值问题和HyperGraph Edge消除的等效性
On the equivalence of the Hermitian eigenvalue problem and hypergraph edge elimination
论文作者
论文摘要
习惯上识别具有相应邻接或入射图的稀疏矩阵。对于使用高斯消除的线性方程式解决方案的解决方案，通过其邻接图表示，可以使用符号计算来预测内存足迹，并可以根据启发式学确定近距离的消除顺序。另一方面，由于其固有的迭代性质，Hermitian特征值问题似乎乍一看避免了这种治疗方法。在本文中，我们通过显示遗传学特征值问题与符号边缘消除程序的等效性，证明了这一断言错误。基于基质的入射图的符号计算可以类似于高斯消除的符号阶段，以开发启发式方法，从而减少记忆足迹和计算。但是，我们还表明，与线性系统案例相比，最佳消除策略的问题仍然是NP-HARD。
It is customary to identify sparse matrices with the corresponding adjacency or incidence graph. For the solution of linear systems of equations using Gaussian elimination, the representation by its adjacency graph allows a symbolic computation that can be used to predict memory footprints and enables the determination of near-optimal elimination orderings based on heuristics. The Hermitian eigenvalue problem on the other hand seems to evade such treatment at first glance due to its inherent iterative nature. In this paper we prove this assertion wrong by showing the equivalence of the Hermitian eigenvalue problem with a symbolic edge elimination procedure. A symbolic calculation based on the incidence graph of the matrix can be used in analogy to the symbolic phase of Gaussian elimination to develop heuristics which reduce memory footprint and computations. Yet, we also show that the question of an optimal elimination strategy remains NP-hard, in analogy to the linear systems case.
