在FORTRAN中高效地查找数组

Question

我试图以稀疏的格式在FORTRAN中存储刚度矩阵，以节省内存，即我使用了三个非零元素的向量(irows，icols，A)。找出这些数组的大小后，下一步是在其中插入值。所以我使用高斯点，即对于每个高斯点，我要找出局部刚度矩阵，然后将这个局部刚度矩阵插入到全局(irows，icols，A)矩阵中。

这种插入的主要问题是，每次我们必须检查新值是否存在于全局数组中，因此如果值存在，则将新值添加到旧数组中，如果不添加到末尾，则将新值添加到旧数组中。也就是说，我们必须搜索整个数组，以找出该值是否存在。如果这些数组(irows，icols，A)的大小很大，那么这种搜索在计算上是非常昂贵的。

有没有人能提出一种更好的方法来为每个高斯点插入局部刚度矩阵，全局刚度矩阵。

Answer 1

我相当肯定这是有限元分析中的一个众所周知的问题-我在这个scipy documentation中找到了它的引用，但当然原理是独立于语言的。基本上，你应该做的是以你所拥有的格式创建矩阵，而不是搜索矩阵来查看一个条目是否已经存在，只要假设它不存在就行了。这意味着你最终会得到重复的条目，这些条目需要加在一起才能得到正确的值。

一旦构建了矩阵，通常会将其转换为某种更有效的求解形式(例如CSR etc.) -确切的格式可能取决于所使用的稀疏求解器。在此转换过程中，应将重复的条目添加到一起-一些稀疏矩阵库将为您完成此操作。我知道scipy做到了这一点，而且它的许多内部例程都是用fortran编写的，所以您可以使用其中的一个(它们都是开源的)。或者你可以检查netlib上是否有合适的东西。

Answer 2

如果您使用预先排序的数据结构，那么搜索它将是非常有效的。作为主数据结构或辅助数据结构。你想要一个，你可以在中间插入另一个条目。例如二叉树(http://en.wikipedia.org/wiki/Binary_search_tree)。