不规则结构问题的集成块分解与分区方法

### 不规则结构问题的集成块分解与分区方法 在处理不规则结构问题时，高效的分区和块分解方法至关重要。本文将介绍一种集成块分解和分区方法，并与其他相关技术进行比较。 #### 1. 分区方法概述 该算法主要由三个步骤组成： 1. **聚类步骤**：将水点聚类到“密集”块中，努力使块效率（即活动点的比例）高于给定阈值。 2. **分布步骤**：将块分配到处理器上，实现较小的负载不平衡率和较少的处理器间依赖关系。 3. **合并步骤**：尝试将同一处理器上的块合并成更大的矩形块，以减少块的总数。 下面将详细介绍前两个步骤。 #### 2. 聚类算法 聚类算法的目标是将活动点聚类到具有高块效率的矩形块中。具体操作步骤如下： 1. **创建最小边界框**：创建一个围绕所有活动点的最小边界框。 2. **递归分割**：递归地分割该块，并在结果块周围创建新的边界框，直到块效率高于给定阈值。在每个递归步骤中，仅选择活动点比例低于给定阈值的块进行分割。该阈值可以是固定速率或相对速率： - **固定速率**：选择活动点比例低于 X%（X 为常数）的块。 - **相对速率**：选择与其他块相比有较多非活动点的块，例如，选择非活动点比平均水平多 Y% 的块。 3. **确定分割线**：在分割阶段，在块的中心周围设置一个搜索窗口，在窗口内沿最长边进行分割，且穿过的活动点数量最少。即沿着具有最小签名 $S_i$ 的网格线进行切割。签名 $S_i$ 定义为沿该线（3D 中为表面）的活动点之和，即 $S_i = \sum_{j} I_{ij}$，其中 $I_{ij} = 1$ 表示水点，$I_{ij} = 0$ 表示陆点。搜索窗口的作用有两个：一是限制搜索空间，二是避免切割过薄的块。 以下是聚类算法的流程图： ```mermaid graph TD; A[创建最小边界框] --> B[检查块效率是否高于阈值]; B -- 是 --> C[结束]; B -- 否 --> D[选择活动点比例低于阈值的块]; D --> E[设置搜索窗口]; E --> F[找到最小签名的网格线]; F --> G[沿该线分割块]; G --> H[在结果块周围创建新边界框]; H --> B; ``` #### 3. 分布方法 分布方法将块分配到处理器上，将其视为图分区问题。具体步骤如下： 1. **构建图**：块构成顶点，块之间的数据依赖关系构成边。选择顶点权重与块上的工作量成比例，边权重与相应块之间的通信量成比例。 2. **使用递归谱二分法（RSB）**：使用 RSB 方法最小化图分区中的全局边切割。在每个二分步骤中，根据 Fiedler 向量将顶点排序为两个工作量大致相等的部分。 3. **局部细化**：使用局部细化方法（如 Greedy、Kernighan - Lin）进一步改进分区。顶点 $v$ 从分区 $A$ 移动到分区 $B$（$A$ 和 $B$ 相邻）的增益定义为： $g(v,A,B) = \sum_{w \in B} E_w - \sum_{w \in A} I_w$ 其中 $E_w$ 是分区 $A$ 中顶点 $v$ 与分区 $B$ 中顶点 $w$ 之间的边权重，$I_w$ 是分区 $A$ 中顶点 $v$ 与顶点 $w$ 之间的边权重。 4. **必要时分割块**：如果块较大或块的数量相对于处理器数量较少，难以平衡工作量。此时，在每个二分步骤中根据块大小和上述计算的增益选择一个块进行分割，选择具有最高增益且足够大的块，以平衡两个分区之间的工作量。 #### 4. 数值结果 ##### 4.1 应用场景 选择与海洋建模相关的应用，求解不规则几何形状（如苏必利尔湖、波罗的海和世界海洋）内的泊松方程。大多数运行是针对苏必利尔湖案例进行的，其他几何形状仅用于补充结果。这些应用在海洋学中具有普遍意义，尽管求解的是具有恒定强迫函数的二维方程。 求解具有恒定强迫函数和齐次 Dirichlet 边界条件的二维泊松方程： $\begin{cases} U_{xx} + U_{yy} = -1 & \text{in } \Omega \\ U = 0 & \text{at } \partial \Omega \end{cases}$ 使用中心五点有限差分模板对该方程进行离散化，并使用 Krylov 子空间方法（共轭梯度平方方法）求解相应的线