数值并行计算是解决大规模科学与工程问题的重要途径在并行计算中，一方面希望通过合理分配计算任务，平衡各计算节点的计算负载，从而缩短计算节点的空闲等待时间；另一方面希望尽可能减少计算节点之间的通信开销，提高并行效率为了更好的解决上述负载平衡问题，可采用任务图的方式进行建模，在这种模型下，负载平衡问题可抽象为图分割问题图分割问题是并行计算领域中的热点问题，国内外学者在数十年的探索和研究中提出了很多优秀的图分割算法和模型然而，面对日益复杂的应用问题，很多现有的图分割算法已无法适应日益变化的应用需求因此，亟待研究更强大的图分割模型，更优秀的图分割算法，以及对各类算法更有效的使用方法在上述背景下，本文以图分割问题为切入点，重点研究图分割算法及其在数值并行计算中的应用，具有重要的理论意义和实际应用价值本文的主要研究成果及创新点如下：1.提出了基于团结构的多层图分割算法针对静态图分割问题，以多层分割算法为切入点，分别针对算法各阶段的特点详细地阐述了不同阶段所采用的典型策略，并对各种策略作了简单的分析和比较接着，在Miller的若干假设的基础上，对多层算法进行了定量分析根据理论分析的结果，剖析了现有的基于匹配的粗化策略的缺点和局限性，在此基础上提出了基于团结构的多层图分割算法（CBML）最后对算法进行了全面地测试和分析，并将实验结果与MeTis进行了比较实验结果表明，CBML产生的分割质量在多数情况下要优于MeTis，尤其是针对线性规划问题和VLSI电路设计问题2.提出了基于多层算法框架的重分割模型针对动态图分割问题，全面分析了各类典型重分割算法，并对其性能和适用条件进行了比较为了克服各类算法的局限性，定义了重分割问题的通信迁移比和耗费函数，通过耗费函数更准确地评价重分割质量，将重分割问题的优化目标统一表达为最小化耗费函数在此基础上利用多层算法的优势，提出了基于多层算法框架的重分割模型（MBRM）最后采取了结构扰动和计算量扰动两种方式对计算负载的动态过程进行了模拟，在此过程中对MBRM的性能进行了全面的测试和分析，并将实验结果与ParMETIS进行了比较实验结果表明，MBRM的性能优于ParMETIS，尤其是当通信开销与迁移开销较接近时，MBRM的优势更明显3.提出了基于超图分割的改进型嵌套排序算法针对最小化引入元的矩阵排序问题，广泛研究了各类典型排序算法，并将重点聚焦在以嵌套排序为基础的混合排序方法上接着对嵌套排序算法进行了分析，找到了影响算法性能的关键因素，即嵌套排序的质量在很大程度上取决于各级嵌套子图中顶点分割子的质量而现有的两类计算顶点分割子的算法都存在固有的缺点和局限性为了解决这个问题，提出了基于超图分割的改进型嵌套排序算法（HBND），将图顶点分割子的计算问题转化为超图分割问题最后对算法进行了全面地测试和分析，并将实验结果与MeTis进行了比较实验结果表明，HBND产生的排序质量优于MeTis4.针对CFD中非结构网格的并行计算问题进行了分区优化将CBML算法用于非结构网格的CFD并行计算问题，针对NACA0012翼型ONERA-M6翼型DLR-F6翼身组合体三个实际的飞行模拟问题，采用CBML算法对其计算网格进行了分区优化，并与pmetis的分区结果进行了比较在超级计算机天河-1A上进行了并行性能测试，通过比较加速比并行效率等性能指标，分析不同分区算法对并行性能的影响实验结果表明，上述应用问题在采用CBML算法进行分区优化时，能获得更好的并行性能