一種基于滑動(dòng)窗口與旋轉(zhuǎn)向量的高斯-約當(dāng)消元算法

竇鑫盛

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

0 引言

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

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

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

1 相關(guān)理論

1.1 可逆矩陣

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

1.2 高斯-約當(dāng)消元法

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

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

圖1 增廣矩陣

圖2 算法輸出矩陣C

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

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

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

以算法中一個(gè)元素的一次乘除換算為基本運(yùn)算，該算法處理n列，對(duì)于每一列完成n列乘2n行次基本運(yùn)算，該算法共需要2n3次基本運(yùn)算。同時(shí)，計(jì)算過程中需要使用n×2n大小空間保存數(shù)據(jù)。因?yàn)榫哂蟹蔷€性時(shí)間和空間復(fù)雜度，隨著輸入數(shù)據(jù)增大時(shí)，算法運(yùn)行時(shí)間和存儲(chǔ)空間需求將難以接受。

1.3 滑動(dòng)窗口

滑動(dòng)窗口是一種流量控制算法，廣泛應(yīng)用于信號(hào)處理和網(wǎng)絡(luò)通信領(lǐng)域。比如：TCP協(xié)議簇中的滑動(dòng)窗口協(xié)議應(yīng)用滑動(dòng)窗口算法對(duì)網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)牧髁窟M(jìn)行控制，以避免阻塞的發(fā)生。滑動(dòng)窗口算法要求設(shè)置一個(gè)“窗口”，使用“窗口”來限定一個(gè)時(shí)間點(diǎn)要處理的數(shù)據(jù)量，以達(dá)到優(yōu)化吞吐量的目的。滑動(dòng)窗口技術(shù)對(duì)處理各種流數(shù)據(jù)模型（如DNA序列、信號(hào)流、大數(shù)據(jù)中的數(shù)據(jù)流）有非常重要的意義。

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

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

2.1 滑動(dòng)窗口消除無效運(yùn)算

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

圖3 滑動(dòng)窗口

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

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

圖4 旋轉(zhuǎn)向量

2.3 算法執(zhí)行流程

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

4 結(jié)語(yǔ)

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