直接作为 CSC 矩阵构建刚度的快速方法

计算科学 有限元 稀疏矩阵
2021-12-19 16:39:38

我一直在 Fortran 2008 中研究有限元代码,并实现了我自己的稀疏矩阵类型。我发现将局部刚度矩阵(真实类型)映射到全局 COO 稀疏类型,然后转换为 CSC 效果很好,但超过一定大小时,对 COO 进行排序变得令人望而却步。
相反,我想直接构建 CSC 矩阵,但我无法让它足够快。我不想让任何人对我的代码细节感到厌烦,但我尝试了以下方法:

  1. 将每个局部刚度矩阵中的值插入到预先声明的全局 CSC 矩阵中。这很慢,因为分配新空间并将列指针向右移动很慢。

  2. 实现 CSC 添加并将每个元素的局部刚度矩阵映射到一个空的全局矩阵,然后依次添加。

  3. 尝试构建邻接矩阵,以便预先分配所有条目。事实证明这同样缓慢。

我对你的结构性想法很感兴趣。人们通常如何做到这一点?我的代码是在非结构化网格上使用二阶元素的 3D 代码。一个较小的问题有大约 400 万个节点。

仅供参考,COO-> CSC 在大型矩阵上传输的问题是我实现了合并排序,一旦总数据大于约 32MB,我的实现就会爬网。

1个回答

COO 是一种不适合的矩阵格式,除非用于特定目的(例如,如果有大量行根本没有条目,可能对角线除外)。

我所知道的所有大型代码构建系统矩阵的方式都是通过三步过程:

  • 在第一步中,您遍历所有单元格并确定您写入哪些条目,并从中构建 CSC/CSR 矩阵的稀疏模式。为此,通常为稀疏模式的每一行保留一组排序的索引(即,不是整个矩阵的一组索引对)。

  • 然后,您可以为每一行计算要写入的唯一列索引的数量,并且可以构建一个静态(不可更改)CSC/CSR 稀疏模式,其中您保留两个数组:一个非常长的列索引数组和一个大小数组等于告诉您在长列索引数组中第行开始的位置的行数。i

  • 构建稀疏模式后,您可以为矩阵分配内存。这是一个长度等于列索引数的数组。

在第一步中,排序操作只对单个行中的列索引进行排序。此外,对于一个单元格上的每个度数,您都知道要写入哪些列;所以对这些列索引进行排序,然后将这个排序数组与之前为该行添加的索引的排序数组合并。合并可以在中完成,而初始排序需要O(nnonzeros per row)O(ndofs per celllogndofs per cell)