稀疏線(xiàn)性方程組的求解是許多科學(xué)計(jì)算任務(wù)和工程技術(shù)問(wèn)題的核心環(huán)節(jié)。隨著實(shí)際問(wèn)題復(fù)雜度的增加,對(duì)稀疏線(xiàn)性方程組求解方法的優(yōu)化研究顯得尤為重要。已有的變量部分值相加的方法對(duì)三角求解進(jìn)行了優(yōu)化,在優(yōu)化中,分析了變量之間的依賴(lài)關(guān)系,并通過(guò)分解變量求解順序關(guān)聯(lián)圖計(jì)算變量的部分值,最后把所有的部分值相加得到變量的最終值。然而,將上述方法直接用于完整的前代-回代過(guò)程求解整個(gè)方程組時(shí),沒(méi)有實(shí)現(xiàn)對(duì)整個(gè)稀疏線(xiàn)性方程組的優(yōu)化求解。原因在于上述方法沒(méi)有充分利用前代求解過(guò)程中得到的變量部分值,而且回代求解要等到前代求解過(guò)程全部完成才能開(kāi)始。根據(jù)上述方法存在的不足,本文提出一種基于前代-回代變量求解的相關(guān)性分解方法的稀疏線(xiàn)性方程組并行求解算法,該算法在求解整個(gè)稀疏方程組時(shí)充分利用前代求解過(guò)程的中間部分值直接計(jì)算得到回代求解中與其相關(guān)的變量的部分值,而不需要等待前代求解的變量全部求解完成即可計(jì)算回代求解的變量的部分值,有效地加快了方程組的求解速度,實(shí)現(xiàn)了稀疏線(xiàn)性方程組的優(yōu)化求解。本文針對(duì)稀疏線(xiàn)性方程組的求解優(yōu)化問(wèn)題,提出一種基于前代-回代變量求解的相關(guān)性分解方法的稀疏性方程組并行求解算法。該算法的優(yōu)勢(shì)在于回代求解無(wú)需... 

【文章來(lái)源】：華北電力大學(xué)河北省 211工程院校 教育部直屬院校

【文章頁(yè)數(shù)】：52 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

水平集劃分方法

華北電力大學(xué)碩士學(xué)位論文9a）稀疏矩陣行主序COO壓縮存儲(chǔ)b）稀疏矩陣列主序COO壓縮存儲(chǔ)圖2-2稀疏矩陣的COO壓縮格式2.1.2行壓縮存儲(chǔ)所謂行壓縮存儲(chǔ)CSR(CompressedSparseRow)是對(duì)稀疏矩陣的非零元素采用按行壓縮存儲(chǔ)。該方法可以對(duì)稀疏矩陣的任一行的非零元素進(jìn)行高效的存取操作。與列壓縮CSC存儲(chǔ)的相同之處在于兩種方法都是采用三個(gè)不同維數(shù)的數(shù)組存儲(chǔ)非零元素的信息。當(dāng)對(duì)于一個(gè)非零元素的個(gè)數(shù)為m的nn階稀疏矩陣采用行壓縮存儲(chǔ)時(shí)，需要設(shè)置三個(gè)不同的數(shù)組，分別是m1維val、m1維col_index、(n1)1維row_ptr。其中，m1維val存儲(chǔ)的是非零元素的值，m1維col_index存儲(chǔ)的是非零元素對(duì)應(yīng)所在位置的行索引，(n1)1維row_ptr存儲(chǔ)的是每列中第一個(gè)非零元素在數(shù)組val中的位置，并且row_ptrn1m1。在上述行壓縮存儲(chǔ)方法中，稀疏矩陣的第i列中的非零元素為val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其對(duì)應(yīng)所在位置的列索引為col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。對(duì)圖2-1中的稀疏矩陣采用行壓縮CSR格式存儲(chǔ)，如圖2-3所示。圖2-3稀疏矩陣的行壓縮存儲(chǔ)

華北電力大學(xué)碩士學(xué)位論文9a）稀疏矩陣行主序COO壓縮存儲(chǔ)b）稀疏矩陣列主序COO壓縮存儲(chǔ)圖2-2稀疏矩陣的COO壓縮格式2.1.2行壓縮存儲(chǔ)所謂行壓縮存儲(chǔ)CSR(CompressedSparseRow)是對(duì)稀疏矩陣的非零元素采用按行壓縮存儲(chǔ)。該方法可以對(duì)稀疏矩陣的任一行的非零元素進(jìn)行高效的存取操作。與列壓縮CSC存儲(chǔ)的相同之處在于兩種方法都是采用三個(gè)不同維數(shù)的數(shù)組存儲(chǔ)非零元素的信息。當(dāng)對(duì)于一個(gè)非零元素的個(gè)數(shù)為m的nn階稀疏矩陣采用行壓縮存儲(chǔ)時(shí)，需要設(shè)置三個(gè)不同的數(shù)組，分別是m1維val、m1維col_index、(n1)1維row_ptr。其中，m1維val存儲(chǔ)的是非零元素的值，m1維col_index存儲(chǔ)的是非零元素對(duì)應(yīng)所在位置的行索引，(n1)1維row_ptr存儲(chǔ)的是每列中第一個(gè)非零元素在數(shù)組val中的位置，并且row_ptrn1m1。在上述行壓縮存儲(chǔ)方法中，稀疏矩陣的第i列中的非零元素為val[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)，其對(duì)應(yīng)所在位置的列索引為col_index[j](jrow_ptr[i],row_ptr[i]1,,row_ptr[i1]1)。對(duì)圖2-1中的稀疏矩陣采用行壓縮CSR格式存儲(chǔ)，如圖2-3所示。圖2-3稀疏矩陣的行壓縮存儲(chǔ)

【參考文獻(xiàn)】：
期刊論文
[1]計(jì)算機(jī)科學(xué)與技術(shù)的發(fā)展趨勢(shì)[J]. 郭宇卓.  電子技術(shù)與軟件工程. 2017(21)
[2]基于不完全LU分解預(yù)處理迭代法的電力系統(tǒng)潮流算法[J]. 唐坤杰,董樹(shù)鋒,宋永華.  中國(guó)電機(jī)工程學(xué)報(bào). 2017(S1)
[3]基于GPU通用計(jì)算的并行算法和計(jì)算框架的實(shí)現(xiàn)[J]. 朱宇蘭.  山東農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版). 2016(03)
[4]基于圖形處理器的電力系統(tǒng)稀疏線(xiàn)性方程組求解方法[J]. 周挺輝,趙文愷,嚴(yán)正,徐得超,江涵.  電力系統(tǒng)自動(dòng)化. 2015(02)
[5]面向高性能計(jì)算的眾核處理器結(jié)構(gòu)級(jí)高能效技術(shù)[J]. 鄭方,張昆,鄔貴明,高紅光,唐勇,呂暉,過(guò)鋒,李宏亮,謝向輝,陳左寧.  計(jì)算機(jī)學(xué)報(bào). 2014(10)
[6]并行計(jì)算的一體化研究現(xiàn)狀與發(fā)展趨勢(shì)[J]. 陳國(guó)良,孫廣中,徐云,龍柏.  科學(xué)通報(bào). 2009(08)
[7]《九章算術(shù)》與劉徽[J]. 龍泉白.  自然辯證法通訊. 1982(03)

博士論文
[1]線(xiàn)性代數(shù)系統(tǒng)迭代解法與預(yù)條件方法研究[D]. 沈海龍.東北大學(xué) 2013

碩士論文
[1]大規(guī)模稀疏線(xiàn)性系統(tǒng)的并行求解方法研究[D]. 宋麗翠.華北電力大學(xué) 2019



本文編號(hào)：3063479