数值并行迭代算法中的收敛性与并行性的权衡
传统串行迭代算法中,收敛速度是衡量一个算法的主要依据.而并行算法要求良好的并行性。设计并行迭代算法时,并行性的增加往往导致收敛速度的降低,从而抵消了并行化带来的性能提高.本文表明需要权衡迭代算法的收敛性和并行性,以获得更好的性能。在一般线性方程组的基于分裂的迭代算法中,Gauss-Seidel算法有着良好的收敛速度但并行性很差;而Jacobi方法具有天然的并行性,但通常收敛速度较慢。我们对两种方法的收敛性和并行性进行权衡,设计了一个新的分裂格式,基于该分裂格式的多分裂算法具有比Jacobi算法更快的收敛速度,而又有比较好的并行性。在理论上给出了该算法成立的收敛性条件,在集群系统上的实验表明此算法结果与理论相符合并且有更好的性能.
并行迭代算法 稠密矩阵 多分裂算法 收敛速度 并行性
商磊 吕全义
中国科学院计算技术研究所 北京 100080 西北工业大学应用数学系 西安 710072
国内会议
深圳
中文
231-238
2007-10-26（万方平台首次上网日期，不代表论文的发表时间）