为什么要使用树结构来表示离散函数空间?

计算科学 数据结构
2021-12-02 19:03:22

在 FEM/FV 代码库中,我偶然发现了离散化函数空间在代码中表示为树结构的事实。我觉得这很令人费解。

示例:假设有人想模拟纳维斯托克斯方程。代码库期望将离散化的函数空间放入如下数据结构中:

在此处输入图像描述

所以是层次树结构。我不明白为什么这应该是一个合理的选择,因为:

  1. 字段没有内在的层次结构。在图像中,压力变量列在比速度分量更高的级别。但这纯粹是装饰性的展示。影响我们的耦合系统的组件没有内在的层次结构。如果没有层次结构,那么树结构对我来说似乎不明智。

  2. 数据局部性。我有一个选项,我可以告诉程序按单元格或字典顺序对齐数据。这是一个不错的功能,但它的核心是(结构数组数组结构)的古老问题。这也没有向我解释为什么我应该使用树。

  3. 有限的复杂性我没有遇到过任何代码库或场景,其中函数空间如此之多或如此复杂,以至于证明非平凡的数据结构是合理的。即使您进行完整的 MHD 模拟,您也可以轻松地将您的字段放入(结构数组数组结构)中。树结构是否会简化或混淆您的代码是值得怀疑的。

我错过了什么?为什么有人会为此使用树结构?(提前致谢!)

1个回答

虽然我不能代表 NS 或 MHD,但我确实发现功能空间的这种“组件化”是 CEM(计算电磁学)中有用的设计原则,特别是对于高阶(以 p 为单位)离散化。

CEM 经常同时使用多个空间:grad-conforming 函数表示电势,curl-conforming 函数表示 E-field,div-conforming 函数表示 B-flux 和 currents 等。这些空间相互关联通过 deRham 图,每个微分算子 (grad/curl/div) 的范围形成下一个的内核(精确序列属性)。

根据我的经验,这可以(应该?)在实现级别一直显示,因为它可以节省您的时间并有助于保证正确性。例如,如果您花费时间和金钱来制表/实现高阶 grad-conforming 空间(基本函数及其梯度,你可以(应该?)重用那些 's 作为 curl-conforming 空间中的基函数,那么您只需要通过添加所需的任何附加函数来丰富它们,将 curl 范围扩展到您想要的顺序。在 curl-conforming 和 div-conforming 空间之间存在类似的结构(符合 curl 的函数的 curl 应该是符合 div 的基础的成员)。ϕϕϕ

不幸的是,由于单解性问题(p=0 卷曲已经跨越 p=0 梯度等),这种富集过程在 p=0 时是混乱/中断的。它实际上只在 p >= 1 时发光。在实践中,我使用以下分解:

  • hgrad0: p=0 符合梯度的函数
  • hgradp: p>0 符合梯度的函数
  • hcurl0: p=0 符合 curl 的函数
  • hcurlp:“丰富” p>0 的 curl 范围的函数
  • hdiv0: p=0 符合 div 的函数
  • hdivp:“丰富” p>0 的 div 范围的函数

使用这些构建块,您可以将整个图表制成表格:

  • hgrad := hgrad0 + hgradp
  • hcurl := hcurl0 + grad(hgradp) + hcurlp
  • hdiv := hdiv0 + curl(hcurlp) + hdivp
  • L2 := 分段常数 + div(hdivp)

并且这些空间中的每一个 (i) 将内核与相应的微分算子的范围分开,并且 (ii) 将 p=0 空间与 p>0 .. 分开。这两个属性在设计预处理器时都很有用。