超节点和多额矩阵分解之间有什么区别?你能提供一些关于这些方法的参考资料或高层次的观点吗?
超节点与多额因子分解
计算科学
矩阵分解
2021-12-21 19:26:58
1个回答
这些术语的范围(在我看来)有些不同。
我将使用“超节点”作为一个广义术语,来描述在符号分析阶段应用足够智能以识别共享相同非零结构的连续列并将它们重新排序/聚合为一个“超变量”的任何稀疏直接求解器同时被消除、反向求解和 schur-downdated。如另一个问题所示,这些操作可以使用 BLAS3 算术并提供比“标量”求解器更高的性能。一些求解器非常积极地超节点,并且会在模式中引入新的存储零,如果它导致消除树更好的粗化(BLAS3 比 BLAS2 更多)。这与密集算法的格局没有什么不同,
另一方面,“multifrontal”是一个狭义的术语,它暗示了一种用于“右视”分解的特定存储和调度策略。它们的关键特性是引入了额外的(小型、大量、内存连续的)工作空间,这些工作空间保存了每个超级节点导致的 schur-downdates。这种策略放松/阻止了正确算法中的“写入竞赛”,并暴露了消除树的多个分支之间的并行性。如果您查看 multifrontal 方法中涉及的实际数据结构,它们不是类似数组的 CSR/CSC 布局,它们都在跟踪数字存储的小而密集的片段,这些片段悬挂在一些底层符号 DAG/树上。Multifrontal 方法通常也是超节点的(但反之则不然,
根据我的经验,multifrontal 方法(最初)更难编写,但更容易并行化(后来)。它们倾向于使用更多的内存(工作空间),但可以通过适度的努力重构为核外求解器。
其它你可能感兴趣的问题