针对复杂系统并行模拟问题的并发式多级矩阵重排算法

A concurrent permutation based multilevel matrix ordering strategy for parallel process simulation

在解决复杂化工过程优化与模拟问题时,大规模代数差分方程的存在导致大量的计算时间花费在重复求解稀疏大型线性方程组的过程中。随着并行计算和网络技术的发展,为了提高优化或模拟工作的速度,可以通过将非对称矩阵重排为带边块对角形式,从而实现对线性系统的高效并行求解。本文提出一种基于Kernighan-Lin算法的并发式的多层次矩阵重排策略,它以最小化边块为目标,同时保证尽可能小的负荷非平衡性,从而获得好的重排结果。应用该重排策略可以对大型稀疏矩阵进行压缩和并行重排,提高重排算法的效率。在研究过程中应用了基于该技术的并行计算程序对一系列标准矩阵进行了检验,并与一些现有的算法进行了比较,证明了其有效性和可行性。

When optimization and simulation of complex chemical process are carried out, large systems of algebraic differential equa-tions must be solved. It was cost a great deal computing time to solve such a large sparse system of linear equations. For speeding up the optimization and simulation, the linear systems may be solved efficiently in parallel by reordering the unsymmetric matrices into a bor-dered block-diagonal (BBD) form. A multilevel matrix ordering strategy based on a Kernighan-Lin algorithm is propo...