[發明專利]通過KRYLOV子空間擴展求解具有多個右端的線性方程組的技術

無效

• 申請號: 201310300852.8
• 申請日: 2013-07-17
• 公開（公告）號: CN103577385A
• 公開（公告）日: 2014-02-12
• 發明（設計）人: 羅伯特·斯特茲歐迪卡
• 申請（專利權）人: 輝達公司
• 主分類號: G06F17/12
• 分類號: G06F17/12
• 代理公司: 北京市磐華律師事務所 11336
• 代理人: 徐丁峰;魏寧

相關申請的交叉引用

本申請要求于2012年7月17日提交的、序列號為61/672,487的美國臨時專利申請的優先權，在此通過援引的方式對其加以合并。

技術領域

本發明總地涉及通用計算，并且，更具體地，涉及用于通過克雷洛夫（Krylov）子空間擴展求解具有多個右端（right?hand?side）的線性方程組的技術。

背景技術

線性方程組出現在諸如化學、結構分析、物理、數學等范圍廣泛的領域內的科學計算的許多應用中。并且求解這種線性方程組是使用在這些領域中的許多算法的重要部分，諸如化學處理仿真算法。眾所周知的是，線性方程組可以以矩陣形式表示為Ax=RHS。通常，包括在線性方程組中的元素基于問題的類型而展現出相似性。具體來講，許多實際問題導致包括大型稀疏A矩陣的線性方程組。注意，在包括N行的稀疏矩陣中，非零系數的數目是（以大寫O標記）O（N）而不是O（N²）。進一步地，一些包括相同大型稀疏A矩陣的線性方程組用來求解具有許多不同但相關的右端向量（RHS）的方程組。然而，對于大型矩陣A，確定針對甚至一個右端向量的精確解x可能也要求太多存儲器和太多時間才能發揮作用。因此，使用迭代技術來生成近似解。

在求解包括與多個相關右端向量相耦合的相同大型矩陣A的線性方程組的一個方法中，每個右端向量被作為獨立問題對待。例如，Krylov迭代解算器可用來針對每個RHS分別查找近似解x。Krylov迭代解算器典型地生成近似解的初始猜測并構建由迭代解算器根據初始殘差（即RHS-Ax）所創建的Krylov子空間的標準正交基。隨后，Krylov迭代解算器通過最小化殘差而生成逐次近似解。針對每次迭代，Krylov解算器使用包括先前近似解的可用信息來獲得更好的新解。Krylov解算器繼續迭代，增量地最小化殘差，直到超過預設時間限制為止或直到殘差低于預定義值（即可接收殘差）為止。為針對新右端向量求解，Krylov迭代解算器完全重新開始該過程。注意，Krylov迭代解算器在針對新右端向量求解之前構建新Krylov子空間的新標準正交基。以該方式針對每個右端向量求解的一個限制是構建相關聯Krylov子空間的基典型地非常耗時。因此，當應用要求針對許多不同右端向量求解線性方程組時，將每個右端向量作為單獨問題對待可能超過應用的時間約束。

在求解包括與多個相關右端向量相耦合的相同大型矩陣A的線性方程組的另一個方法中，迭代解算器針對每個后續右端向量來變換初始Krylov子空間。在該方法中，迭代解算器構造初始標準正交基和相應Krylov子空間以針對第一右端向量求解。隨后，為了針對新右端向量求解，迭代解算器變換標準正交基和Krylov子空間。解算器然后使用經變換的標準正交基和Krylov子空間以針對新右端向量求解出近似x。類似地，針對每個新右端向量，迭代解算器實施變換并且然后進行迭代以針對新右端向量近似地求解。當右端向量緊密相關時，使用變換來代替創建全新Krylov子空間會減少達到可接受的精度水平所要求的時間。然而，實施變換仍然非常耗時。并且，盡管在執行時間上有所減少，在許多應用中該方法仍然超過可用時間。

如前所述，本領域中所需要的是用于求解某些類的、具有多個右端的線性方程組的更高效的技術。

發明內容

本發明的一個實施例闡述用于求解具有多個右端向量的線性方程組的方法。方法包括標識包括常數矩陣、要求解的變量、以及第一右端向量的第一線性方程組；基于Krylov子空間生成第一線性方程組的第一近似解；計算與第一右端向量有關的第一數據集；標識包括常數矩陣、要求解的變量、以及第二右端向量的第二線性方程組；基于第一數據集擴展Krylov子空間；以及基于Krylov子空間生成第二線性方程組的第二近似解。

本發明的其他實施例包括但不限于計算機可讀存儲介質以及系統，該計算機可讀存儲介質包括當被處理單元所執行時致使處理單元實現本文所描述的技術的各方面的指令，該系統包括配置為實現本文所描述的技術的各方面的不同元件。

通過實現所公開的技術，解算器程序可杠桿調整源自線性方程組的先前右端向量的信息以減少針對后續右端向量求解線性方程組所要求的時間。具體來講，通過針對每個新右端向量持續擴展Krylov子空間的標準正交基，解算器可比現有技術更高效地針對相關右端向量求解線性方程組。因此，某些軟件應用的整體性能可得到改進。

附圖說明