通过krylov子空间扩展求解具有多个右端的线性方程组的技术的制作方法.docx

通过krylov子空间扩展求解具有多个右端的线性方程组的技术的制作方法通过krylov子空间扩展求解具有多个右端的线性方程组的技术的制作方法一个实施例阐述用于求解包括与多个右端向量相耦合的相同矩阵A的线性方程组的方法针对每个新右端向量，解算器基于与先前右端向量相关联的Krylov子空间和数据来扩展现有的Krylov子空间解算器然后针对新右端向量使用经扩展的Krylov子空间以近似求解线性方程组通过针对每个新右端向量扩展Krylov子空间，解算器持续地杠杆调整来自在先右端向量的信息有利地，扩展Krylov子空间在计算上典型地快于现有技术，诸如创建新Krylov子空间或变换现有的Krylov子空间因此，通过实现所公开的技术，超过与包括求解某些类的线性方程组的算法相关联的时间约束的可能性可以减少专利说明】通过KRYLOV子空间扩展求解具有多个右端的线性方程组的技术[0001]相关串请的交叉引用[0002]本申请要求于2012年7月17日提交的、序列号为61/672，487的美国临时专利申请的优先权，在此通过援弓I的方式对其加以合并技术领域】[0003]本发明总地涉及通用计算，并且，更具体地，涉及用于通过克雷洛夫(Krylov)子空间扩展求解具有多个右端(right hand side)的线性方程组的技术。

背景技术】[0004]线性方程组出现在诸如化学、结构分析、物理、数学等范围广泛的领域内的科学计算的许多应用中并且求解这种线性方程组是使用在这些领域中的许多算法的重要部分，诸如化学处理仿真算法众所周知的是，线性方程组可以以矩阵形式表示为Ax=RHS通常，包括性方程组中的元素基于问题的类型而展现出相似性具体来讲，许多实际问题导致包括大型稀疏A矩阵的线性方程组注意，在包括N行的稀疏矩阵中，非零系数的数目是(以大写O标记)O (N)而不是O (N2)进一步地，一些包括相同大型稀疏A矩阵的线性方程组用来求解具有许多不同但相关的右端向量(RHS)的方程组然而，对于大型矩阵A，确定针对甚至一个右端向量的精确解X可能也要求太多存储器和太多时间才能发挥作用因此，使用迭代技术来生成近似解[0005]在求解包括与多个相关右端向量相耦合的相同大型矩阵A的线性方程组的一个方法中，每个右端向量被作为独立问题对待例如，Krylov迭代解算器可用来针对每个RHS分别查找近似解XKrylov迭代解算器典型地生成近似解的初始猜测并构建由迭代解算器根据初始残差(即RHS-Αχ)所创建的Krylov子空间的标准正交基随后，Krylov迭代解算器通过最小化残差而生成逐次近似解。

针对每次迭代，Krylov解算器使用包括先前近似解的可用信息来获得更好的新解Krylov解算器继续迭代，增量地最小化残差，直到超过预设时间限制为止或直到残差低于预定义值(即可接收残差)为止为针对新右端向量求解，Krylov迭代解算器完全重新开始该过程注意,Krylov迭代解算器在针对新右端向量求解之前构建新Krylov子空间的新标准正交基以该方式针对每个右端向量求解的一个限制是构建相关联Krylov子空间的基典型地非常耗时因此，当应用要求针对许多不同右端向量求解线性方程组时，将每个右端向量作为单独问题对待可能超过应用的时间约束[0006]在求解包括与多个相关右端向量相耦合的相同大型矩阵A的线性方程组的另一个方法中，迭代解算器针对每个后续右端向量来变换初始Krylov子空间在该方法中，迭代解算器构造初始标准正交基和相应Krylov子空间以针对第一右端向量求解随后，为了针对新右端向量求解，迭代解算器变换标准正交基和Krylov子空间解算器然后使用经变换的标准正交基和Krylov子空间以针对新右端向量求解出近似X类似地，针对每个新右端向量，迭代解算器实施变换并且然后进行迭代以针对新右端向量近似地求解。

当右端向量紧密相关时，使用变换来代替创建全新Krylov子空间会减少达到可接受的精度水平所要求的时间然而，实施变换仍然非常耗时并且，尽管在执行时间上有所减少，在许多应用中该方法仍然超过可用时间[0007]如前所述，本领域中所需要的是用于求解某些类的、具有多个右端的线性方程组的更高效的技术发明内容】[0008]本发明的一个实施例阐述用于求解具有多个右端向量的线性方程组的方法方法包括标识包括常数矩阵、要求解的变量、以及第一右端向量的第一线性方程组；基于Krylov子空间生成第一线性方程组的第一近似解；计算与第一右端向量有关的第一数据集；标识包括常数矩阵、要求解的变量、以及第二右端向量的第二线性方程组；基于第一数据集扩展Krylov子空间；以及基于Krylov子空间生成第二线性方程组的第二近似解[0009]本发明的其他实施例包括但不限于计算机可读存储介质以及系统，该计算机可读存储介质包括当被处理单元所执行时致使处理单元实现本文所描述的技术的各方面的指令，该系统包括配置为实现本文所描述的技术的各方面的不同元件[0010]通过实现所公开的技术，解算器程序可杠杆调整源自线性方程组的先前右端向量的信息以减少针对后续右端向量求解线性方程组所要求的时间。

具体来讲，通过针对每个新右端向量持续扩展Krylov子空间的标准正交基，解算器可比现有技术更高效地针对相关右端向量求解线性方程组因此，某些软件应用的整体性能可得到改进专利附图】【附图说明】[0011]因此，可以详细地理解本发明的上述特征，并且可以参考实施例得到对如上面所简要概括的本发明更具体的描述，其中一些实施例在附图中示出然而，应当注意的是，附图仅示出了本发明的典型实施例，并且因此不应被认为是对其范围的限制，本发明可以许可其他等效的实施例[0012]图1是示出了配置为实现本发明的一个或多个方面的计算机系统的框图；[0013]图2是根据本发明的一个实施例的、示出图1的解算器和构造器的示意图；[0014]图3是根据本发明的一个实施例的、示出解算器执行次序和构造器执行次序的示意图；[0015]图4是根据本发明的一个实施例的、用于针对不同右端向量来求解线性方程组的方法步骤的流程图；以及[0016]图5是根据本发明的一个实施例的、用于基于不同右端向量来扩展Krylov子空间的标准正交基的方法步骤的流程图具体实施方式】[0017]在下面的描述中，将阐述大量的具体细节以提供对本发明更透彻的理解然而，本领域的技术人员应该清楚，本发明可以在没有一个或多个这些具体细节的情况下得以实践。

[0018]图1是示出了配置为实现本发明的一个或多个方面的计算机系统100的框图如所示，计算机系统100包括但不限于，经由可以包括存储器桥105的互连路径通信的中央处理单元(CPU) 102和系统存储器104存储器桥105可以是例如北桥芯片，经由总线或其他通信路径106 (例如超传输(HyperTransport)链路)连接到I/O (输入/输出)桥107I/O桥107，其可以是例如南桥芯片，从一个或多个用户输入设备108 (例如键盘、鼠标)接收用户输入并且经由通信路径106和存储器桥105将该输入转发到CPU102并行处理子系统112经由总线或第二通信路径113 (例如外围部件互连(PCI) Express、加速图形端口或超传输链路)耦连到存储器桥105 ;在一个实施例中，并行处理子系统112是将像素传递到显示设备110 (例如常规的基于阴极射线管或液晶显示器的监视器)的图形子系统系统盘114也连接到I/O桥107交换器116提供I/O桥107与诸如网络适配器118以及各种插卡120和121的其他部件之间的连接其他部件(未明确示出)，包括通用串行总线(USB)或其他端口连接、压缩光盘(⑶)驱动器、数字视频光盘(DVD)驱动器、胶片录制设备及类似部件，也可以连接到I/O桥107。

图1所示的包括具体命名的通信路径106和113的各种通信路径可以使用任何适合的协议实现，诸如PCI Express,AGP (加速图形端口)、超传输或者任何其他总线或点到点通信协议，并且如本领域已知的，不同设备间的连接可使用不同协议[0019]如所示，并行处理子系统112耦连到本地并行处理(PP)存储器124可使用一个或多个集成电路设备或以任何其他技术上可行的方式来实现并行处理子系统112和并行处理存储器124，该一个或多个集成电路设备诸如可编程处理器、专用集成电路(ASIC)、或存储器设备如所示，并行处理子系统112经由连接到存储器桥105 (或在可替代实施例中直接连接到CPU102)的通信路径113与计算机系统100的其余部分通信并行处理子系统112到计算机系统100的其余部分的连接也可以改变在一些实施例中，并行处理子系统112实现为可插入计算机系统100的扩展槽中的插卡在其他实施例中，并行处理子系统112可集成在具有诸如存储器桥105或I/O桥107的总线桥的单个芯片上在又一个实施例中，并行处理子系统112的一些或所有元件可集成在具有CPU102的单个芯片上在一个实施例中，通信路径113是PCI Express链路。

还可使用其他通信路径[0020]在一个实施例中，并行处理子系统112包含经优化用于图形和视频处理的电路，包括例如视频输出电路，并且构成图形处理单元(GPU)在另一个实施例中，并行处理子系统112包含经优化用于通用处理的电路，与此同时保留底层(underlying)的计算架构，本文将更详细地进行描述在又一个实施例中，可以将并行处理子系统112与一个或多个其他系统元件集成在单个子系统中，诸如结合存储器桥105、CPU102以及I/O桥107以形成片上系统(SoC)[0021]并行处理子系统112可装备有任何数量的并行处理存储器124并可以以任何组合方式使用并行处理存储器124和系统存储器104并行处理子系统112可从系统存储器104和/或本地并行处理存储器124转移数据到内部(片上)存储器、处理数据以及将结果数据回写到系统存储器104和/或本地并行处理存储器204，其中这种数据可由包括CPU102或另一个并行处理子系统112的其他系统部件访问[0022]在操作中，CPU102是计算机系统100的主处理器，控制和协调包括并行处理子系统112的其他系统部件的操作有利地，并行处理子系统112可相对于CPU102的操作异步地执行命令。

如所示，系统存储器104包括在CPU102上执行的构造器109并且并行处理存储器124包括在并行处理子系统112上执行的解算器129构造器109和解算器129异步地合作以求解具有多个右端的线性方程组通过共同工作以高效地利用CPU102和并行处理子系统112这二者，构造器109和解算器129对求解线性方程组所要求的时间进行优化在可替代实施例中，构造器109和解算器129可以任何组合方式在CPU102和并行处理子系统112上执行进一步地，构造器109和解算器129可组合成单个程序或分解成附加程序[0023]应该理解，本文所示系统是示例性的，并且变化和修改都是可能的连接拓扑，包括桥的数目和布置、CPU102的数目以及并行处理子系统112的数目，可根据需要修改例如，在一些实施例中，系统存储器104直接连接到CPU102而不是通过桥，并且其他设备经由存储器桥105和CPU102与系统存储器104通信在其他替代性拓扑中，并行处理子系统112连接到I/O桥107或直接连接到CPU102，而不是连接到存储器桥105而在其他实施例中，I/O桥107和存储器桥105可能被集成到单个芯片上而不是作为一个或多个分立设备存在。

大型实施例可以包括两个或两个以上的CPU102以及两个或两个以上的并行处理子系统112本文所示的特定部件是可选的；例如，任何数目的插卡或外围设备都可能得到支持在一些实施例中，交换器116被去掉，网络适。