竇鑫盛

（河北農(nóng)業(yè)大學海洋學院，秦皇島 066000）

0 引言

矩陣求逆是計算機科學與工程中要解決的一個典型問題［1-2］，在很多計算機研究領域中，矩陣求逆都是基本功能模塊，在機器學習、深度學習和圖像處理等領域有著廣泛的應用。因此，如何高效的求解逆矩陣是一個非常重要的研究方向。高斯-約當消元法是幾個常用的求逆算法之一，其求解過程清晰，輸出穩(wěn)定，尤其在大型矩陣上表現(xiàn)良好，但是高斯-約當消元法的步驟較多，運算量較大，且運算速度較慢［3］。

針對上述缺點，許多學者對此算法進行了不同方式的優(yōu)化。其中，由于高斯-約當消元法的天然并行性，許多學者主要是從并行角度出發(fā)來對算法進行優(yōu)化。劉單等人［4］通過對輸入數(shù)據(jù)進行規(guī)格化處理，使數(shù)據(jù)滿足特定規(guī)范，從而達到提升計算速度的目的。實驗結(jié)果表明，簡單的規(guī)格化可大大減少消元過程或回代過程中的計算次數(shù)，對實數(shù)矩陣的計算速度提升了大約30%。徐勝利［5］使用OpenMP技術編程，在8個CPU和16個獨立處理器內(nèi)核的圖形工作站上獲得了2倍的加速比。楊梅［6］構建了適應于CUDA架構的高斯-約當消元法的并行版本，利用GPU的硬件特性，在維度超過1000時，計算加速比穩(wěn)定在6.4～7.0。Griish Sharma［8］重新設計了CUDA平臺上的高斯-約當消元法，利用NVIDIA GPU內(nèi)核眾多的優(yōu)勢并行優(yōu)化，證明了在有n2線程的計算資源的情況下，算法的復雜度能夠減小到O（n）。Debabrata DasGupta［9］提出了一種空間替換的高斯-約當消元法，通過實現(xiàn)單位矩陣的虛擬存儲，壓縮了部分計算量。現(xiàn)有的對高斯-約當消元法的優(yōu)化未從算法本身的邏輯出發(fā)，未能識別并管理算法在運行中積累的大量的無用的數(shù)據(jù)。

本文從優(yōu)化算法邏輯本身出發(fā)，提出了一種基于滑動窗口與旋轉(zhuǎn)向量的高斯-約當消元法，能夠減少一半的數(shù)據(jù)存儲空間，并壓縮相應計算量，從而從存儲空間和運行時間兩方面提高算法性能。通過實驗，驗證了本文算法的優(yōu)良性能。

1 相關理論

1.1 可逆矩陣

矩陣是現(xiàn)代自然科學、工程技術乃至社會科學許多領域的一個不可缺少的數(shù)學工具，也常見于統(tǒng)計分析等應用數(shù)學學科中。然而矩陣并沒有除法操作，因此當涉及到除法時，就需要對矩陣做求逆變換。矩陣求逆是線性代數(shù)的基本問題之一，同時也是眾多科學與工程計算的核心，許多問題最后都歸結(jié)為求解逆矩陣。因此，一種高效和具有拓展性的矩陣求逆算法在工程應用中顯得非常重要。

1.2 高斯-約當消元法

高斯-約當消元法［6］是一種矩陣求逆的算法，是高斯消元法的另一個版本，在線性代數(shù)中用來計算線性方程組的解。

該算法首先將一個n×n二維輸入矩陣A和一個n×n二維單位矩陣B拼接，組成增廣矩陣（如圖1所示），然后對該組合矩陣進行初等行變換運算，最終將單位矩陣B位置對應的增廣矩陣右側(cè)部分作為結(jié)果輸出（如圖2所示）。算法自左向右逐列處理數(shù)據(jù)，對于列i（i=1，2，3，…，n），運算步驟如下：

圖1 增廣矩陣

圖2 算法輸出矩陣C

（1）選取aii為主元，pivot=aii。

（2）對于第i行，aik/=pivot，bi k/=pi voti（k=i=1，2，3，…，n）。

（3）對于第j行，a jk+=aik*（-aij），bjk+=bik×（-aij），（j=1，2，3，…，n，j≠i），（k=1，2，3，…，n）。

以算法中一個元素的一次乘除換算為基本運算，該算法處理n列，對于每一列完成n列乘2n行次基本運算，該算法共需要2n3次基本運算。同時，計算過程中需要使用n×2n大小空間保存數(shù)據(jù)。因為具有非線性時間和空間復雜度，隨著輸入數(shù)據(jù)增大時，算法運行時間和存儲空間需求將難以接受。

1.3 滑動窗口

滑動窗口是一種流量控制算法，廣泛應用于信號處理和網(wǎng)絡通信領域。比如：TCP協(xié)議簇中的滑動窗口協(xié)議應用滑動窗口算法對網(wǎng)絡數(shù)據(jù)傳輸?shù)牧髁窟M行控制，以避免阻塞的發(fā)生?；瑒哟翱谒惴ㄒ笤O置一個“窗口”，使用“窗口”來限定一個時間點要處理的數(shù)據(jù)量，以達到優(yōu)化吞吐量的目的?；瑒哟翱诩夹g對處理各種流數(shù)據(jù)模型（如DNA序列、信號流、大數(shù)據(jù)中的數(shù)據(jù)流）有非常重要的意義。

2 基于滑動窗口與旋轉(zhuǎn)向量的高斯-約當消元法

針對高斯-約當消元法高計算量、高存儲度的問題，本文提出一種基于滑動窗口與旋轉(zhuǎn)向量的高斯-約當消元法。

2.1 滑動窗口消除無效運算

分析高斯-約當消元法過程（圖3），對于在消除一列的n×2n規(guī)模的初等行變換處理中，有效運算總為n×（n+1）個元素，所以保存一個n×n的窗口可消除無效運算。為了進行下一次變換，左側(cè)一列退出運算，右側(cè)一列加入運算，有效運算的規(guī)模總保持不變。因此將運算壓縮至n×n規(guī)模，既能保證運算的正確性，又消減了運算量?；朔治?，本文采用n×n的窗口方陣進行初等行變換，在逐列處理數(shù)據(jù)過程中，該方陣自左向右滑動，直至增廣矩陣的最右側(cè)，最終窗口方陣保持的數(shù)據(jù)即為輸出結(jié)果。采用窗口方陣后，算法在內(nèi)存中開辟n×n大小空間用于變換處理，消減了內(nèi)存使用量。與標準高斯-約當消元法相比，滑動窗口的引入，使得無論運算次數(shù)還是內(nèi)存開銷都壓縮了將近50%，獲得非常大的性能提升。

圖3 滑動窗口

2.2 旋轉(zhuǎn)向量減少存儲開銷

設當前滑動窗口最左側(cè)列為第m列，最右側(cè)列為第m+n列。初等行變換前第m+n列為單位矩陣中的對角線元素為1、其他位置元素為0的一列，計算結(jié)束后第m列變換為單位矩陣中的對角線元素為1、其他位置元素為0的一列。第m+n列元素取值的特點決定了該列無需保存在存儲中，可通過元素坐標確定，同時，初等行變換后第m列無需保存在存儲中?；趯Τ醯刃凶儞Q的分析，本文提出采用旋轉(zhuǎn)向量進一步優(yōu)化高斯-約當消元法：算法在內(nèi)存中使用一個n×n的二維矩陣進行初等行變換運算。運算前矩陣中保存第m至m+n-1列（見圖4），第m+n列元素取值由元素坐標判斷取值（1或者0）。運算過程中，以滑動窗口縱軸中心線為中心翻轉(zhuǎn)窗口的左右邊界列，使用第m+n列覆蓋第n列，即對于每一行，將計算所得第m+n列的元素值保存在第m列同行元素位置。旋轉(zhuǎn)向量的引入，將計算的存儲空間由n×（n+1）進一步優(yōu)化為n×n，減少了存儲開銷。

圖4 旋轉(zhuǎn)向量

2.3 算法執(zhí)行流程

算法遵循標準高斯-約當消元法的運算流程，自左至右逐列將左側(cè)元素變換為單位矩陣元素。算法運行至第i列時以該列為左側(cè)起始列，向右包含n列，在該n×n矩陣的基礎上進行初等行變換操作，由于滑動窗口的引入，算法執(zhí)行過程中僅需維持一個大小為n×n的矩陣。在變換過程中，第i列將成為單位矩陣的一列，與最終輸出無關，第i+n列由單位

矩陣一列變成與后續(xù)計算和輸出矩陣相關的一列。因此，采用旋轉(zhuǎn)向量方式將第i+n列計算所得覆蓋至第i列，以實現(xiàn)存儲的復用，達到優(yōu)化存儲消耗的目的。具體算法流程如下所示。

算法 基于滑動窗口和旋轉(zhuǎn)向量的高斯-約當消元法偽碼

Input:matrix A,dimension n

Output:inversion matrix C

（1）Function Glide-Window-Gauss-Jordan（A,n）

（2）for each column ci∈n

（3） pivot=A［ci］［ci］

（4） divide_pivot（A,ci,pivot）

（5） A［ci］［ci］=1/pivot

（6） for each row rj∈n and rj≠ci

（7） alpha=-A［rj］［ci］

（8） A［rj］［ci］=0

（9） for each column ck∈n

（10） elimination（A,ci,rj,alpha）

（11）C=A

（12）return C

與標準高斯-約當消元法相比，本文提出的滑動窗口與旋轉(zhuǎn)向量組合的設計將算法的存儲開銷壓縮至n×n，將計算開銷壓縮至n3，相較于高斯-約當消元法減少了一半的計算量和存儲量，大大優(yōu)化了算法的性能。

3 實驗結(jié)果

實驗環(huán)境為一臺戴爾筆記本,CPU主頻為2.80 GHz，8 GB主機內(nèi)存，操作系統(tǒng)為X86_64版本的Ubuntu1 8.04。實驗所有數(shù)據(jù)集采用C++語言庫隨機數(shù)產(chǎn)生函數(shù)生成，數(shù)據(jù)類型為浮點數(shù)。本實驗使用Google-Benchmark性能測試工具，為了進一步減少實驗中的機器運行引入的隨機誤差影響，本文采用每個測試重復50次再取平均值的方法獲得實驗數(shù)據(jù)。

實驗從兩個角度驗證本文提出的基于滑動窗口與旋轉(zhuǎn)向量的高斯-約當消元優(yōu)化算法的性能。實驗一以指數(shù)量級變化輸入數(shù)據(jù)的規(guī)模（圖5）。首先，本文提出的優(yōu)化算法全面快于傳統(tǒng)高斯-約當消元算法，前者比后者快約1/3。其次，兩個算法均呈現(xiàn)指數(shù)增長的趨勢，但本文算法的增長速度明顯慢于傳統(tǒng)的高斯-約當消元法。實驗二以等量遞增方式變化數(shù)據(jù)的規(guī)模（圖6）。執(zhí)行時間方面與實驗一結(jié)果一致，在算法擴展性方面，隨著矩陣階數(shù)的增大，兩個算法耗時的增長差距越來越大。本文提出的優(yōu)化算法比傳統(tǒng)算法運行更快，表明了本文算法在大型矩陣上有更優(yōu)良的性能與擴展性表現(xiàn)。在實驗二中，本文算法在900階是獲得了最大約30%的加速效果。兩個實驗證明隨著矩陣階數(shù)的增大，本文算法在性能與擴展性兩方面具有明顯的優(yōu)勢。

圖5 執(zhí)行時間隨矩陣階數(shù)變化情況（以2的指數(shù)冪增加）

圖6 執(zhí)行時間隨矩陣階數(shù)變化情況（以100等差增加）

4 結(jié)語

針對傳統(tǒng)高斯-約當消元法復雜度高、內(nèi)存消耗較大的問題，本文提出了一種基于旋轉(zhuǎn)向量和滑動窗口的高斯-約當消元優(yōu)化算法。通過實驗驗證了本文算法合理有效，同時也表現(xiàn)了本文算法在大型矩陣求解逆矩陣問題上的計算速度和存儲空間消耗的優(yōu)越性，具有較好的性能優(yōu)勢，同時算法具有較高的拓展性，為有效解決相關數(shù)學問題奠定了計算基礎。