面向众核处理器的稀疏线性方程组求解方法研究
发布时间：2021-03-04 15:44
稀疏线性方程组的求解是许多科学计算任务和工程技术问题的核心环节。随着实际问题复杂度的增加,对稀疏线性方程组求解方法的优化研究显得尤为重要。已有的变量部分值相加的方法对三角求解进行了优化,在优化中,分析了变量之间的依赖关系,并通过分解变量求解顺序关联图计算变量的部分值,最后把所有的部分值相加得到变量的最终值。然而,将上述方法直接用于完整的前代-回代过程求解整个方程组时,没有实现对整个稀疏线性方程组的优化求解。原因在于上述方法没有充分利用前代求解过程中得到的变量部分值,而且回代求解要等到前代求解过程全部完成才能开始。根据上述方法存在的不足,本文提出一种基于前代-回代变量求解的相关性分解方法的稀疏线性方程组并行求解算法,该算法在求解整个稀疏方程组时充分利用前代求解过程的中间部分值直接计算得到回代求解中与其相关的变量的部分值,而不需要等待前代求解的变量全部求解完成即可计算回代求解的变量的部分值,有效地加快了方程组的求解速度,实现了稀疏线性方程组的优化求解。本文针对稀疏线性方程组的求解优化问题,提出一种基于前代-回代变量求解的相关性分解方法的稀疏性方程组并行求解算法。该算法的优势在于回代求解无需...
【文章来源】：华北电力大学河北省 211工程院校 教育部直属院校
【文章页数】：52 页
【学位级别】：硕士
【部分图文】：
水平集划分方法
华北电力大学硕士学位论文9a）稀疏矩阵行主序COO压缩存储b）稀疏矩阵列主序COO压缩存储图2-2稀疏矩阵的COO压缩格式2.1.2行压缩存储所谓行压缩存储CSR(CompressedSparseRow)是对稀疏矩阵的非零元素采用按行压缩存储。该方法可以对稀疏矩阵的任一行的非零元素进行高效的存取操作。与列压缩CSC存储的相同之处在于两种方法都是采用三个不同维数的数组存储非零元素的信息。当对于一个非零元素的个数为m的nn阶稀疏矩阵采用行压缩存储时，需要设置三个不同的数组，分别是m1维val、m1维col_index、(n1)1维row_ptr。其中，m1维val存储的是非零元素的值，m1维col_index存储的是非零元素对应所在位置的行索引，(n1)1维row_ptr存储的是每列中第一个非零元素在数组val中的位置，并且row_ptrn1m1。在上述行压缩存储方法中，稀疏矩阵的第i列中的非零元素为val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其对应所在位置的列索引为col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。对图2-1中的稀疏矩阵采用行压缩CSR格式存储，如图2-3所示。图2-3稀疏矩阵的行压缩存储
华北电力大学硕士学位论文9a）稀疏矩阵行主序COO压缩存储b）稀疏矩阵列主序COO压缩存储图2-2稀疏矩阵的COO压缩格式2.1.2行压缩存储所谓行压缩存储CSR(CompressedSparseRow)是对稀疏矩阵的非零元素采用按行压缩存储。该方法可以对稀疏矩阵的任一行的非零元素进行高效的存取操作。与列压缩CSC存储的相同之处在于两种方法都是采用三个不同维数的数组存储非零元素的信息。当对于一个非零元素的个数为m的nn阶稀疏矩阵采用行压缩存储时，需要设置三个不同的数组，分别是m1维val、m1维col_index、(n1)1维row_ptr。其中，m1维val存储的是非零元素的值，m1维col_index存储的是非零元素对应所在位置的行索引，(n1)1维row_ptr存储的是每列中第一个非零元素在数组val中的位置，并且row_ptrn1m1。在上述行压缩存储方法中，稀疏矩阵的第i列中的非零元素为val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其对应所在位置的列索引为col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。对图2-1中的稀疏矩阵采用行压缩CSR格式存储，如图2-3所示。图2-3稀疏矩阵的行压缩存储
【参考文献】：
期刊论文
[1]计算机科学与技术的发展趋势[J]. 郭宇卓. 电子技术与软件工程. 2017(21)
[2]基于不完全LU分解预处理迭代法的电力系统潮流算法[J]. 唐坤杰,董树锋,宋永华. 中国电机工程学报. 2017(S1)
[3]基于GPU通用计算的并行算法和计算框架的实现[J]. 朱宇兰. 山东农业大学学报(自然科学版). 2016(03)
[4]基于图形处理器的电力系统稀疏线性方程组求解方法[J]. 周挺辉,赵文恺,严正,徐得超,江涵. 电力系统自动化. 2015(02)
[5]面向高性能计算的众核处理器结构级高能效技术[J]. 郑方,张昆,邬贵明,高红光,唐勇,吕晖,过锋,李宏亮,谢向辉,陈左宁. 计算机学报. 2014(10)
[6]并行计算的一体化研究现状与发展趋势[J]. 陈国良,孙广中,徐云,龙柏. 科学通报. 2009(08)
[7]《九章算术》与刘徽[J]. 龙泉白. 自然辩证法通讯. 1982(03)
博士论文
[1]线性代数系统迭代解法与预条件方法研究[D]. 沈海龙.东北大学 2013
硕士论文
[1]大规模稀疏线性系统的并行求解方法研究[D]. 宋丽翠.华北电力大学 2019
本文编号：3063479
【文章来源】：华北电力大学河北省 211工程院校 教育部直属院校
【文章页数】：52 页
【学位级别】：硕士
【部分图文】：
水平集划分方法
华北电力大学硕士学位论文9a）稀疏矩阵行主序COO压缩存储b）稀疏矩阵列主序COO压缩存储图2-2稀疏矩阵的COO压缩格式2.1.2行压缩存储所谓行压缩存储CSR(CompressedSparseRow)是对稀疏矩阵的非零元素采用按行压缩存储。该方法可以对稀疏矩阵的任一行的非零元素进行高效的存取操作。与列压缩CSC存储的相同之处在于两种方法都是采用三个不同维数的数组存储非零元素的信息。当对于一个非零元素的个数为m的nn阶稀疏矩阵采用行压缩存储时，需要设置三个不同的数组，分别是m1维val、m1维col_index、(n1)1维row_ptr。其中，m1维val存储的是非零元素的值，m1维col_index存储的是非零元素对应所在位置的行索引，(n1)1维row_ptr存储的是每列中第一个非零元素在数组val中的位置，并且row_ptrn1m1。在上述行压缩存储方法中，稀疏矩阵的第i列中的非零元素为val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其对应所在位置的列索引为col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。对图2-1中的稀疏矩阵采用行压缩CSR格式存储，如图2-3所示。图2-3稀疏矩阵的行压缩存储
华北电力大学硕士学位论文9a）稀疏矩阵行主序COO压缩存储b）稀疏矩阵列主序COO压缩存储图2-2稀疏矩阵的COO压缩格式2.1.2行压缩存储所谓行压缩存储CSR(CompressedSparseRow)是对稀疏矩阵的非零元素采用按行压缩存储。该方法可以对稀疏矩阵的任一行的非零元素进行高效的存取操作。与列压缩CSC存储的相同之处在于两种方法都是采用三个不同维数的数组存储非零元素的信息。当对于一个非零元素的个数为m的nn阶稀疏矩阵采用行压缩存储时，需要设置三个不同的数组，分别是m1维val、m1维col_index、(n1)1维row_ptr。其中，m1维val存储的是非零元素的值，m1维col_index存储的是非零元素对应所在位置的行索引，(n1)1维row_ptr存储的是每列中第一个非零元素在数组val中的位置，并且row_ptrn1m1。在上述行压缩存储方法中，稀疏矩阵的第i列中的非零元素为val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其对应所在位置的列索引为col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。对图2-1中的稀疏矩阵采用行压缩CSR格式存储，如图2-3所示。图2-3稀疏矩阵的行压缩存储
【参考文献】：
期刊论文
[1]计算机科学与技术的发展趋势[J]. 郭宇卓. 电子技术与软件工程. 2017(21)
[2]基于不完全LU分解预处理迭代法的电力系统潮流算法[J]. 唐坤杰,董树锋,宋永华. 中国电机工程学报. 2017(S1)
[3]基于GPU通用计算的并行算法和计算框架的实现[J]. 朱宇兰. 山东农业大学学报(自然科学版). 2016(03)
[4]基于图形处理器的电力系统稀疏线性方程组求解方法[J]. 周挺辉,赵文恺,严正,徐得超,江涵. 电力系统自动化. 2015(02)
[5]面向高性能计算的众核处理器结构级高能效技术[J]. 郑方,张昆,邬贵明,高红光,唐勇,吕晖,过锋,李宏亮,谢向辉,陈左宁. 计算机学报. 2014(10)
[6]并行计算的一体化研究现状与发展趋势[J]. 陈国良,孙广中,徐云,龙柏. 科学通报. 2009(08)
[7]《九章算术》与刘徽[J]. 龙泉白. 自然辩证法通讯. 1982(03)
博士论文
[1]线性代数系统迭代解法与预条件方法研究[D]. 沈海龙.东北大学 2013
硕士论文
[1]大规模稀疏线性系统的并行求解方法研究[D]. 宋丽翠.华北电力大学 2019
本文编号：3063479
本文链接：https://www.wllwen.com/kejilunwen/yysx/3063479.html
