文档介绍：南京邮电大学
硕士学位论文
基于块Broyden方法的并行预处理技术的研究
姓名:丁秀梅
申请学位级别:硕士
专业:计算机应用技术
指导教师:杨庚
2011-05
南京邮电大学硕士研究生学位论文摘要
摘要
高性能计算在科学研究和工程应用中扮演着日益重要的角色,其面临的基本问题之一
是超大规模非线性方程组的数值求解。非线性系统维数的巨大,常常导致算法不仅对内存
有巨大的需求,而且收敛速度往往很慢,可靠性差。这些因素常使算法无法真正应用到工程
实际中,因此必须寻求高效的能够实际应用的数值方法。目前,人们通常采用并行计算技
术,以提高求解问题的规模,加快求解问题的速度。本文的目标就是基于块 Broyden 方法,
建立并行求解非线性方程组迭代算法的预处理方法,从而达到提高算法收敛性的目的,并
为今后的并行化、整体化的预处理方法的研究奠定理论基础。
本文首先描述了求解非线性方程组的几种经典迭代算法(包括牛顿法、拟牛顿法等),
显示了块 Broyden 方法的优势。回顾了预处理技术的发展历史,分析了预处理矩阵的基本
构造要求,讨论了六种不同的预处理技术。然后,将块 Broyden 方法与各种预处理技术相
结合形成不同的 BBP 算法,并从理论上分析了各种算法在串行和并行下求解大规模非线性
系统方面的时间复杂度和存储需求,进而推导出性能比较的定量公式。最后,将 BBP 算法
运用到计算物理经典的 Bratu 问题的数值求解中,得到了详尽的实验数据,并依据理论分
析中给出的公式,对各种求解方法的性能进行了分析比较。试验数据表明,结合了预处理
技术的块 Broyden 算法具有更好的求解性能,可适用于大规模科学与工程的高性能计算。
I
南京邮电大学硕士研究生学位论文 Abstract
Abstract
High-puting plays an increasingly important role in scientific research and
engineering application. One of the fundamental problems it faces is to solve large-scale nonlinear
systems of equations. Huge dimension of nonlinear systems often has a high demand on memory
in the process of calculation. Worse still, it results in slow convergence in algorithm and a lack of
good reliability and stability. These problems make it difficult to apply algorithm into engineering
practice. Therefore, it is essential to find the efficient feasible numerical methods. At present,
puting techniques are widely used to improve problem solving scale and speed up
problem solving speed. The objective of this thesis is to detect the proper preconditioners, based
on Block Broyden Method, to solve nonlinear equations and meanwhile lay theoretical
foundations for future research of the parallel and the whole preconditioning methods.
First, this thesis sketches several classical iterative methods about the solving to the
nonlinear equations and shows the advantages of Block Broyden Method. Meanwhile, it focuses
on preconditioning techniques and presents six preconditioners. Different pr