[發明專利]一種穩定的基于Spark平臺的矩陣求逆算法

在審

• 申請號: 201810327881.6
• 申請日: 2018-04-12
• 公開（公告）號: CN108519959A
• 公開（公告）日: 2018-09-11
• 發明（設計）人: 郭海旋;任江濤
• 申請（專利權）人: 中山大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 林麗明

本發明基于傳統的Strassen矩陣求逆算法上對其進行修改，實現了一種能緩解這種數值穩定性問題的方法。類似于Strassen矩陣求逆算法，不過本發明對其進行矩陣旋轉操作，使Strassen矩陣求逆算法遞歸時其對進行求逆，那么當比更加良態的時候，就使用旋轉后的算法求逆，以提升數值穩定性。

技術領域

本發明涉及Spark平臺技術領域，更具體地，涉及一種穩定的基于Spark平臺的矩陣求逆算法。

背景技術

由于Spark平臺在2012年被提出，主要集中在大數據處理領域，尚不支持大型矩陣的求逆運算，而在Spark平臺上的大型矩陣求逆算法的研究也非常少，只有2016年LIU等人提出的基于遞歸LU分解的算法以及2018年Misra等人提出的基于Strassen的遞歸求逆算法(SPIN)，本發明基于后者，即是SPIN。

Strassen算法由Strassen發表于1969年，它應用于矩陣乘法的方法因為把矩陣乘法的復雜度從O(n³)降低到O(n^2.8)而廣為人知，Strassen同時提出的求逆算法則沒有那么高的知名度。類似于Strassen矩陣乘法，對于

有

那么C矩陣可以通過以下步驟計算得出：

P₂＝A₂₁×P₁

P₃＝P₁×A₁₂

P₄＝A₂₁×P₃

P₅＝P₄-A₂₂

C₁₂＝P₃×P₆

C₂₁＝P₆×P₂

C₁₁＝P₁-P₃×C₂₁

C₂₂＝-P₆

對子矩陣A₁₁遞歸使用該算法(SPIN)，到達遞歸的頂點時，使用已有求逆算法(如LU分解)求解矩陣的逆，執行所有步驟后即可得到矩陣C。Strassen求逆算法的偽代碼如圖1所示，圖2給出了Spark版本的Strassen矩陣求逆算法偽代碼。

Spark版本的Strassen求逆算法，主要涉及到六個函數:

■breakMat：把矩陣分成4個塊

■xy：即圖2中的_11、_12、_21、_22等四個函數，作用是獲取對應位置的子矩陣塊

■multiply：矩陣乘法，使用Spark自帶的矩陣乘法

■subtract：矩陣減法，使用Spark自帶的矩陣減法

■scalarMul：矩陣乘以一個常數

■arrange：把四個矩陣塊合并成一個大矩陣