检索结果-内蒙古大学图书馆

计算机工程与科学 2010年第12期32卷 89-93,101页

作者：骆志刚仲妍吴枫国防科学技术大学计算机学院湖南长沙410073

稀疏线性方程组的高效求解是数值计算方向的研究热点之一,其中包括预处理技术的研究。本文从技术分类的角度,总结了稀疏线性方程组求解中的预处理技术。首先,介绍了填充元缩减策略,旨在减少求解过程中存储量的同时,仍能保持矩阵的稀疏结... 详细信息

稀疏线性方程组的高效求解是数值计算方向的研究热点之一,其中包括预处理技术的研究。本文从技术分类的角度,总结了稀疏线性方程组求解中的预处理技术。首先,介绍了填充元缩减策略,旨在减少求解过程中存储量的同时,仍能保持矩阵的稀疏结构;其次,介绍了不同结构系数矩阵的多种匹配技术,旨在获得矩阵的对角优势性;最后,介绍了具有天然并行性的因子分解近似逆预条件子构造方法和不完全分解预条件中的并行求解技术等。

关键词：稀疏线性方程组预处理技术预条件子

来源：评论

学校读者我要写书评

暂无评论

求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法

引用

同济大学学报（自然科学版） 2020年第8期48卷 1224-1231,1240页

作者：杜亦疏殷俊锋张科同济大学数学科学学院上海200092 上海海事大学文理学院上海201306

基于一种从系数矩阵中选取工作行的新概率准则提出一类求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法.理论表明该方法收敛到相容线性方程组的最小范数解,而且该方法的理论收敛因子小于经典随机Kaczmarz方法的收敛因子.数值实验表... 详细信息

基于一种从系数矩阵中选取工作行的新概率准则提出一类求解大型稀疏线性方程组的贪婪距离随机Kaczmarz方法.理论表明该方法收敛到相容线性方程组的最小范数解,而且该方法的理论收敛因子小于经典随机Kaczmarz方法的收敛因子.数值实验表明该方法比传统的随机Kaczmarz方法收敛更快.

关键词： Kaczmarz方法稀疏线性方程组收敛性随机迭代

来源：评论

学校读者我要写书评

暂无评论

基于变量相关性分解方法的稀疏线性方程组并行求解算法

引用

清华大学学报（自然科学版） 2020年第4期60卷 312-320页

作者：刘珊瑕靳松王文琛汪宇航王瑜华北电力大学电子与通信工程系保定071001

稀疏线性方程组的求解是许多大规模科学计算任务的核心环节。目前,并行算法的发展为稀疏线性方程组的求解提供了新的思路和强有力的工具。然而,现有的并行算法存在一些缺陷,如最优子矩阵的划分难以获得、并行任务间的同步开销较大等。... 详细信息

稀疏线性方程组的求解是许多大规模科学计算任务的核心环节。目前,并行算法的发展为稀疏线性方程组的求解提供了新的思路和强有力的工具。然而,现有的并行算法存在一些缺陷,如最优子矩阵的划分难以获得、并行任务间的同步开销较大等。针对上述问题,该文提出一种基于变量相关性分解方法的稀疏线性方程组并行求解算法。该算法首先对系数矩阵进行不完全LU分解,得到上三角和下三角方程组,然后在这2个方程组求解过程中利用y与x的关系分解变量的相关性,同时并行计算变量的独立部分值,最后将所有的独立部分值相加得到变量的最终值。由于算法中变量的求解无需等待其所有前继变量计算完成即可进行部分值计算,因此有效减少了算法的执行时间,进而提高了算法的求解速度及并行度。实验结果表明:与调用cusparse库函数实现的并行求解方法相比,该文提出的算法能将稀疏线性方程组的求解速度提升了50%以上。

关键词：图形处理器稀疏线性方程组并行计算变量部分值线程

来源：评论

学校读者我要写书评

暂无评论

稀疏线性方程组的一种预处理并行算法

引用

纺织高校基础科学学报 2012年第2期25卷 180-183页

作者：刘秀敏吕全义杜艳君西北工业大学应用数学系陕西西安710129

给出了一种求解系数矩阵为稀疏对称正定矩阵的线性方程组的预处理共轭梯度法的并行算法.该方法提出了迭代法的预处理模式.基于此思想,首先给出预条件子M,然后构造并行迭代求解预处理方程组的迭代格式,进而使用共轭梯度法并行求解.通过... 详细信息

给出了一种求解系数矩阵为稀疏对称正定矩阵的线性方程组的预处理共轭梯度法的并行算法.该方法提出了迭代法的预处理模式.基于此思想,首先给出预条件子M,然后构造并行迭代求解预处理方程组的迭代格式,进而使用共轭梯度法并行求解.通过数值试验,与直接使用共轭梯度法及传统的预处理共轭梯度方法(迭代1次)相比,该方法提高了收敛速度,同时具有很好的并行性.

关键词：并行算法预处理共轭梯度法预处理方程组稀疏线性方程组

来源：评论

学校读者我要写书评

暂无评论

稀疏线性方程组不完全分解预条件方法

引用

计算机工程与科学 2006年第8期28卷 59-62页

作者：李晓梅吴建平装备指挥技术学院信息装备系北京101416 国防科技大学计算机学院湖南长沙410073

稀疏线性方程组的高效求解在科学计算与工程应用中起着十分重要的作用。本文系统介绍一般稀疏线性方程组和块三对角线性方程组的不完全预条件构造技术,同时介绍我们提出的多行双门槛不完全分解预条件子MRILUT和局部块不完全分解预条件子... 详细信息

稀疏线性方程组的高效求解在科学计算与工程应用中起着十分重要的作用。本文系统介绍一般稀疏线性方程组和块三对角线性方程组的不完全预条件构造技术,同时介绍我们提出的多行双门槛不完全分解预条件子MRILUT和局部块不完全分解预条件子LBF2(l)构造方法,并将它们应用于二维三温能量方程组的离散求解与二维Laplace微分方程的离散求解中,取得了满意的结果。

关键词：预条件技术不完全分解预条件方法稀疏线性方程组

来源：评论

学校读者我要写书评

暂无评论

稀疏线性方程组求解中关键算子优化

稀疏线性方程组求解中关键算子优化

引用

作者：姜佳凡青海大学

学位级别：硕士

稀疏线性方程组求解是最基础的数值计算方法之一,在科学计算、工程建模等领域有着重要的应用。随着稀疏线性方程组的问题规模不断扩大,需要求解的方程组阶数逐渐增加,求解时间也随之增长。对稀疏线性方程组求解过程中的关键算子进行并... 详细信息

稀疏线性方程组求解是最基础的数值计算方法之一,在科学计算、工程建模等领域有着重要的应用。随着稀疏线性方程组的问题规模不断扩大,需要求解的方程组阶数逐渐增加,求解时间也随之增长。对稀疏线性方程组求解过程中的关键算子进行并行优化、减少求解过程的时间开销变得至关重要。稀疏线性方程组求解包括直接法和迭代法两种主要策略,SpMV是迭代法求解过程中的重要计算过程,在每次迭代中,都需要通过SpMV计算更新解向量,然而,这一过程占据了大量的计算时间,对于SpMV的并行优化一直是重要的研究方向。随着GPU技术的进步,计算性能的提高带来了比CPU更大的优势,为SpMV计算带来了更高的性能要求,GPU上的SpMV计算仍存在负载不够均衡、计算程序通用性差等问题,针对GPU硬件特性进行并行优化能够为稀疏线性方程组的迭代法求解带来巨大的计算效率提升。然而,在使用直接法求解稀疏对称不定线性方程组时,矩阵中存在的极小对角元会引入计算精度误差,通过使用对称权重匹配算法寻找匹配顶点,实现增强矩阵主元的功能,保证后续求解过程的计算精度并减少计算过程中的空间开销,但寻找匹配顶点的过程会带来大量的查找时间,对于对称权重匹配算法的并行优化能够提升稀疏对称线性方程组直接法求解的增强主元过程的计算效率,进而减少直接法求解过程的整体时间,对称权重匹配算法仍存在算法依赖性强,并行化复杂等问题。为了解决SpMV算法与对称权重匹配算法的并行问题,本文从以下三个方面对稀疏线性方程组求解的算子展开研究: (1)为了解决GPU上SpMV计算中存在的多核心计算负载不均衡、硬件利用率低等问题,本文设计了一种多计算内核的负载均衡计算方法,首先基于CSR数据以行为单位切分得到多个数据行,再设计了四种计算内核适用于不同规模的数据行,并为计算内核设计了动态和静态的任务调度方式,最后,根据计算内核的性能表现设计了数据行与计算内核的分配策略,实现了以行数据为单位的SpMV负载均衡计算。实验结果表明,在V100平台上相比Light SpMV、cusparse CSR、cusparse HYB分别达到了1.78倍、2.02倍和1.54倍的加速。 (2)为了解决已有的固定计算方法在多种GPU和不同稀疏数据上性能发挥不稳定的问题,提高并行计算方法的通用性,本文设计了一种自动调优的数据完全等分的计算方法;首先设计了一种平均切分CSR格式数据的数据划分方法;再实现了访存优化和边界数据并行化处理;通过数据收集与性能建模实现了根据数据自动选择最优的数据切分方式的自动调优方法,实现了根据GPU型号与稀疏矩阵数据特征自动选择数据平均切分数量,从而支持在多种GPU平台上负载均衡的SpMV计算。实验结果表明,与Light SpMV、CSR5、Merge、cu Sparse CSR和cu Sparse HYB算法相比,在T4平台上获得了1.58倍、1.86倍、1.27倍、1.28倍和1.33倍的平均加速,在1080Ti平台上获得的平均加速分别为1.04倍、1.68倍、1.12倍、1.04倍和1.22倍。 (3)为了解决对称权重匹配算法依赖性强,并行化复杂等问题,本文设计并使用了极大基数匹配、最大基数匹配、完美最大权重匹配和对称约束对串行算法进行等效替换;再对极大基数匹配进行了数据结构和搜索算法优化,对最大基数匹配和完美最大权重匹配实现了多进程多线程并行优化,消除了对称权重匹配计算过程的依赖性,并实现了有效的并行加速。实验结果表明,与串行算法相比,8线程加速比达到4.46倍,16线程加速比达到6.8倍,32线程加速比达到10.63倍,4进程共128线程加速比达到17.33倍。

关键词：稀疏线性方程组 SpMV 对称权重匹配并行计算

来源：评论

学校读者我要写书评

暂无评论

基于异构并行环境的大型稀疏线性方程组求解的任务映射算法

引用

电子学报 1999年第8期27卷 102-104页

作者：舒继武赵金熙张德富周维四南京大学计算机软件新技术国家重点实验室南京大学计算机科学与技术系胜利油田地质科学研究院

本文基于异构并行环境，针对大型稀疏形线性方程组的并行求解，给出了求解方程组的静态任务映射，提出了合理的任务映射费用函数，并运用模拟退火算法寻找最佳任务映射，从而将一类不均匀任务合理地映射到异构并行环境中高效地并行求解。

关键词：大型任务映射稀疏线性方程组算法解

来源：评论

学校读者我要写书评

暂无评论

解大型稀疏线性方程组的一种有效并行ICCG法

引用

计算机工程与应用 1999年第7期35卷 30-31,34页

作者：舒继武赵金熙张德富南京大学计算机软件新技术国家重点实验室南京210093 南京大学计算机系南京210093

该文分析了不完全Cholesky分解预处理共轭梯度（ICCG）法各部分的计算量，给出了占ICCG法主要计算时间的解预处理方程的并行算法，它既有比目前迭代算法快的收敛速度，又有较好的并行度。

关键词：稀疏线性方程组 ICCG法并行迭代

来源：评论

学校读者我要写书评

暂无评论

大型稀疏线性方程组的新型预条件算法研究

大型稀疏线性方程组的新型预条件算法研究

引用

作者：张慧荣中国科学院大学

学位级别：博士

本论文意图为大规模非对称的线性方程组Ax=b并行求解器提供一个兼顾高可扩展性和高逼近精度的新型预条件子核心部件，称之为LST类预条件子，其基于系数矩阵的对称部分而形成，算法构造依托于权重连通图及相关联的Laplacian矩阵和广义逆... 详细信息

本论文意图为大规模非对称的线性方程组Ax=b并行求解器提供一个兼顾高可扩展性和高逼近精度的新型预条件子核心部件，称之为LST类预条件子，其基于系数矩阵的对称部分而形成，算法构造依托于权重连通图及相关联的Laplacian矩阵和广义逆矩阵。LST类预条件子的算法构造基于两个理论系统，其一为分解理论，主要解决新型预条件子的高可扩展性;其二为近似理论，主要解决新型预条件子的高逼近精度。\n LST类预条件子的并行程序实现尽力地保持了权重连通图的局部特性，该特性一方面由聚类形的局地表达方式体现，以Cheeger值和Cheeger常数作为度量函数;另一方面由骨架形的主干路表达方式体现，以均值Stretch值和均值Stretch常数作为度量函数。\n LST类预条件子高逼近精度的程序实现尽力地近似了原系数矩阵对应的权重连通图的广义条件数和谱分布，其逼近精度的度量和控制主要采用了两种模式:其一是矩阵A和B之间的谱范数逼近，通过引入广义条件数来实现;其二是矩阵A和B之间的Frobenius范数逼近，通过特征值的和（迹算子）之间的逼近进行实现。新型预条件子对应于权重连通图的谱稀疏化子图，稀疏化子图与原图之间的逼近由迹算子的逼近进行度量，它又归结为以均值Stretch值/均值Stretch常数为测度的逼近度量。\n LST类预条件子的程序实现有三个核心算法模块，其一是权重连通图的局部特性保持的算法模块，据此得到系统矩阵的大尺度聚类剖分和中小尺度区域分解;其二是权重连通图的谱稀疏化子图算法与（过）抽样算法模块，其有效利用了大规模集成电路网格的等效电路原理与有效电阻概念，将预条件子与系数矩阵之间的逼近问题转化为广义逆矩阵之间的逼近问题，利用（过）抽样算法的不等式约束手段，得到了近似线性时间开销的高逼近精度的稀疏广义逆，从而得到了高逼近精度的谱稀疏化子图的快速构造算法;其三是Low stretch生成树(LST)模块，它利用分层递进式的Petal-分解策略、分级逐层地渐进式地构造了权重连通图的Low stretch生成树，从而将连通图的全局特性与局地特性有效地融合起来，并为谱稀疏化子图的形成提供了骨架式的主干路，该模块因此而成为新型预处理算法的基础算法模块。\n 本论文基于通信极小化的图剖分算法、具有(ε)-approx逼近精度的谱稀疏化子图算法、基于Petal-分解的Low stretch生成树算法等构造理论与算法实现，对新型的LST类预条件子进行了系统地理论分析与算法研究，由此给出了求解非对称线性方程组的高可扩展高计算精度的预条件子的核心算法组件;在程序设计和算法实现的基础上，本文利用理论算例、数值算例和应用算例，对LST类预条件子的剖分效果、逼近效果、聚类质量、谱分布效果、求解器加速效果等进行了定性和定量的数值试验与数值分析。\n 本论文在LST类预条件子的算法构造过程中，系统性的研究了将分解理论与近似理论有机融合的预处理算法构造理论，有效地构建了将聚类形的局地表达方式与骨架形的全局表达方式融合在一起的谱稀疏化子图算法及其程序，充分地使用了分层递进式Petal分解和Low stretch生成树在大尺度聚类剖分中的通信极小化特性，从而得到了兼顾高可扩展性和高逼近精度的新型预条件子。上述的理论研究和算法实现构成了本论文的创新性工作。

关键词：稀疏线性方程组预条件算法逼近精度谱稀疏化子图通信极小化

来源：评论

学校读者我要写书评

暂无评论

一般稀疏线性方程组的因子组合型并行预条件研究

引用

计算机应用与软件 2012年第5期29卷 6-9,108页

作者：吴建平赵军马怀发宋君强张卫民李晓梅国防科技大学计算机学院湖南长沙410073 中国水利水电科学研究院北京100044 装备指挥技术学院北京101416

基于因子组合给出一般稀疏线性方程组的一种新并行预条件。在该方案中,应用基于邻接图的重叠区域分解,形成一串相互重叠的子区域。对每个子区域,可以采用任何不完全LU分解。之后,利用全局三角因子与全局下三角因子的乘积作为全局的并行... 详细信息

基于因子组合给出一般稀疏线性方程组的一种新并行预条件。在该方案中,应用基于邻接图的重叠区域分解,形成一串相互重叠的子区域。对每个子区域,可以采用任何不完全LU分解。之后,利用全局三角因子与全局下三角因子的乘积作为全局的并行预条件,其中全局三角因子利用限制加性Schwarz思想对每个局部上三角因子的逆进行组合得到。分析表明,提出的预条件优于经典加性Schwarz和限制加性Schwarz,且能保持对称正定性。对混凝土细观数值模拟中线性方程组的实验再次表明,新方案优于经典加性Schwarz。

关键词：并行计算稀疏线性方程组预条件不完全分解混凝土模拟有限元

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：