共轭梯度法毕业论文

牛顿法需要函数的一阶、二阶导数信息，也就是说涉及到Hesse矩阵，包含矩阵求逆运算，虽然收敛速度快但是运算量大。拟牛顿法采用了一定的方法来构造与Hesse矩阵相似的正定矩阵，而这个构造方法计算量比牛顿法要小；共轭梯度法的基本思想是把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共轭方向基本性质，这种方法运算量不太大收敛速度也不慢。

从20世纪40年代开始的现代计算机发展历程可以分为两个明显的发展时代：串行计算时代、并行计算时代。每一个计算时代都从体系结构发展开始，接着是系统软件（特别是编译器与操作系统）、应用软件，最后随着问题求解环境的发展而达到顶峰。并行计算机是由一组处理单元组成的。这组处理单元通过相互之间的通信与协作，以更快的速度共同完成一项大规模的计算任务。因此，并行计算机的两个最主要的组成部分是计算节点和节点间的通信与协作机制。并行计算机体系结构的发展也主要体现在计算节点性能的提高以及节点间通信技术的改进两方面。节点性能不断进步20世纪60年代初期，由于晶体管以及磁芯存储器的出现，处理单元变得越来越小，存储器也更加小巧和廉价。这些技术发展的结果导致了并行计算机的出现。这一时期的并行计算机多是规模不大的共享存储多处理器系统，即所谓大型主机。IBM 360是这一时期的典型代表。到了20世纪60年代末期，同一个处理器开始设置多个功能相同的功能单元，流水线技术也出现了。与单纯提高时钟频率相比，这些并行特性在处理器内部的应用大大提高了并行计算机系统的性能。伊利诺依大学和Burroughs公司此时开始实施Illiac Ⅳ计划，研制一台64颗CPU的SIMD主机系统，它涉及到硬件技术、体系结构、I/O设备、操作系统、程序设计语言直至应用程序在内的众多研究课题。不过，当一台规模大大缩小的原型系统（仅使用了16颗CPU）终于在1975年面世时，整个计算机界已经发生了巨大变化。首先是存储系统概念的革新，提出虚拟存储和缓存的思想。以IBM 360/85和IBM 360/91为例，两者是属于同一系列的两个机型，IBM 360/91的主频高于IBM 360/85，所选用的内存速度也较快，并且采用了动态调度的指令流水线。但是，IBM 360/85的整体性能却高于IBM 360/91，惟一的原因就是前者采用了缓存技术，而后者则没有。其次是半导体存储器开始代替磁芯存储器。最初，半导体存储器只是在某些机器中被用作缓存，而CDC7600则率先全面采用这种体积更小、速度更快、可以直接寻址的半导体存储器，磁芯存储器从此退出了历史舞台。与此同时，集成电路也出现了，并迅速应用到计算机中。元器件技术的这两大革命性突破，使得Illiac Ⅳ的设计者们在底层硬件以及并行体系结构方面提出的种种改进都大为逊色。处理器高速发展1976年Cray-1问世以后，向量计算机从此牢牢地控制着整个高性能计算机市场15年。Cray-1对所使用的逻辑电路进行了精心的设计，采用了我们如今称为RISC的精简指令集，还引入了向量寄存器，以完成向量运算。这一系列技术手段的使用，使Cray-1的主频达到了80MHz。微处理器随着机器的字长从4位、8位、16位一直增加到32位，其性能也随之显著提高。正是因为看到了微处理器的这种潜力，卡内基·梅隆大学开始在当时流行的DEC PDP-11小型计算机的基础上研制一台由16台PDP-11/40处理机通过交叉开关与16个共享存储器模块相连接而成的共享存储多处理器系统。从20世纪80年代开始，微处理器技术一直在高速前进。稍后又出现了非常适合于SMP方式的总线协议。而伯克利加州大学则对总线协议进行了扩展，提出了Cache一致性问题的处理方案。从此，开创出的共享存储多处理器之路越走越宽。现在，这种体系结构已经基本上统治了服务器和桌面工作站市场。通信机制稳步前进同一时期，基于消息传递机制的并行计算机也开始不断涌现。20世纪80年代中期，加州理工学院成功地将64个i8086/i8087处理器通过超立方体互连结构连结起来。此后，便先后出现了Intel iPSC系列、INMOS Transputer系列，Intel Paragon以及IBM SP的前身Vulcan等基于消息传递机制的并行计算机。20世纪80年代末到90年代初，共享存储器方式的大规模并行计算机又获得了新的发展。IBM将大量早期RISC微处理器通过蝶形互连网络连结起来。人们开始考虑如何才能在实现共享存储器缓存一致的同时，使系统具有一定的可扩展性。20世纪90年代初期，斯坦福大学提出了DASH计划，它通过维护一个保存有每一缓存块位置信息的目录结构来实现分布式共享存储器的缓存一致性。后来，IEEE在此基础上提出了缓存一致性协议的标准。20世纪90年代至今，主要的几种体系结构开始走向融合。属于数据并行类型的CM-5除大量采用商品化的微处理器以外，也允许用户层的程序传递一些简单的消息。Cray T3D是一台NUMA结构的共享存储型并行计算机，但是它也提供了全局同步机制、消息队列机制，并采取了一些减少消息传递延迟的技术。随着微处理器商品化、网络设备的发展以及MPI/PVM等并行编程标准的发布，集群架构的并行计算机出现开始。IBM SP2系列集群系统就是其中的典型代表。在这些系统中，各个节点采用的都是标准的商品化计算机，它们之间通过高速网络连接起来。 有限元并行计算的发展和现状目前，在计算力学领域内，围绕着基于变分原理的有限元法和基于边界积分方程的边界元法，以及基于现在问世的各种并行计算机，逐渐形成了一个新的学科分支——有限元并行计算。它是高效能的，使得许多现在应用串行计算机和串行算法不能解决或求解不好的大型的、复杂的力学问题能得到满意的解答，故其发展速度十分惊人。在国际上已经掀起了利用并行机进行工程分析和研究的高潮。从1975到1995年的二十年间，有关有限元方法和相应的数值并行计算的文章已发表1000余篇。有限元并行计算正在向两个方向发展。一是对系统方程组实施并行求解的各种算法。二是并行分析方法，包括有限元并行算法和边界元并行算法，前者趋向成熟，而后者的研究较少。对这一方面的研究，是为了挖掘有限元计算自身潜在的并行性，是有限元并行计算的根本问题。国内并行算法的设计和有效实现强烈地依赖于并行机的硬软件环境。国内仅极少数单位拥有并行机，且机型杂乱，因此研究人员少，起步晚，而且局限于特定的硬件环境。从有限元分析方法的内容来看，发表的几十篇研究论文（报告）还未显示出较强的系统性。1）南京航空航天大学周树荃教授等在YH-1向量机上实现了刚度矩阵计算、对称带状矩阵的Cholesky分解和线性方程组的求解等并行处理。针对不规则结构工程分析问题，他们还采用了变带宽存贮方法，并实现了刚度矩阵的并行计算以及求解变带宽稀疏线性方程组的并行直接解法【20】。2）中国科学院计算中心王荩贤研究员等在基于Transputer芯片的分布式MIMD系统上，提出了有限元分析中变带宽线性方程组的并行直接解法，初步完成了一个静力分析程序【21】。3）重庆大学张汝清教授等借助于ELXSI-6400共享存贮器型MIMD系统，先后开展了范围比较广泛的并行算法研究，主要成果有：a)提出了静力分析中子结构解法的并行算法，以及动力分析中模态综合子结构法的并行算法；b)从波前法出发，发展了多波前并行算法以求解大型结构分析问题；c)从Jacobi块迭代法和加权残差法出发，导出了基于异步控制的有限元方程并行解法和有限元并行迭代的基本格式；d)利用图论中的着色理论，实现了刚度矩阵的并行计算；e)实现了基于有色线剖分的SOR并行迭代解法；f)实现了子空间迭代法、Lanczos法以及利用多项式割线迭代法和矢量迭代法求解结构固有频率和模态的并行算法；g)针对弹塑性分析，提出了一种多波前子结构并行算法；h)针对弹性接触问题，提出了一种基于参数变分原理的并行解法；i)实现了一步积分法的并行处理【22】。4）南京航空航天大学乔新教授等借助于Transputer芯片的分布式MIMD系统实现了有限元方程组的并行直接解法，并提出了基于子结构的预处理共轭梯度法的并行计算方法【23】。此外，浙江大学姚坚【24】、中国科学院西南计算中心马寅国、东北工学院张铁以及国防科技大学六系也曾对有限元分析的并行计算开展了一些研究。上述研究结果表明，国内并行计算方法的研究，在硬件上基于向量机、分布式并行机和共享存贮式并行机；在内容上，似乎面很广，但系统性和深度还很不够，软件开发距实际应用和商品化还有很大距离，对不依赖并行机具体环境的通用并行算法研究还很少，同样对旨在进行结构有限元分析的并行计算的硬件研究也很少。国外自从美国国家宇航局（NASA）的于1975年发表第一篇有限元并行计算的文章以来，有限元并行处理技术几乎与并行计算机同步发展。距不完全统计，到1992年，国外已发表了400余篇这方面的论文，其中后5年的文章篇数是前12年的总和。在研究内容上也由过去的算法研究发展到了算法、软件和硬件相结合的研究，并针对一些机型开发了一些实用的大型结构分析软件。1）有限元机器FEM【25】（Finite Element Machine）。早在70年代末，就有人发表了有关FEM的论文，1982年美国国家宇航局Langley研究中心的等撰文详细地介绍了该中心设计的供研究用的FEM。该机器由1个处理器阵列、1台作为控制器的微机和1个并行操作系统及一些模块化了的通用并行算法程序组成，用户使用系统的文本编辑器和控制器的其它特殊功能，能建立有限元计算模型并进行分析。10多年来，又有一些人在这一方面进行了不懈的努力，但FEM的发展前景仍然不太令人乐观。2）心动阵列并行机【26】。心动阵列并行机主要应用于信号和图象的并行处理，但由于其高效的矩阵计算功能，近年来有人把它应用于有限元分析，并作了一些有益的尝试。3）巨型向量机【27】。在有限元分析中越来越显示出巨大的威力，处于领先的是美国思维公司的CM-2。许多结构分析家把这个具有65536个处理器的巨型向量机应用于有限元计算，如等人采用显式方法，完成了具有32768个单元的壳的非线性有限元计算，并行效率极高，速度几乎比CRAY X-MP/14并行机高出1个数量级。4）并行机网络和工作站网络【28】。日本东京大学矢川等借助高速网络把3台CRAY Y-MP机联成网络进行有限元分析，有限元方程求解采用的是基于区域分裂技术的共轭梯度法（CGM）， 在求解三维弹性问题时自由度个数超过了100万，系统平均运行速度高达。另外，他们还基于一个工程工作站网络，在并行环境下进行了类似的研究，求解问题的自由度数高达20万个。--我左看右看前看后看可还是看不过来这个....那个....我越看越奇怪....不是我不明白，这世界变化快

1.并行计算体系结构发展纵览.并行和分布计算技术现状及发展策略 .并行计算软件开发概述.基于ANSYS的并行计算发展及实现