[發(fā)明專利]一種任意階下三角復(fù)矩陣求逆運(yùn)算方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201410156677.4
• 申請(qǐng)日: 2014-04-18
• 公開（公告）號(hào): CN103927290A
• 公開（公告）日: 2014-07-16
• 發(fā)明（設(shè)計(jì)）人: 李麗;楊丹;虞瀟;潘紅兵;何書專;王堃
• 申請(qǐng)（專利權(quán)）人: 南京大學(xué)
• 主分類號(hào): G06F17/16
• 分類號(hào): G06F17/16
• 代理公司: 南京匯盛專利商標(biāo)事務(wù)所(普通合伙) 32238
• 代理人: 陳揚(yáng)

技術(shù)領(lǐng)域

本發(fā)明涉及矩陣求逆的硬件結(jié)構(gòu)及實(shí)現(xiàn)方法，尤其涉及一種任意階下三角復(fù)矩陣求逆運(yùn)算方法。

背景技術(shù)

矩陣求逆的方法有很多，如伴隨矩陣法、初等變換法、分塊矩陣法、高斯消去法等，大多方法都有計(jì)算過程復(fù)雜、存儲(chǔ)資源需求大等問題，不適合在硬件上實(shí)現(xiàn)。目前在硬件平臺(tái)中主要使用的是基于矩陣分解的方法。基于矩陣分解的方法主要有LU分解、QR分解和Cholesky分解三種。其中QR分解雖然適用范圍廣，但計(jì)算過程過于復(fù)雜，不適合在硬件上實(shí)現(xiàn)；Cholesky分解雖然較為簡(jiǎn)單，但只適用于實(shí)對(duì)稱正定矩陣，適用范圍太小，并且開方運(yùn)算會(huì)消耗很多的硬件資源；LU分解的適用條件容易滿足，計(jì)算復(fù)雜度適中，較適合硬件實(shí)現(xiàn)。而三種分解方法都會(huì)產(chǎn)生三角矩陣，其中LU分解將矩陣分解為一個(gè)上三角矩陣和下三角矩陣。因此，研究三角矩陣求逆具有重要的現(xiàn)實(shí)意義。

對(duì)于三角矩陣求逆運(yùn)算的硬件實(shí)現(xiàn)，通常只需開發(fā)下三角矩陣求逆模塊，對(duì)于上三角矩陣，利用矩陣轉(zhuǎn)置的性質(zhì)通過轉(zhuǎn)化復(fù)用下三角矩陣求逆模塊。目前硬件實(shí)現(xiàn)下三角矩陣求逆運(yùn)算使用最為廣泛的是脈動(dòng)陣列結(jié)構(gòu)，其優(yōu)點(diǎn)是并行度高、運(yùn)算執(zhí)行周期少，但是缺點(diǎn)也很明顯：對(duì)硬件資源的消耗很大，其所需的浮點(diǎn)運(yùn)算單元個(gè)數(shù)與矩陣的階數(shù)N呈平方函數(shù)關(guān)系；并且時(shí)序控制較為復(fù)雜，使得運(yùn)算單元之間的數(shù)據(jù)通信很頻繁。雖然經(jīng)過了多次改進(jìn)和優(yōu)化，但脈動(dòng)陣列結(jié)構(gòu)仍然十分復(fù)雜，且難以實(shí)現(xiàn)高階矩陣求逆。目前還沒有任何硬件實(shí)現(xiàn)設(shè)計(jì)能夠有效地解決上述問題，因此，有必要對(duì)下三角矩陣求逆的硬件實(shí)現(xiàn)結(jié)構(gòu)進(jìn)行重新設(shè)計(jì)和優(yōu)化。

發(fā)明內(nèi)容

本發(fā)明目的在于克服以上現(xiàn)有技術(shù)之不足，提供一種任意階下三角復(fù)矩陣求逆運(yùn)算方法，用以支持基于分解的矩陣求逆算法，提高運(yùn)算速度并節(jié)省硬件資源，具體有以下技術(shù)方案實(shí)現(xiàn)：

所述任意階下三角復(fù)矩陣求逆運(yùn)算方法，包括如下步驟：

（1）設(shè)置一取倒單元，用于對(duì)N階矩陣L的對(duì)角線元素進(jìn)行取倒運(yùn)算，并輸出取倒后的矩陣；

（2）設(shè)置一乘累加單元，用于接收所述取倒后的矩陣，對(duì)矩陣第i行中前i-1個(gè)元素進(jìn)行乘累加運(yùn)算并輸出第i行的累加結(jié)果，其中，i為大于等于2的整數(shù)，并且i的初始值為2；

（3）設(shè)置一取反乘單元，用于接收對(duì)應(yīng)于第i行矩陣元素的所述累加結(jié)果，進(jìn)行取反運(yùn)算后再與第i行的對(duì)角線元素相乘，得到逆矩陣L-1的第i行的矩陣元素；

（4）令i自加1，重復(fù)執(zhí)行（2）、（3）步驟，直至i=N，最終得到逆矩陣L^-1。

所述的任意階下三角復(fù)矩陣求逆運(yùn)算方法的進(jìn)一步設(shè)計(jì)在于，所述步驟2）中乘累加單元根據(jù)公式???????????????????????????????????????????????，通過按行計(jì)算的方式，在每一行的計(jì)算過程中，對(duì)不同列的元素采用并行度為M的并行運(yùn)算，其中，S_ij為逆矩陣L^-1的元素表達(dá)。

所述的任意階下三角復(fù)矩陣求逆運(yùn)算方法的進(jìn)一步設(shè)計(jì)在于，所述乘累加單元包括

一個(gè)復(fù)數(shù)乘法器，用于接收對(duì)應(yīng)的l_ik以及S_kj，完成l_ik與S_kj的復(fù)數(shù)相乘操作，并輸出乘法結(jié)果；

一個(gè)復(fù)數(shù)加法器，用于接收所述乘法結(jié)果并完成復(fù)數(shù)加法操作，在輸出所述累加結(jié)果；

以及邏輯控制單元，分別與所述復(fù)數(shù)乘法器與復(fù)數(shù)加法器通信連接，用于實(shí)現(xiàn)帶有流水級(jí)的復(fù)數(shù)加法器的自累加功能。

所述的任意階下三角復(fù)矩陣求逆運(yùn)算方法的進(jìn)一步設(shè)計(jì)在于，所述步驟2中）根據(jù)并行度為M的執(zhí)行運(yùn)算設(shè)定對(duì)應(yīng)的存儲(chǔ)方案，所述存儲(chǔ)方案包括將原矩陣L和結(jié)果矩陣S分別存放在N個(gè)不同的連續(xù)的存儲(chǔ)單元中，所述N個(gè)存儲(chǔ)單元按對(duì)應(yīng)的地址先后順序設(shè)置，其中N為大于等于2M的整數(shù)。

所述的任意階下三角復(fù)矩陣求逆運(yùn)算方法的進(jìn)一步設(shè)計(jì)在于，根據(jù)所述存儲(chǔ)方案建立訪存機(jī)制，所述訪存機(jī)制包括對(duì)于矩陣中的每個(gè)元素，根據(jù)當(dāng)前元素對(duì)應(yīng)的列下標(biāo)數(shù)j與存儲(chǔ)單元總數(shù)N設(shè)定一存儲(chǔ)單元k，代表第k個(gè)存儲(chǔ)單元，k為小于等于N的整數(shù)，并且k=j?mod?N，將其存放在對(duì)應(yīng)的第k組存儲(chǔ)單元中，實(shí)現(xiàn)并行訪存以完成并行度為M的并行運(yùn)算。