检索结果-南通市图书馆

krylov子空间方法的一些改进及其在求解N-S方程中的应用

在线全文

学校读者我要写书评

暂无评论

Krylov子空间方法的一些改进及其在求解N-S方程中的应用

作者：关朋燕北方民族大学

学位级别：硕士

随着计算机技术的快速发展,大规模稀疏线性系统的高效求解问题已成为许多科学与工程计算、数值模拟以及金融优化等领域的核心问题.由于求解线性方程组所花费的时间在整个问题总的计算时间中占有很大的比重,因此,高效地求解大规模稀疏线... 详细信息

随着计算机技术的快速发展,大规模稀疏线性系统的高效求解问题已成为许多科学与工程计算、数值模拟以及金融优化等领域的核心问题.由于求解线性方程组所花费的时间在整个问题总的计算时间中占有很大的比重,因此,高效地求解大规模稀疏线性系统能够很大程度上提升整个问题的求解效率.本文主要讨论求解大型线性系统的krylov子空间类方法,和使用TDMA算法对高维对流扩散问题所产生的代数方程组迭代求解时做了收敛性分析. 首先,介绍了对于高维对流-扩散问题在采用有限体积法离散域且满足守恒性、有界性和运输性时,所生成的离散方程组,通常采用TDMA(Tri-diagonal matrixalgorithm)算法迭代求解.对于该TDMA迭代求解算法,本章首先给出了其收敛性证明:对离散方程组的系数矩阵采用矩阵分块,对二维TDMA迭代算法采用逐列迭代收敛,证明了这种算法对解决此类方程组问题是收敛的,给出了这种算法收敛的充分条件;对三维TDMA迭代算法采用逐层迭代收敛,证明了这种算法对解决此类方程组问题是收敛的,并出了这种算法收敛的充分条件;以二维受热平板为例,验证了这种算法对解决此类方程组问题是收敛的,并与Gauss-Seidel算法进行了比较. 其次,利用加权GMRES本身构造出一种有效的多项式预处理并与加权GMRES结合,构造了一种新算法.该算法能够显著地减少加权GMRES迭代次数,并能减少其运算量和储存量.数值算例表明,相对于加权GMRES来说,新算法减少了运算时间并降低了迭代次数. 最后,将本文提出的多项式预处理加权GMRES(m)算法应用到流体力学N-S方程求解过程中.以平行板突扩管为例,验证了多项式预处理加权GMRES(m)算法在该问题中的可行性与有效性,并与加权GMRES(m)算法进行比较.

关键词： krylov子空间方法 PWGMRES算法 WGMRES算法 N-S方程

krylov子空间方法并行算法的全局通信策略

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Krylov子空间方法并行算法的全局通信策略

作者：彭波春福建师范大学

学位级别：硕士

绝大部分偏微分方程数值求解问题都可以归结为大型稀疏线性方程组的求解问题,因此设计求解大型稀疏线性方程组的高效算法就成为一个重要课题.求解线性方程组的方法分为直接法和迭代法,当系数矩阵为大规模稀疏矩阵时,常使用迭代法.Krylo... 详细信息

绝大部分偏微分方程数值求解问题都可以归结为大型稀疏线性方程组的求解问题,因此设计求解大型稀疏线性方程组的高效算法就成为一个重要课题.求解线性方程组的方法分为直接法和迭代法,当系数矩阵为大规模稀疏矩阵时,常使用迭代法.krylov子空间方法是求解大型稀疏线性方程组的主流迭代法之一.随着求解问题规模的增加和并行计算机的发展,采用并行算法求解线性方程组就显得势在必行.而在分布式并行计算环境下,内积计算导致的全局通信成为krylov子空间方法高效并行计算求解的瓶颈.针对内积计算导致的全局通信问题,本文研究了平滑共轭残差平方法(SCRS)和预处理共轭残差平方法(PCRS2),其中SCRS算法是通过为共轭残差平方法(CRS)添加一个平滑算子得到的,PCRS2算法是通过对CRS算法附加一个预条件子得到的.在SCRS和PCRS2的基础上,通过改变算法的计算次序,重构算法,提出了改进的适合于分布式并行计算环境的LCSCRS与LCPCRS2算法.在LCSCRS中,我们把三个全局通信点减少为一个;而在LCPCRS2中,将全局通信次数从两次减少为一次.并且每次迭代所需要的内积都是独立的,内积所需要的通信时间能与计算有效重叠.以增加微小的计算量为代价,提高了计算效率.对LCSCRS与SCRS算法,LCPCRS2与PCRS2算法的性能进行了理论分析,包括并行时间、加速比、可扩展性以及并行性能改进比率.结果说明了 LCSCRS算法和LCPCRS2算法分别比SCRS算法和PCRS2算法有更少的并行时间与更好的可扩展性.其中LCSCRS算法的加速比能达到SCRS算法的3倍,并行性能改进比率达到了 66.7%;LCPCRS2算法的加速比能达到PCRS2算法的2倍,并行性能改进比率达到了50%.通过数值实验将PCRS2算法与CRS、共轭梯度平方法(CGS)和双正交共轭梯度稳定法(BiCGSTAB)的计算时间和收敛行为进行了比较,实验结果显示PCRS2有着比CRS、CGS和BiCGSTAB算法更少的计算时间和更为平滑的收敛效果.并行数值实验结果显示LCSCRS与LCPCRS2分别有着比SCRS方法与PCRS2算法更好的加速比和可扩展性,验证了理论分析的结果.

关键词： krylov子空间方法 SCRS算法 PCRS2算法稀疏线性方程组并行计算全局通信

求解大规模矩阵问题的krylov子空间方法

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

南京航空航天大学学报 2001年第2期33卷 139-145页

作者：戴华南京航空航天大学理学院南京210016

求解大规模矩阵问题包括线性方程组和特征值问题等是计算数学和科学工程计算中的重大课题。最近几年 ,其研究工作取得了许多重大进展。文中给出大型线性方程组和特征值问题 krylov子空间方法若干进展的一个概述 ,其中包括作者对这些问... 详细信息

求解大规模矩阵问题包括线性方程组和特征值问题等是计算数学和科学工程计算中的重大课题。最近几年 ,其研究工作取得了许多重大进展。文中给出大型线性方程组和特征值问题 krylov子空间方法若干进展的一个概述 ,其中包括作者对这些问题的研究成果。涉及的专题包括求解大型线性方程组的共轭梯度法、SYMMLQ算法、MINRES算法、GMRES算法、Lanczos双正交化算法、QMR算法以及这些算法的块格式 ;求解大型对称特征值问题的 Lanczos算法和块 Lanczos算法 ;求解大型非对称特征值问题的 Lanczos算法、Arnoldi算法以及这些算法的块推广。讨论求解大规模矩阵问题的加速技术和预处理技术。

关键词：线性方程组特征值 krylov子空间方法大规模矩阵

krylov子空间方法的GPU加速算法研究

在线全文

学校读者我要写书评

暂无评论

Krylov子空间方法的GPU加速算法研究

作者：秦晋国防科学技术大学

学位级别：硕士

近几年来,通用图形处理单元(GPGPU)在体系结构、编程模型等方面迅速发展,可编程性不断提高,同时GPU的单精度浮点峰值性能已经从几个Gflops增长到几个Tflops。GPU开始越来越多的运用于通用计算,并且越来越多地应用到科学计算程序的加速... 详细信息

近几年来,通用图形处理单元(GPGPU)在体系结构、编程模型等方面迅速发展,可编程性不断提高,同时GPU的单精度浮点峰值性能已经从几个Gflops增长到几个Tflops。GPU开始越来越多的运用于通用计算,并且越来越多地应用到科学计算程序的加速研究当中。在科学计算领域中,迭代法求解大型稀疏线性系统在计算流体力学、数值天气预报、石油地震数据处理、材料模拟与设计等实际应用中具有重要的意义,krylov子空间方法是求解大规模稀疏线性系统的有效算法,具有存储容量需求小和快速收敛等优点。然而在CPU上利用该算法求解稀疏线性系统时往往会耗费大量的时间,如何加速其求解具有重要的理论意义和实际应用价值。利用GPU加速krylov子空间方法求解大型稀疏线性系统可以降低计算周期,提高计算效率,有利于加速多种实际问题的解决。本文通过对GPU体系结构和CUDA编程模型的分析,研究了krylov子空间方法在NVIDIA GPU上移植的技术难点,包括稀疏矩阵中零元素对存储空间的浪费、稀疏矩阵向量乘在GPU上的实现、内积操作在GPU上的实现、GPU上实现算法中公式时产生的计算核心开销对性能的降低、NVIDIA GPU不存在归约操作、在NVIDIA GPU上需要采用针对性的优化方法等问题。通过CPU和GPU协作的方式使用CUDA编程模型在NVIDIA GPU上对算法进行了加速,取得了如下的成果: 1,面向CUDA编程模型的算法优化。详细分析NVIDIA GPU的体系结构特点,首先NVIDIA GPU的一个重要特点就是具有复杂的存储层次结构,包括registers、shared memory、local memory、global memory以及两种只读存储器texture memory和constant memory,各种存储器在容量、速度方面有较大的差别,优化算法需要充分利用GPU内的高速存储器,例如shared memory、texture memory甚至是registers。CUDA中的一个与硬件联系比较紧密的概念是warp,在NVIDIA GPU实际运行程序时,warp才是真正的执行单位,在我们的程序优化中,从优化访存入手,线程束能符合warp或者half-warp的对其访问要求。 2,提出稀疏对角矩阵的CDIA压缩存储格式。在DIA存储格式的基础上设计了一种新型的压缩存储格式CDIA,在该格式下能够获得较高的数据传输效率以及满足CUDA对数据的对齐访问。为满足CUDA对存储器的合并访问要求,CDIA压缩存储格式中包含了对压缩矩阵做了相应的转置处理的操作,这大大提高了GPU的访存性能,从而在krylov子空间方法的几个核心操作中起到了重要的作用。在稀疏对角矩阵向量乘中,使用CDIA格式比使用普通DIA格式性能提高了50.3%。 3,稀疏对角矩阵向量乘在GPU上的加速实现。使用CDIA压缩存储格式对矩阵进行压缩存储,将计算任务进行细粒度的任务分配,在NVIDIA C1060平台上使用CUDA编程模型,数据试验结果表明矩阵向量乘的性能有明显的提高,通过对访存、数据传输等的优化,在测试数据中,最高获得了单精度39.6Gflop/s和双精度19.6Gflop/s的浮点计算性能,性能在Nathan Bell和Michael Garland的基础上分别提高了7.6%和17.4%。 4,内积运算在GPU上的实现及优化。内积运算的实现以归约操作的实现为基础,内积运算采用先乘法再归约的方式,借助shared memory在GPU上有良好的性能表现,单精度情况下,与CPU相比,达到了高达36.2倍的加速比。 5,提出了krylov子空间方法在GPU上的优化策略。对算法的优化主要从程序结构、主机与设备的通信以及CUDA编程模型下的存储层次结构等几方面入手,使用NVIDIA GPU上的高速存储部件,主要是shared memory来提高访存效率,同时使用pinned memory来提高通信带宽。这些措施大大提高了算法的整体性能。在NVIDIA C1060平台使用CUDA 3.0的测试结果中,双精度和单精度条件算法性能分别达到11.3Gflop/s和16.7Gflop/s,相比Intel四核处理器Q6600使用三级优化编译,加速比分别达到9.2倍和13.57倍。测试结果表明,在不同矩阵规模下算法的性能有较大的差异,这是由GPU的体系结构特点决定的,从测试数据可以看出,GPU在加速krylov子空间方法求解线性系统中具有较大的优势。

关键词： GPU CUDA krylov子空间方法稀疏对角矩阵向量乘内积操作

解大型线性方程组的轮换重新开始krylov子空间方法(英文)

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

山东大学学报（理学版） 2010年第9期45卷 65-69,89页

作者：陆峰江苏广播电视大学公共管理系江苏南京210036

重新开始krylov子空间方法(包括Galerkin法和最小二乘法)是求解大型线性方程组的一类流行和重要的方法。然而,这类方法容易在收敛过程中发生中断或停滞现象。为了解决这一问题,本文提出一种新的重新开始格式,称之为轮换重新开始格式。... 详细信息

重新开始krylov子空间方法(包括Galerkin法和最小二乘法)是求解大型线性方程组的一类流行和重要的方法。然而,这类方法容易在收敛过程中发生中断或停滞现象。为了解决这一问题,本文提出一种新的重新开始格式,称之为轮换重新开始格式。该格式的基本思想是通过轮流使用方程组系数矩阵与其转置矩阵来生成Kry-lov子空间。轮换重新开始krylov方法的迭代残量容易在各个特征向量方向上取得大致相等的收敛量,从而使得收敛得到改善。数值实验结果表明轮换重新开始krylov子空间方法能够有效解决收敛失败的问题。

关键词：线性方程组迭代法收敛 krylov子空间方法重新开始

三维热传导方程的krylov子空间方法并行分析

在线全文

学校读者我要写书评

暂无评论

计算机应用研究 2010年第4期27卷 1335-1338页

作者：李丹丹程汤培王群中国地质大学(北京)信息工程学院北京100083

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对krylov子空间方法中的CG和GMRES算法进行并行分析,并对... 详细信息

热传导方程在地下水流动数值模拟、油藏数值模拟等工程计算中有着广泛应用,其并行实现是加速问题求解速度、提高问题求解规模的重要手段,因此热传导方程的并行求解具有重要意义。对krylov子空间方法中的CG和GMRES算法进行并行分析,并对不同的预处理CG算法作了比较。在Linux集群系统上,以三维热传导模型为例进行了数值实验。实验结果表明,CG算法比GMRES算法更适合建立三维热传导模型的并行求解。此外,CG算法与BJACOBI预条件子的整合在求解该热传导模型时,其并行程序具有良好的加速比和效率。因此,采用BJACOBI预处理技术的CG算法是一种较好的求解三维热传导模型的并行方案。

关键词： krylov子空间方法线性方程组预条件子热传导方程共轭梯度算法广义极小残量

求解大型稀疏线性方程组的krylov子空间方法的发展

在线全文

学校读者我要写书评

暂无评论

科技导报 2013年第11期31卷 68-73页

作者：李晓爱陈玉花张耘王新苹河南师范大学数学与信息科学学院北京联合大学应用科技学院

求解大型稀疏线性方程组是许多科学和工程计算中最重要的问题之一,krylov子空间方法是求解这类线性方程组的一个研究热点。本文介绍了krylov子空间方法及其分类,例如正交投影方法(或Ritz-Galerkin方法),正交化方法(或极小残差方法),双... 详细信息

求解大型稀疏线性方程组是许多科学和工程计算中最重要的问题之一,krylov子空间方法是求解这类线性方程组的一个研究热点。本文介绍了krylov子空间方法及其分类,例如正交投影方法(或Ritz-Galerkin方法),正交化方法(或极小残差方法),双正交化方法(或Petrov-Galerkin方法),解法方程组的CGNE和CGNR方法等,指出了这些方法在算法设计方面国内外研究现状和存在问题,着重考虑稀疏矩阵向量乘积与内积计算方法的并行处理问题;讨论了预条件与并行预条件技术,残差磨光技术及其并行实现,数据的合理分布问题,内积瓶颈问题等方面研究的发展趋势,希望有更多学者了解和研究这些方法。

关键词：大型稀疏线性方程组迭代法 krylov子空间方法预条件技术

求解矩阵特征值问题的Inverse-free krylov子空间方法

在线全文

学校读者我要写书评

暂无评论

求解矩阵特征值问题的Inverse-free Krylov子空间方法

作者：孟红燕南京航空航天大学

学位级别：硕士

矩阵特征值问题是数值代数领域的重要分支之一，在许多工程计算和现代科学中都有广泛的应用。因此，研究矩阵特征值的求解方法具有重要的理论意义及应用价值。 krylov子空间方法是计算大型广义特征值问题Ax=λBx的极端特征值的有效... 详细信息

矩阵特征值问题是数值代数领域的重要分支之一，在许多工程计算和现代科学中都有广泛的应用。因此，研究矩阵特征值的求解方法具有重要的理论意义及应用价值。 krylov子空间方法是计算大型广义特征值问题Ax=λBx的极端特征值的有效方法。针对krylov子空间方法中大型矩阵求逆的难点，Golub提出了Inverse-free krylov子空间方法。为了能有效地计算内部密集特征值，本文提出了带位移矩阵的Inverse-free krylov子空间方法，并研究其正交基的形成、收敛性分析和算法的实现;为了能够有效地计算多个内部密集特征值且减少计算量，本文提出了带位移矩阵的块Inverse-free krylov子空间方法。用数值实验比较了求解广义对称矩阵内部特征值的krylov子空间方法与Inverse-free krylov子空间方法，数值实验结果表明了算法的有效性。

关键词： krylov子空间方法 Inverse-free 广义特征值问题内部特征值

不适定问题的krylov子空间方法研究及性能分析

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

不适定问题的Krylov子空间方法研究及性能分析

作者：王培电子科技大学

学位级别：硕士

随着科学技术和工程计算的飞速发展,许多实际问题经常需要求解线性不适定问题离散所得的大型线性方程组。例如,第一类Fredholm积分方程问题、反向热导方程的边值问题、数理方程反问题等。求解这类问题的关键是求解其相应的最小二乘问题... 详细信息

随着科学技术和工程计算的飞速发展,许多实际问题经常需要求解线性不适定问题离散所得的大型线性方程组。例如,第一类Fredholm积分方程问题、反向热导方程的边值问题、数理方程反问题等。求解这类问题的关键是求解其相应的最小二乘问题。对于小规模不适定问题的求解,传统的正则化方法较为常用。但是由于计算量和存储量的限制,传统的正则化方法在求解大规模离散不适定问题时常常不适用。krylov子空间方法是目前求解大型不适定问题最为常用的迭代正则化方法。由于科学工程技术发展的需要,陆续涌现出了许多求解工业计算模型中不适定问题的krylov子空间算法,以及许多算法的可用工具箱。krylov子空间方法处理这类大规模问题时,其在数值计算中所展现的特点,体现出这类方法在求解此类相关问题时的卓越之处。例如,其在计算中收敛速度快:矩阵不需分割改变,甚至不需被显示形成。虽然这类方法受误差干扰会出现半收敛现象,但选择合适的正则化参数亦能得到稳定的近似解,因此krylov子空间方法成为处理这类问题较为强大的工具。本论文给出了不适定问题的研究概况,阐述了近年来求解离散不适定问题的krylov子空间方法的相关进展和常用的方法类型,包括经典方法、法方法、扩张方法和灵活预处理方法,并分析了不同算法间的区别与联系以及部分算法的迭代终止准则。基于用右端向量扩张CGLS的思想,以及用用户提供的子空间的基向量扩张GMRES的思想,我们用右端向量和用户提供的子空间的一组基向量同时扩充CGLS,提出了一种新型混合扩张CGLS方法—HACGLS方法。通过求解不适定问题的数值实验表明,HACGLS方法比标准的CGLS方法,和分别用右端向量、特定子空间的基向量扩张CGLS产生的krylov子空间的方法的求解精度高。同时验证了CGLS类krylov子空间方法在求解这类问题方面的优越之处。

关键词： krylov子空间方法不适定问题 HACGLS方法近似解性能分析