[發明專利]一種采用非正交基的GMRES變型算法

在審

• 申請號: 202110577595.7
• 申請日: 2021-05-26
• 公開（公告）號: CN113343170A
• 公開（公告）日: 2021-09-03
• 發明（設計）人: 曹欣遠;陳明生;齊琦;王道平;況曉靜;孔勐;張量;張忠祥;陳兵兵;范程華
• 申請（專利權）人: 合肥師范學院
• 主分類號: G06F17/12
• 分類號: G06F17/12;G06F17/16
• 代理公司: 合肥市長遠專利代理事務所(普通合伙) 34119
• 代理人: 劉勇

本發明公開了一種采用非正交基的GMRES變型算法，其實現步驟為：S1、選取初始解向量，計算初始殘量，獲取Krylov子空間的第一維基向量；S2、計算系數矩陣與第一維基向量的乘積，任意選取該乘積結果中的部分元素，并對第一維基向量作對應抽取，以二者的內積作為此向量在第一維基向量上的投影系數，由其殘差向量確定Krylov子空間的第二維基向量；S3、以此類推，通過矩陣向量乘、抽取以及求解最小二乘問題，得第三、四、五……維Krylov基向量；S4、通過求解上Hessenberg矩陣方程的最小二乘問題更新殘量，直至殘量小于既定閾值。本發明相較于標準GMRES方法，大幅降低了生成Krylov基向量的計算復雜度，且易與GMRES(m)、QGMRES等方法結合，可用于大規模矩陣方程特別是非對稱線性方程組的求解。

技術領域

本發明涉及科學與工程計算如計算電磁學等技術領域，尤其涉及一種采用非正交基的GMRES變型算法。

背景技術

在應用數學和科學工程計算領域，許多問題的數學模型都可以用線性方程組來描述。例如目標電磁特性仿真計算問題經由矩量法(MoM)、有限元(FEM)等數值算法離散化電磁場微積分方程即轉化為了對矩陣方程的求解，又如流體力學中的Navier-Stokes方程求解、量子色動力學(QCD)中的格點規范理論、慣性約束聚變(ICF)中的三溫能量方程求解、油藏數值模擬、地震反演模擬過程中的Helmholtz偏微分方程求解等。

當系數矩陣為非對稱情況時，廣義最小殘量法(GMRES)特別是帶重啟的GMRES即GMRES(m)則是當今最常用的一類算法。GMRES的運算量主要由矩陣向量乘積和向量正交化兩部分構成，如何進一步降低其計算復雜度一直是一項頗具挑戰性的工作。

發明內容

為有效降低了計算復雜度，為此，本發明提出了一種采用非正交基的GMRES變型算法，具體方案如下：

一種采用非正交基的GMRES變型算法，包括以下步驟：

S1、選取初始解向量，計算初始殘量，獲取Krylov子空間的第一維基向量；

S2、計算系數矩陣與第一維基向量的乘積，任意選取該乘積結果中的部分元素，并對第一維基向量作對應抽取，以二者的內積作為此向量在第一維基向量上的投影系數，由其殘差向量確定Krylov子空間的第二維基向量；

S3、計算系數矩陣與第二維基向量的乘積，再次通過抽取以及求解最小二乘問題獲取新向量在由第一、第二維基向量張成的子空間上的一個斜投影向量，并由相應的殘差向量確定第三維基向量，以此類推，直至獲得第n維基向量；

S4、在每次生成新基向量的同時，根據投影系數向量構建并更新上Hessenberg陣，通過求解其對應的矩陣方程的最小二乘問題，更新殘量，直至殘量為零或小于既定閾值。

具體地說，步驟S1具體為：

S11、建立線性方程組：

Ax＝b (1)

設迭代初值為x₀，則初始殘量為r₀＝b-Ax₀；

S12、任意選取r₀中部分元素記作r_0p，Krylov子空間span{r₀,Ar₀,A²r₀,...,A^n-1r₀}的第一維基向量Q₁由公式(2)確定；

Q₁＝r₀/||r_0p||₂ (2)