什么是密集 ODE 系统?什么是稀疏 ODE 系统?

计算科学 教育
2021-12-15 18:21:58

您能否对“密集 ODE 系统”和“稀疏 ODE 系统”的含义提供无行话(尽可能)的解释?

我从谷歌上得到的一些提示:

  • 稠密 ODE 系统的计算成本随系统规模呈二次方增长

  • 稀疏 ODE 系统的计算成本与系统的大小无关

  • 密集 ODE 系统的计算成本主要由 CPU 考虑

  • 稀疏 ODE 系统的计算成本主要由“通信”考虑因素决定

我的一些猜测:如果密集 ODE 系统的计算成本随系统大小呈二次方增加,那么变量之间肯定存在大量“点对点”交互。那么,n体问题会是密集的吗?

我想不出一个稀疏 ODE 系统的好例子,除了一个琐碎的例子,我拿了一堆彼此无关的独立 ODE,然后把它们放在一起声称它是一个“系统” ?

为什么稀疏 ode 系统的计算成本会受到通信问题的支配?之间有什么交流?处理器?

1个回答

n 体问题会很密集(当然,如果您不进行任何过滤以消除“弱”耦合。

正如 Maxim Umansky 在评论中提到的,时间相关 PDE 的一些离散化会产生稀疏 ODE 系统。其他一些方法,如光谱方法,是密集 ODE 系统。

在并行计算方面,我认为稀疏 ODE 系统与密集 ODE 系统的解决方案中的通信成本不会有太大差异——当然,除非您在进程之间移动系统的一部分。然而,稀疏 ODE 系统的算法通常耗时较少,例如采用密集矩阵向量乘法O(n2)反对稀疏矩阵向量乘法O(nonzeros)- 和非零是O(n)根据稀疏性的定义。因此,可以想象花费在沟通上的时间变得很重要。