自适应迭代求解器的制作方法
专利名称：自适应迭代求解器的制作方法
技术领域：
本发明一般涉及求解线性方程系统的迭代求解器，且更具体地涉及自适应迭代求解器，其可操作用于调整/适应(adapt)存在奇点时的性能。
背景技术：
已知有各种技术用于求解线性方程系统。通常会在给定真实世界系统的各种基于计算机的三维(“3D”)模拟或建模中碰到线性方程系统(并需要求解)。例如，这样的基于计算机的3D建模可用于将这样的真实世界系统建模为机械和/或电子系统(如可用于汽车、飞机、轮船、潜水艇、宇宙飞船等)，建模人体(如人体全部或部分建模，如重要器官等)、天气形势，地下碳氢化合物储层(如气田或油田)以及各种其他要建模的真实世界系统。通过这样的建模，可以分析和/或预测被建模的系统的将来潜在性能。例如，呈现给建模系统的某些变化的条件对系统未来性能的影响可通过与基于计算机的的模型的交互以及对这种模型的分析进行评估。作为例子，多孔介质中流体流量/流动(fluid flow)的建模是石油工业的焦点。 不同的基于计算机的模型用于石油工业的不同领域，但大多包括以偏微分方程(PDE’ s)系统描述模型。一般地，这种建模通常要求针对给定网格在空间和时间上离散PDE’ s，并针对每个时间步骤执行计算直到达到规定的时间。在每个时间步骤中，离散方程被求解。通常离散方程是非线性的，并且求解过程是迭代的。非线性迭代方法的每个步骤通常包括非线性方程系统的线性化(如，雅可比(Jacobian)构造)、求解该线性系统和属性计算，其用于计算下一雅可比构造。图1示出一般工作流，其通常用于地下碳氢化合物储层中流体流量对时间的基于计算机的模拟(或建模)。内循环101是求解非线性系统的迭代方法。每次通过内循环101 通常包括非线性方程系统11的线性化(如，雅可比构造)、求解线性系统12和属性计算13， 其用于计算下一雅可比构造(当循环到方框11时)。外循环102是时步(time step)循环。如图所示，对于每个时步循环，边界条件可以在方框10中定义，并且然后在执行完内循环101后，可以在方框14中输出针对时步计算的时步结果(如，结果可存储到数据存储介质和/或提供给软件应用程序以生成表示针对相应时间步建模的地下碳氢化合物储层中流体流量的显示)。如上所述，除了地下碳氢化合物储层中流体流量建模外，真实世界系统的基于计算机的3D建模可以类似方式执行，即可采用迭代方法求解线性方程系统(如图1 中方框12所示)。线性方程系统的求解是计算量非常大的任务，因此需要有效算法。有两类线性求解器1)直接法和幻迭代法。直接法通常依靠有效形式的(Russian消元法来分解线性系统矩阵。该解是通过执行后向求解(backward solve)，然后执行前向求解(forward solve) 获得的。分解因子的计算成本和存储成本会很高，因为必须计算和存储所有新的填充项。计算效率很大程度上依赖于矩阵大小和带宽。三维模型导致矩阵非常大、稀疏，并具有相当的带宽。该大小和大带宽导致非常大量的必须计算和存储的新填充项。因此，无论是从计算成本还是存储成本的角度，直接法用于实际3D建模的成本通常是无法想象的。迭代法提供求解大稀疏线性系统的另一种方法。当采用迭代法时，解在每次迭代中被更新直到达到收敛。每次迭代仅要求以稀疏矩阵进行运算且通常与未知数的数目成比例。不幸的是，对于大的线性方程系统，标准迭代方法收敛非常慢。可以通过使用预处理矩阵的新矩阵取代原矩阵显著改善这种情形。例如，原问题Ax = b可以由具有相同解的修正的问题B4Ax = Β_、取代，其中B是预处理矩阵(或简称为“预处理器(preconditioner) ”)。 具有修正的矩阵的每次迭代以矩阵B求解问题，Bu = r。针对椭圆和抛物线问题开发高效预处理器已经取得了相当进展。主要进展是开发了计算成本低(如运算数目与未知数的数目成比例)且有效的(如具有不随问题大小变化的少量迭代)的预处理器。这种预处理器的最佳已知示例是多重网格(MultiGrid)和域分解(Domain Decomposition)算法。这样的预处理器在本文中可称为“最优预处理器”，在这种预处理器中收敛所需的迭代数目不随问题(或模型)的大小增大而增加。最优预处理器的第一个已知示例是多重网格，其通过作用于不同网格上误差的不同成分减少误差。最优预处理器的第二已知示例是域分解。域分解算法通过求解部分原始域中相同或类似的问题来构造解。非迭代域分解法在域的每部分(所谓的子域，图2所示例子的Q1 和Ω2)中求解类似问题以及公共接口 Y上的不同问题。迭代域分解法求解扩展域上的问题，扩展域由原始域和交迭带(strip)形成，如图3所示。全局问题的解由子域问题的解组成。可以以加法或乘法方式应用域分解算法。加法域分解算法同时计算其解的各部分。乘法方法中的每个步骤都包括几个子步骤。在第一子步骤，一组子域首先计算解。在下一子步骤，下一组子域使用第一组的结果计算其解，如此类推。因此，如果模型尺寸增长，则如多重网格和域分解的最优预处理器已知是最优的。 例如，假定模型以100，000个单元开始，但在随后的某个时间使用具有上百万个单元的更大模型。一般地，可采用诸如多重网格或域分解的最优预处理器，并且对于所有的三种模型，其可以在固定数目的迭代(例如10次迭代)中收敛于解。其他已知预处理器随着模型尺寸增长要求更多次迭代以达到收敛，而最优预处理器将通常在固定次数的迭代中收敛， 与模型尺寸是否增长无关。不幸的是，如果PDE’ s的原始系统或线性系统具有某些特殊特征，那么即使最优预处理器的性能也会显著恶化。例如，如果PDE’s的系统的解在域的某部分极其大，或没有导数，则在求解线性系统时会产生困难。解的这类行为通常称为“奇点”。当建模地下碳氢化合物储层中的流体流量时，各种特殊影响或特征可能存在于被建模的地下区域中，如井、断层或其他地质特征。被建模的真实世界系统中出现的这类特殊影响或特征可能产生奇点。一般地，“奇点”是指线性系统或物理模型中的任何特征，其削弱求解器使用的迭代方法(如预处理器)的收敛性。例如，奇点的存在可导致最优预处理器不能在预期的迭代次数内收敛。例如，如上所述，最优预处理器通常在固定的迭代次数内收敛，无论模型尺寸是否增长。然而，如果在模型中碰到奇点，则传统最优预处理器，如多重网格和域分解将不能在模型的固定迭代次数内收敛。通常，奇点是由地下碳氢化合物储层的建模中出现的井或不连续系数及其特殊行为引起的，特殊行为如被建模的地下岩石属性。井通常被建模为点或线源，并且在具有非常小尺寸的区域中(数学抽象中的零)，某些有限量的流体或者注入到地下，或者由井产生 (即从地下抽取)。这导致解及其导数极其大(数学意义上的无穷大)。解的这种行为频繁地导致预处理的迭代方法收敛性降低。许多不同井模型用于石油工业。其中大多数都不会写为椭圆或抛物线方程。因此，上述多重网格和域分解对于这类线性系统不是很有效。此外，某些地质特征，如断层、裂缝(fracture)或尖灭(pinch-out)也可能在预处理的迭代方法中引起问题。也就是，某些地质特征也可能引起奇点，该奇点降低 (deteriorate)预处理方法的收敛性。某些地质特征可能引起问题的一个原因是这类地质特征中的流体流动可能与周围的多孔介质中的流动显著不同。如上面所考虑的，已经做出了许多努力来为线性系统开发有效的预处理器。作为一个例子，使用不完全LU分解的预处理器不受井的存在、断层或裂缝的影响，但对于非常大的线性系统也不是有效的。作为另一个例子，有人提出消除某些最优预处理器中奇点的技术，如在域分解和多重网格中。例如，已经尝试使用某些域分解法消除奇点，但收敛性取决于交迭且被降低，参看 H. Cao，H. A. Tchel印i，J. Wallis 和 H. Yardumian 的 “Parallel Scalable Unstructured CPR-Type Linear Solver for Reservoir Simulation，，， SPE Annual Conference and Exhibition，2005 年 10 月，德克萨斯的达拉斯。多重网格法更成功，参看 K. Stuben, T. Clees, H. Klie, B. Lu 和 M. F. Wheeler 的 Algebraic multigrid methods for the efficient solution of fully implicit formulations in reservoir simulation, SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨斯休斯顿；Τ· Clees 禾口 L. Ganzer 的 An efficient multigrid solver strategy for adaptive implicit methods in oil reservoir simulation,SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨斯休斯顿；以及 H. Klie,M. F. Wheeler, K. Stuben 和 T. Clees 的 Deflation AMG solvers for highly ill-conditioned reservoir simulation problems, SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨其jf休其jf顿。然而，上面提出的消除最优预处理器中奇点的技术无法保持最优预处理器的性能。例如，假定预期最优预处理器在例如10次迭代内收敛于解，无论模型的大小(假定没有碰到奇点)；则模型中特殊特征的存在可能产生奇点，其导致最优预处理器要实现收敛需要100次迭代。已经提出的用于消除奇点的传统技术可改善最优预处理器的性能，以便其可在例如25次迭代内收敛，但不能实现其预期的性能(在该例子中为10次迭代)，如果模型中不存在引起奇点的特殊特征，则将实现该预期性能。进一步，上面提出的消除奇点的技术依靠预先识别奇点的存在，然后遵从消除任何这类预先识别的奇点的预定方案(regiment)。也就是说，求解器被预先配置以消除预先识别的奇点。因此，要求用户(如工程师、分析人员等)预先识别模型中被认为可能产生奇点的特殊特征，且用户预先配置求解器以消除预先识别的奇点。求解器本身不用于识别奇点，也不涉及判断是否消除预先识别的奇点。而是所有这类奇点的识别和关于如何预先配置求解器以消除识别的奇点的判断都是在求解器外进行的(如，通过工程师、分析人员或其他用户完成)。
发明内容
本发明公开一种采用自适应迭代求解器的系统和方法。也就是说，提供了一种迭代求解器，其采用自适应过程提取奇点以求解线性方程系统。因此，根据某些实施例，提供了自适应迭代求解器，其可操作用于确定如何在存在一个或多于一个奇点的情况下调整其性能。因此，根据本发明的某些实施例，提供的自适应迭代求解器用于求解线性方程系统，如通常用于基于计算机的3D建模。在某些实施例中，自适应迭代求解器可识别可能的奇点，并且之后分析其性能以调整对可能奇点的处理，从而提供所需的性能(即，用于实现至解的收敛性)。因此，并不是被预先配置为提供对某些预先识别的奇点的某种处理(如消除)，在某些实施例中，迭代求解器基于其计算性能调整其对奇点的处理。例如，自适应迭代求解器的实施例可尝试第一奇点处理(如采用第一预处理器提取某些奇点)，并基于其计算性能的分析(如收敛所要求的迭代次数和/或每次迭代的计算成本等)，自适应迭代求解器可调整其奇点处理(如通过将不同预处理器用于提取奇点)， 从而实现以提供所需性能的方式求解线性方程系统的技术。在调整其性能过程中，在某些实施例中，自适应迭代求解器可提取比所有预先识别的奇点较少的奇点和/或可识别要提取的额外奇点。例如，自适应迭代求解器可推导出存在于被建模的真实世界系统中且最初被认为可能引起奇点的某些特殊影响或特征实际上不产生为改善性能而应当被提取的奇点。作为另一个例子，在其处理的过程中，自适应迭代求解器可能检测进一步的奇点(这些奇点并不被预先识别为可能的奇点)，其应被提取以改善求解器的性能。在某些实施例中，自适应迭代求解器调整迭代求解过程中使用的预处理器，从而以提供所需性能水平的方式处理奇点。例如，在某些实施例中，自适应迭代求解器构造预处理器以提取某些奇点，且其处理自适应迭代求解器的过程可修正/调整其构造的预处理器 (例如，以提取可能被发现的额外奇点和/或不提取某些预先识别的可能奇点)以求解线性方程系统。在某些实施例中，自适应迭代求解器是最优求解器，其调整其性能，从而以维持模型中不存在奇点时遇到的迭代次数的方式处理奇点。在某些实施例中，自适应迭代求解器可选择以导致迭代次数增加超过模型中不存在奇点时碰到的迭代次数的方式调整其性能。 然而，增加迭代次数的这类自适应可以由自适应迭代求解器智能地执行(相对于由求解器操作的预先配置产生)。例如，自适应迭代求解器可以确定在某些实例中，迭代次数增加相对于具有每次计算成本极其高昂的较少迭代更为理想。在某些实施例中，在分析其性能时，自适应迭代求解器考虑迭代的次数和每次迭代的计算成本。例如，在某些情形中，特定预处理器可用于以显著减少实现收敛所需迭代次数的方式处理奇点，但是处理每次迭代的计算成本(如要求的CPU时间量和/或要求的内存)可能很高。因此，在某些情形中，自适应求解器可得出这样的结论，每次迭代计算成本不是很高的迭代次数的少量增加是适当的解决方案。给定奇点的相对重要性可能基于各种考虑的一个或多于一个方面，如由奇点导致的迭代求解器性能的相应退化量(如果奇点没有被预处理器提取)。有不同的可能方式对奇点排序。一种排序方式是给不同的奇点分配不同的权重。在某些实施例中，奇点越重要， 分配的权重越大。自适应迭代求解器可至少部分基于分配给奇点的相对权重来确定其对奇点的可能的处理(例如，确定预处理器用于提取可能奇点中选择的奇点)。在某些实施例中，分配的权重可以由自适应迭代求解器在其处理过程中更新(例如，基于在存在奇点时自适应迭代求解器对其性能的评估等)。在很多实例中，忽略某些低权重的可能奇点不会不利地影响迭代求解器的收敛，因为迭代方法考虑这些奇点。下面进一步说明可由自适应迭代求解器采用的用于识别可能奇点并基于其计算性能自适应其对这些可能奇点的处理的各种示例性技术。在某些实施例中，自适应迭代求解器采用两步法构造预处理器。在这样的实施例中，自适应迭代求解器首先尝试从可用于被识别的奇点的近似构造预处理器。对于每个这种近似，自适应迭代求解器可以评估其性能，并确定预处理器的性能不可接受的那些近似(如，要么收敛太慢，每次迭代具有不理想的计算成本，等)。对于近似不可用或性能被确定为不可接受的那些奇点，自适应迭代求解器采用可替换的预处理器构造技术，如基于将解表示为奇点部分及其补元(complement) 的和的技术。本文将进一步说明可以在某些实施例中采用的示例性预处理器构造算法。前面已经相当宽泛地概括了本发明的特征和技术优点，从而可以更好地理解本发明以下的详细说明。将在下文描述本发明的额外特征和优点，其形成本发明权利要求的主题。本领域技术人员应该理解公开的概念和具体实施例易于用作修改或设计执行本发明相同目的的其他结构的基础。本领域技术人员还应该认识到这样的等效构造不偏离权利要求中限定的本发明的精神和范围。根据以下说明并结合附图可以更好地理解被认为是本发明特征的新颖特征(包括运算的组织和方法)以及本发明的进一步的目的和优点。然而应当清楚地理解，提供的每附附图目的在于例示和说明，而非意在限制本发明。
为了更完整地理解本发明，可参考结合附图的以下说明，其中图1示出通常用于地下碳氢化合物储层中流体流量对时间的基于计算机的模拟 (或建模)的一般工作流；图2示出可以在非交迭域分解方法中求解的子域；图3示出可以在交迭域分解方法中求解的交迭子域；图4示出根据本发明一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图5示出根据本发明另一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图6示出根据本发明另一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图7示出根据本发明一个实施例构造预处理器的自适应迭代求解器的示例性操作流；图8示出根据一个实施例构造用于奇点(一个或多个)的预处理器的自适应迭代求解器的示例性操作流，对于所述奇点近似不可用或被确定为不可接受；以及
图9示出可实施根据本发明某些实施例的自适应迭代求解器的所有或部分的示例性计算机系统。
具体实施例方式参考图4，其示出根据本发明一个实施例的示例性基于计算机的系统400的方框图。如图所示，系统400包括基于处理器的计算机401，如个人计算机(PC)、膝上型计算机、 服务器计算机、工作站计算机、多处理器计算机、计算机集群等。此外，自适应迭代求解器 (如软件应用程序)402在这类计算机401上执行。计算机401可以是能够执行自适应迭代求解器402的任何计算设备，如本文的进一步说明。尽管在图4中自适应迭代求解器402 示为在计算机401上执行，以易于图示，但是应该认识到这类求解器402可以在本地计算机 401或经通信网络与计算机401通信连接的远程计算机(如，服务器计算机上)上驻存和/ 或执行，通信网络如局域网(LAN)、因特网或其他广域网(WAN)等。而且，应该理解计算机 401可包括多个集群的或分布的计算设备(如服务器)，如本领域所熟知的，自适应迭代求解器402可跨这些计算设备存储和/或执行。如同许多传统的基于计算机的迭代求解器，自适应迭代求解器402包括存储到计算机可读介质的计算机可执行软件代码，这些代码可以由计算机401的处理器读取，并且由这类处理器执行时会引起计算机401执行下文进一步说明的这种自适应迭代求解器402 的各种操作。自适应迭代求解器402可操作为使用迭代过程来求解线性方程系统。如上所述，这样的迭代求解器通常用于3D基于计算机的建模。例如，自适应迭代求解器402可用于(图1的)传统工作流的运算方框12，以进行地下碳氢化合物储层中流体流的3D基于计算机的建模。在图4所示的例子中，模型406(例如，包含有关要建模的真实世界系统的各种信息，如关于地下碳氢化合物储层的信息，针对该储层，将建模流体流量随时间的变化) 存储在通信耦合到计算机401的数据存储装置405中。数据存储装置405可包括硬盘、光盘、磁盘和/或其他可操作用于存储数据的计算机可读数据存储介质。如同用于3D基于计算机的建模的许多传统迭代求解器，自适应迭代求解器402可操作用于接收模型信息406，并执行用于求解线性方程系统的迭代方法，所述线性方程系统用于生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量随时间变化的模型。根据本发明的实施例，自适应迭代求解器402可操作用于分析其计算性能以确定是否自适应其对模型406中可能奇点(singularity)的处理，如方框403所示。如方框404 所示，当确定应当自适应其对模型中可能奇点的处理时，自适应迭代求解器402自适应其对可能奇点的处理以提高其在求解用于3D基于计算机的建模的线性方程系统的性能。例如，自适应迭代求解器402可适于使用预处理器(多个)来提取可能奇点的多个不同奇点以获得所需的计算性能。因此，无需局限于对预先识别的奇点(一个或多个)执行某种预先配置的消除，实施例自适应迭代求解器402可操作用于自适应其奇点处理。作为一个例子，自适应迭代求解器402可以是预计在给定次数的迭代即10次迭代内收敛的最优求解器，其中不考虑模型 406的大小。然而，由于遇到模型406中的某些奇点，自适应迭代求解器402的性能可能会衰减，导致要求10次以上迭代才能收敛，除非自适应迭代求解器402调整其对这类奇点的处理。在某些实施例中，自适应迭代求解器402调整其对奇点的处理(例如，通过构造预处理器来提取识别的可能奇点中选择的奇点)，以实现在要求的10次迭代内收敛的处理技术。如上所述，在某些实施例中，如果认为每次迭代的计算成本在不同情况下太昂贵，则自适应迭代求解器402可以智能选择使用增加收敛的迭代次数(如在上述示例中超过10次) 的处理技术。下面进一步讨论不同示例性方式，其中自适应迭代求解器402的实施例可评估其性能并调整其对奇点的处理。参考图5，其示出根据本发明实施例的另一个示例性基于计算机的系统500的框图。类似于图4中的示例性系统400，系统500包括基于处理器的计算机401，其上执行自适应迭代求解器402的实施例，在该例子中示为自适应迭代求解器402A。而且，如图4的示例，模型406 (如包含关于要建模的真实世界系统的各种信息，如地下碳氢化合物储层的信息，为此信息将建模流体流量随时间的变化)存储在通信连接到计算机401的数据存储装置405中。如上所述，自适应迭代求解器402A可操作用于接收模型信息406并执行求解线性方程系统的迭代方法以生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量对时间的模型，其可用于图1的示例性流中方框12中。在图5的示例性实施例中，方框501中，自适应迭代求解器402A识别可能的奇点。 可以以各种方式识别模型中可能的奇点。例如，可以基于有关被建模的真实世界的已知信息预先识别(如由用户，如工程师、分析人员等识别)某些可能的奇点，并且模型406的预先被识别的可能奇点可以分类(存储)到存储在数据存储装置405中的目录(catalog) 505 中(如任何适当的计算机可读数据结构，如文件、数据库等)。因此，已知存在于被建模的真实世界系统中并被怀疑将产生奇点的各种特征可以在目录505中被预先识别。例如，在地下碳氢化合物储层中流体流量的建模中，可能引起模型中的奇点并且可以在要建模的目标区域中被预先识别的公知特征可以包括某些地质特征(如断层、大裂缝、尖灭等等)和/或某些工程特征(如水平井、倾斜井和垂直井、连接的设施网络等)的存在。此外，在某些实施例中，自适应迭代求解器402A自身可以在处理模型的过程中发现某些可能的奇点。例如，在处理过程中，求解器402A可以通过其对被处理的方程(如矩阵)的分析来识别可能的奇点。例如，对于给定的建模过程，自适应迭代求解器402A可以将异常矩阵项或结构(如极大项、非对角占优矩阵、M矩阵中非对角正项等)辨认为存在于模型的相应部分的可能奇点。在某些实施例中，自适应迭代求解器402A保持列表506 (其可采用任何适当的计算机可读数据结构的形式，如文件、数据库等)，该列表存储在数据存储装置405内，其中这类列表506识别自适应迭代求解器402A要提取的当前奇点。可用于提取奇点的示例性技术在下面进一步讨论。在一个实施例中，当可能的奇点在方框501中被识别时，其被加入到要提取的当前奇点的列表506中。当然，如下面进一步的讨论，列表506是动态的并且可以由自适应迭代求解器402A修改，因为其确定如何最好地调整其对奇点的处理以提供所需水平的性能。如下面进一步的讨论，在某些实施例中，当前奇点的列表和/或预先识别的可能奇点的目录可包括分配给奇点的相应权重。在方框502中，自适应迭代求解器402A构造预处理器，其提取当前奇点(S卩，列表 506上被识别的奇点)。最初，列表506可包括在目录505中预先定义的所有可能的奇点。 如下面进一步讨论，在某些情形中，可以从当前列表506中去除一个或多于一个这类可能的奇点(因此，其不被抽取)和/或可以将自适应迭代求解器402A发现的(如通过分析正被处理的矩阵)一个或多于一个可能的奇点加入到当前列表506中。再次，可在方框502 中用于构造预处理器以提取所选奇点(即，当前列表506上的奇点)的示例性技术在下面进一步讨论。在某些实施例中，要包括在当前列表506中的奇点(由预处理器提取)和要从列表506中去除的奇点的确定可至少部分基于分配给奇点的相对权重。例如，如果分配有高权重的奇点没有被提取，则可以认为其对迭代求解器的性能有高退化作用，并且可以认为分配有低权重的奇点对迭代求解器的性能有较低退化作用；在此情形下，具有最高权重的奇点可以被选择为包含在当前列表506上由预处理器提取。在方框503中，自适应迭代求解器402A在迭代求解线性方程系统中使用构造的预处理器来确定3D基于计算机的模型的相应部分。可用于某些实施例并用于迭代求解线性方程系统的示例性预处理器在下面进一步说明。当然，本发明的实施例并不限于使用任何特定预处理器，某些实施例可以被实施为自适应任何各种不同预处理器的应用。在方框403中，自适应迭代求解器402A分析其性能以确定是否自适应模型中可能奇点的处理。虽然图5中为了图示的便利示为线性流，但应该理解各种操作不限于所示的顺序，且其中的某些方框可并行执行。例如，在某些实施例中，在方框503中处理构造的预处理器的同时，自适应迭代求解器402A可分析其性能以确定是否调整其对奇点的处理。当确定应当自适应处理可能的奇点时，在方框404中，自适应迭代求解器402A自适应其对可能奇点的处理。在某些情形下，这可能在方框503的迭代过程收敛于一个解之前中断其在方框503中的处理，以在方框404中自适应其对可能奇点的处理。在某些实施例中，作为方框403中的分析的一部分，方框504中自适应迭代求解器 402A权衡利用排除所选奇点(列表506上)的预处理器获得的迭代性能的增益和每次迭代中预处理器的计算成本。例如，在方框403中分析其性能时，自适应迭代求解器402A可同时考虑收敛的迭代次数和每次迭代的计算成本。例如，在某些情形中，可以以显著减小实现收敛的迭代次数的方式使用特定预处理器来处理当前奇点(列表506中)，但处理每次迭代的计算成本(如需要的CPU时间量和/或需要的内存)可能非常高。因此，在某些情形下， 在方框504中，自适应迭代求解器402A可得出这样的结论，如果每次迭代的计算成本不是如此高昂，那么迭代次数的少量增加是适当解。参考图6，其示出根据本发明实施例的另一个示例性基于计算机的系统600的方框图。类似于图4的示例性系统400和图5的系统500，系统600包括基于处理器的计算机 401，其上执行自适应迭代求解器402的一个实施例，在此示例中显示为自适应迭代求解器 402B。而且，和图5的例子一样，模型406(如包含关于要建模的真实世界系统的各种信息， 如关于地下碳氢化合物储层的信息，为获得此信息建模流体流量随时间的变化)、预先识别的可能奇点的目录505和当前要提取的奇点的列表506存储在与计算机401通信连接的数据存储装置405中。如上所述，自适应迭代求解器402B可操作用于接收模型信息406，并执行求解线性方程系统的迭代方法以生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量对时间的模型，其可用于图1的示例性流程的方框12中。在图6的示例性实施例中，自适应迭代求解器402B可用于工作流，如以上图1中所述。例如，自适应迭代求解器402B可用于时步循环601中，如图1中的示例性外部循环 102，其中下面讨论的各种操作可在时步循环601中执行。在方框602中，检查物理问题(例如，模型406和/或相应的真实世界系统)和/或线性系统以识别当前和可能的新奇点。可以以各种方式识别模型中可能的奇点。例如， 某些可能的奇点可基于已知的关于被建模的真实世界系统的信息被预先识别(如由用户识别，如工程师、分析人员等)，并且预先识别的模型406的可能奇点可分类(存储)到存储在数据存储装置405中的目录505中(如任何适当的计算机可读数据结构，如文件、数据库等)。也就是说，可执行某种预处理610以由预先识别的可能奇点初始构成目录505。因此，已知存在于被建模的真实世界系统中并且可能产生奇点的各种特征可能在目录505中被预先识别。例如，在建模地下碳氢化合物储层的流体流量的过程中，可能产生模型中的奇点并且可以在要建模的目标区域中被预先识别的共同特征可包括某些地质特征(如断层、 大裂缝、尖灭等)和/或某些工程特征(如水平井、倾斜井和垂直井、连接的设施网络等) 的存在。在此示例性实施例中，在时步循环601的每个时步中，检查线性系统以获得当前奇点和由于物理系统变化导致的可能新奇点，物理系统变化如井被打开和关闭、井从主要生产到排放水或气的切换和/或发生在正被建模的地下碳氢化合物储层内的其他变化。一开始，检查所有分类的可能奇点。也就是，自适应迭代求解器可评估目录505中分类的每个可能奇点以确定其是否为真正的奇点(即，它们的存在是否真正退化(degrade)求解器 402B采用的迭代方法的收敛性)，并且那些被确定为一定程度上退化迭代方法性能的真正奇点被加入到要去除的当前奇点的列表506。此外，在方框603中，自适应迭代求解器402B自身可基于对针对模型406处理的矩阵的检查发现某些可能奇点。例如，对于给定的建模过程，异常矩阵项或结构(如极大项、非对角占优的矩阵、M矩阵中非对角正项等)可以被自适应迭代求解器402B辨认为模型相应部分中存在的可能奇点。在某些实施例中，自适应迭代求解器402B保持列表506 (其形式可以是任何适当的计算机可读数据结构，如文件、数据库等)，其存储在数据存储装置405中，其中这种列表 506识别自适应迭代求解器402B要提取的当前奇点。最初，列表506可包括目录505中预先识别并在方框603中确定的所有可能的奇点。然而，要提取的当前奇点的列表506是动态的，且因此可通过自适应迭代求解器402B在处理模型406的过程中进行调整。在方框604中，自适应迭代求解器402B构造提取当前奇点的预处理器(即在列表 506上识别的那些奇点)。如下面进一步的讨论，在某些情形中，可以从当前列表506中去除一个或多于一个这种可能的奇点(以便它们不能被提取)，并且/或者可以将一个或多于一个自适应迭代求解器402B发现的可能奇点(如通过分析被处理的矩阵)加入到当前列表506中。再次，下面进一步详细讨论可在方框604中用于构造提取所选奇点(即，当前列表506上的奇点)的处理器的示例性技术。在方框605中，自适应迭代求解器402B在迭代求解线性方程系统中使用构造的预处理器以确定3D基于计算机的模型的相应部分。下面进一步说明可用于某些实施例的示例性预处理器，以及其在迭代求解线性方程系统中的使用。当然，本发明实施例并不限于使用任何特定预处理器，某些实施例可实施为自适应于各种不同预处理器中任何预处理器的应用。在方框606中，自适应迭代求解器402B分析预处理器的性能，且如果需要，调整预处理器从而改善求解器的计算性能。在方框607中，可更新当前奇点的列表506以反映要提取奇点中的任何变化，如方框606中确定的那样。虽然图6中为了便于图示而示为线性流，但是应该认识到各种操作不限于显示的顺序，并且某些方框可并行执行。例如，在某些实施例中，自适应迭代求解器402B在方框605中处理构造的预处理器的同时，可分析其性能(方框606)从而确定是否调整其对奇点的处理。当确定应自适应可能奇点的处理时，自适应迭代求解器402B通过更新要提取的当前奇点的列表506(在方框607中)自适应可能奇点的处理。在某些情形中，可以在方框605的迭代过程收敛到解之前中断方框605中的处理，以在方框607中自适应要提取的当前奇点的列表506，其中操作可返回到方框602以最终构造(在方框604中)另一个预处理器以提取修订的奇点的当前列表506。当在方框608中确定对于被处理的模型的当前时间间隔，自适应迭代求解器402B 已收敛到解时，在方框609中，操作可进入要处理的下一时间间隔，如图1的示例性工作流的外部循环102。并不是所有奇点总是以坏的方式影响线性系统。例如，如果建模的地下碳氢化合物储层的井关闭(shut in)，则对线性系统没有影响。在该示例性实施例中，自适应迭代求解器402B可通过针对小块模型并分析相应线性系统及其解来研究每个可能的奇点(物理限定的)。如果线性系统(如大条件数)或者是其解有某种异常行为，则奇点被选择以供提取(即，被加入到当前奇点的列表506中)。否则，可能的奇点不包括在当前时步的列表 506中(即，可从其中除去)。通常，仅检查模型406中是否有变化是足够的。例如，如果井正在生产，并且曾经常常引起线性系统的问题，则假定其将持续该行为。在一个实施例中，性能分析(如图4的方框403或图6的方框606)检查迭代求解器的行为以尝试改善自适应迭代求解器的迭代性能和/或CPU/Wall时钟性能。可通过加入忽略的奇点、发现新奇点和/或改善当前奇点的处理来改进迭代性能。在某些实施例中， 可以通过调整预处理器的操作改善CPU/Wall时钟性能。例如，如果迭代性能是好的，但预处理器计算成本高昂，则在某些实施例中，自适应迭代求解器可选择忽略某些奇点和/或放宽(relax)对某些奇点的处理。理想地，改善迭代性能应改善CPU/Wall时钟性能，但不总是这样。使预处理器非常昂贵，即“很好”，会导致少但非常昂贵的迭代。使用非常便宜但不高效的预处理器通常无法提供好的解。某些实施例用来实现折衷的方式是按重要性排序当前奇点并保持最重要的，即具有最高排序的奇点。一种可能的方式是为不同奇点提供权重，且权重越高，则排序越高。权重在模拟运行中更新，并且变化反应性能。忽略某些低级奇点通常不会不利地影响收敛，因为迭代方法会考虑这些奇点。有几种方法可用于分配权重给不同奇点。根据某些实施例可以采用的一种方法是基于奇点的类型分配静态权重。例如，垂直井可分配以权重1，倾斜井可分配以权重2，水平井可分配以权重3，等等。这些静态权重可基于之前运行(以某些静态工具处理)的结果分析和/或可基于某些理论假设的应用。根据某些实施例，可以使用的更复杂的方法是基于迭代求解器性能动态调整权重。例如，该方法在第一次运行中可以使用固定权重作为开始 (如第一次3D建模采用迭代求解器)，且在下一次运行时，可改变某些权重并且分析迭代求解器的相应性能。例如，该方法可以按如下权重分配求解线性方程系统一次，第一水平井权重为3，第二水平井权重为3。然后，可以以分配给第一水平井权重2和分配给第二水平井权重4求解线性方程系统。可比较第一和第二迭代方法的性能，并且该方法可基于确定的性能比较继续调整权重。例如，可以证明第一井不重要，且其可从当前奇点列表中去除。例如，通过采用仅考虑被分配最高权重的固定数目的奇点的方法，一旦该方法有效地降低其相对权重，则可从当前奇点列表中去除第一井。可使用各种不同算法提取奇点。不同的奇点可能要求不同的方法进行提取。可以使用的一个示例性算法考虑物理限定(bound)的奇点，如被物理限定的地下碳氢化合物储层中流体流量模型的部分中碰到的奇点。在一个实施例中，假定给定奇点中的流体行为和给定奇点周围的流体行为可以较为简单的模型近似，并且该较为简单的模型不会不利地影响线性系统。例如，复杂的井模型通常不利地影响预处理器的质量。简单的井模型表现得更好。如果复杂的井模型可以简单的井模型近似，则预期最终的预处理器会更好。有时，近似不能解决该问题，但“坏的”部分的维度显著减小。在一个实施例中，应用第二步，其涉及特定的小的排序更新过程。类似方法可用于地质奇点，如在被建模的地下碳氢化合物储层中碰到的裂缝。根据一个实施例，对于识别的物理限定的奇点，两个预处理器被考虑。最初，对于每个物理限定的奇点，选择子域，其包含该奇点及其周围的小的带。以下讨论在某些实施例中可用于构造用于这种奇点的预处理器的示例性的两步过程。也就是，在某些实施例中，下面说明的示例性两步方法用于构造预处理器(如图6的方框604)。首先，以适当的近似取代每个奇点(如，其可作为图6中方框604的部分执行)。 然后，构造全局预处理器(如其可作为图6中方框604的部分执行)，其中全局预处理器包括在奇点之外的原始问题和在奇点内确定的近似。在某些实施例中，可以通过全局预处理器和子域应用加法和乘法khwarz。可使用重叠或不重叠版。然后，评估给定奇点的近似的质量(如其可作为图6中方框606的部分执行)。例如，近似的质量可以使用包含该近似的本地块并检查线性系统进行评估，或者通过观察预处理器的收敛行为进行评估。也就是说，给定奇点可以被近似，且可对近似执行线性解。然后确定在使用近似时，收敛是否可接受。如果确定收敛不可接受，则以下讨论的替换的预处理器构造技术用于下一时步(如，在图6的示例性时步循环中的下一时间间隔609之后)。在该示例性实施例的可替换的预处理器构造技术中，当没有可用的好的近似或近似仍然不利地影响线性系统时，使用另一个预处理器。在一个实施例中，解被计算为两项的和。第一项是对“奇点空间”的正交投影，第二项是其补元。可针对“好的部分”使用任何预处理器，其包括前面步骤中的预处理器。给定奇点可视为包含在奇点空间中，其可包括可很好近似的某些特征/特性，并且也可以包括无法达到好的近似的某些其他特征/特性。根据某些实施例，奇点空间可分成能很好近似的部分(其可称为“好的”部分)和不能很好近似的部分(其可称为“坏的” 部分)。因此，在某些实施例中，自适应迭代求解器可操作用于从奇点空间提取“坏的”部分，从而得到可很好近似的好的剩余部分。给定奇点空间“X”可视为具有对应的维度(对应于描述奇点的子矩阵的大小)， 如维度“dim(X)”。求解器可首先尝试以具有减小维度的较为简单的模型近似/近似 (approximate)奇点，如在维度为“dim⑴”的空间“Y”中(其中dim(Y) < dim(X))0空间 “Y”是奇点空间“X”的一部分。可以保留没有良好近似的奇点的一部分。该部分在具有维度“dim(Z) ”的空间“Z”中，其中“dim(Z) = dim(X)-dim(Y) ”，即，在从奇点空间取出“Y”后留下的部分。在某些实施例中，奇点空间的空间“Y”中近似的部分被当作奇点空间的“好的”部分，可以用适当的预处理器对其进行处理，而奇点空间剩余的“Z”部分被称为奇点空间的“坏的”部分，可以以不同方式对其进行处理。因此，根据某些实施例，对于无法获得近似(如方框701中所确定的)或近似的质量被确定为不可接受(方框703中)的任何奇点， 自适应迭代求解器402尝试提取“坏的”部分。因此，当对于给定奇点无法获得适当近似时或者这种近似的质量不可接受时，在某些实施例中，求解器提取奇点的“坏的”部分，从而剩余的好的部分可通过可接受的近似来建模。作为例子，假定原始问题维度为1，000, 000，且存在维度100的奇点。进一步假定求解器尝试以具有维度如90的较为简单的模型近似该奇点。如果第一预处理器的性能被确定为可接受，则使用该预处理器。否则，如果第一预处理器的性能被确定为不可接受的， 则采用本文进一步讨论的第二步。因此，借助奇点近似，100个奇点模式中的一些奇点模式被抑制，例如90个奇点模式可能被近似抑制。10个剩余奇点模式称为仍需考虑的“坏的” 模式(或“坏的”部分)。不幸的是，我们不能明确知道哪些是“坏的”模式。在该例子中， “坏的”或奇点部分的维度为10，且“好的”部分的维度为1，000，000-10。进一步，在该例子中，去除“坏的”部分的迭代次数将与10成比例，如0(10)。一般地，我们仅使用第二算法， 但计算量取决于“坏的”模式的数目，并且首先近似并减少未解析模式的数目在计算上更有效。因此，可通过辨认被识别奇点空间的“好的”和“坏的”部分和适当地处理每个好的和坏的部分来实现性能的改善，如下面进一步讨论。因此根据某些实施例，响应于识别奇点，自适应迭代求解器可操作用于确定是否有奇点的可接受的近似可用。如果有好的近似可用，则用于近似的相应预处理器用于迭代求解奇点。当确定没有可接受的近似可用(即，要么没有可用的好的近似或近似被确定为还不利地影响线性系统)，则迭代求解器提取奇点的坏的部分从而得到有好的近似可用的奇点的剩余的好的部分。然后，用于奇点的好的部分的适当预处理器用于迭代地求解奇点好的部分。在某些实施例中，可以以不同方式处理提取的奇点坏的部分。对奇点坏的部分的处理在计算上的效率比好的部分的处理在计算过上的效率低，但由于从奇点提取“坏的” 部分，使计算总体上得到改善，因而使得“好的”部分能够以计算有效的方式被迭代求解。现在，考虑难于物理分离的奇点群，但是它们可以某些其他方式分离。例如，如果预处理的系统仅有几个分离的特征值，则可使用紧缩(deflation)。关于紧缩的更多信息， 请参见R. Nabben禾口 C. Vuik 的"A Comparison of deflation and Coarse grid correction applied to porous media flows", SIAM H. Numer. Anal. , v. 42,1631-1647 ；以及 J.Frank 禾口 C. Vuik 的"On the construction of deflation-based preconditioners", SIAM J. ki.Comput.，v. 23,442-462。一般地，更难于检查这类奇点的存在。在某些实施例中，其存在是从预处理器的迭代行为推导来的。因此，参考图7进一步说明根据自适应迭代求解器402的一个实施例构造预处理器的示例性工作流(如，图6的方框604中)。在方框71中，自适应迭代求解器402将当前奇点分为两组a)物理限定的，和b)特征值限定的。在一个实施例中，特征值限定的奇点更为通用并且包括物理限定的奇点。物理限定的奇点的算法通常更易于实施，且通常更为有效。如果仅几个特征值没有被抑制，则紧缩算法可能是有帮助的，但其更难于实施且计算成本高。会导致问题的物理特征(非受抑制的特征值)的示例是被建模的地下碳氢化合物储层的多孔介质中具有完全不同属性的层。这类问题可由建模的用户识别，或者对于非常复杂的模型，可由模式识别算法识别。对于这类简化情形，存在有效的紧缩算法。在方框72，自适应迭代求解器402尝试针对物理限定的奇点构造预处理器。对于物理限定的奇点，在方框701中，自适应迭代求解器402为每个物理限定的奇点确定奇点的近似是否可用。对于近似可用的奇点，在方框702中这些近似(多个)被用于近似奇点。 在方框703中，自适应迭代求解器402评估近似的质量(如，确定收敛是否可接受，如上所述)。对于在方框703中，其质量被确定为可接受的每个奇点，这类奇点的近似被用于构造预处理器，如方框704所示。对于近似不可用(如方框701中确定的那样)或对于近似质量被确定为不可接受(方框703中)的任何奇点，在方框73中，自适应迭代求解器402尝试提取“坏的”部分 (如使用下文进一步讨论的第二算法)。传统上，迭代求解器并不使用构造预处理器的自适应方法，如图7中的示例性方法。而是，传统迭代求解器可预先配置从而利用奇点近似或使用紧缩来构造预处理器，但传统迭代求解器一直不是自适应的从而不可能使用这两种构造技术中的一种或两种，如图7 的示例性方法所使用的。针对传统迭代求解器实施的预先配置的方法通常无法提供所需的计算性能，且如这里所述的自适应迭代求解器的某些实施例可自适应其方法以构造预处理器(如在图7的上述示例中所讨论的)，以便改善计算性能。根据一个实施例，给定矩阵A的迭代方法的收敛是通过特征值的分布确定的(至少对于对称矩阵)。假定特征值在数字a = 1和b = 1，000, 000之间。则迭代求解器中的迭代次数应与(b/a)的平方根 1000成比例。为了改善收敛，在某些实施例中，预处理器是作为B-IA引入的，其可减少特征值的数目。例如，继续上面的例子，B4A的特征值可在c =1和d = 100之间。然后，处理预处理器的迭代求解器的迭代次数与(d/c)的平方根成比例。一般地，MultiGrid和域分解算法“移动”特征值到谱的左手侧并改善迭代求解器的收敛。然而，如果存在奇点，则其特征值不动(即，不会移动到方程的左手侧)。根据本发明的某些实施例，可以使用算法“移动”未改动的特征值。本文提及的紧缩算法也可在某些实例中用于“移动”特征值到左侧，但它们需要具有特征向量的近似，这并不常用。为此，某些实施例中，紧缩算法通常视为处在最后的解决方案。在某些很好研究的情形中，如具有显著不同特性的多孔介质层，这可以有效地实现。现在简单地讨论可根据某些实施例构造的示例性预处理器。也就是，下面进一步讨论可根据某些实施例用于构造预处理器的示例性算法。当然，本发明的实施例不限于使用下述示例性预处理器构造算法。首先讨论可用于基于一个或多于一个奇点的近似构造预处理器的算法。因此，该示例性算法可在图7的方框72中采用。考虑矩阵
A10
A =為2為3，其中块^3对应于复数个奇点，^2是这些奇点周围的带，_ 0為2
而A11为剩余部分。假定我们可以另一个矩阵為3近似A33。则交迭相加(overlapping additive)形式的第一预处理器为
权利要求
1.一种方法，其包括通过自适应迭代求解器识别存在于线性方程系统中的至少一个奇点； 通过所述自适应迭代求解器构造第一预处理器以用于求解所述线性方程系统； 通过所述自适应迭代求解器确定所述第一预处理器的计算性能是否可以接受；以及当确定所述第一预处理器的计算性能不可接受时，通过所述自适应迭代求解器构造可替代的预处理器来求解所述线性方程系统。
2.根据权利要求1所述的方法，其中所述可替代的预处理器抑制被识别的至少一个奇点的被确定的坏的部分，从而导致被识别的至少一个奇点的剩余的好的部分的计算性能可以接受。
3.根据权利要求2所述的方法，其中所述可替代的预处理器包括所述第一预处理器， 其用于迭代求解所述被识别的至少一个奇点的剩余的好的部分。
4.根据权利要求1所述的方法，其中所述识别包括识别多个奇点，且其中所述第一预处理器用于提取所述多个奇点中的一些，用于求解所述线性方程系统，且其中所述可替代的预处理器用于提取所述多个奇点的剩余部分，用于求解所述线性方程系统。
5.根据权利要求4所述的方法，进一步包括采用紧缩算法提取所述多个奇点的进一步剩余部分以求解所述线性方程系统。
6.根据权利要求4所述的方法，进一步包括由所述自适应迭代求解器确定近似对于所述多个奇点中的至少某些奇点是可接受地有效的；并且其中构造所述第一预处理器包括根据所述近似构造所述第一预处理器。
7.根据权利要求6所述的方法，进一步包括由所述自适应迭代求解器确定近似对于所述多个奇点中的至少第二部分是不可接受地有效的。
8.根据权利要求6所述的方法，其中构造所述可替代的预处理器包括使用紧缩构造所述可替代的预处理器以用于提取所述多个奇点的所述至少第二部分。
9.一种方法，其包括通过自适应迭代求解器识别线性方程系统中存在的奇点； 通过所述自适应迭代求解器确定是否可接受近似可用于被识别的奇点； 当确定没有可接受的近似可用于所述被识别的奇点时，通过所述自适应迭代求解器提取所述被识别的奇点的坏的部分从而产生所述奇点的剩余好的部分，对于所述剩余好的部分，可接受的近似是可用的；以及通过自适应迭代求解器迭代求解所述奇点的剩余的好的部分的近似。
10.根据权利要求9所述的方法，其中所述确定是否可接受近似可用于被识别的奇点包括通过所述自适应迭代求解器构造用于求解所述线性方程系统的第一预处理器；以及通过所述自适应迭代求解器确定所述第一预处理器的计算性能是否可接受。
11.根据权利要求10所述的方法，进一步包括当确定所述第一预处理器的计算性能不可接受时，通过所述自适应迭代求解器构造可替代的预处理器用于求解所述奇点的所述剩余的好的部分。
12.根据权利要求11所述的方法，其中所述可替代的预处理器包括所述第一预处理器。
13.根据权利要求9所述的方法，进一步包-·-括通过所述自适应迭代求解器求解所述被识别的奇点的被提取的坏的部分。
14.存储在计算机可读介质中的计算机可执行软件代码，当其由计算机执行时使得所述计算机执行一种方法，所述方法包括识别存在于线性方程系统中的至少一个奇点； 确定所述至少一个奇点的近似；基于所确定的近似构造第一预处理器以由迭代求解器用于求解所述线性方程系统； 确定所述预处理器的计算性能是否可接受；当确定所述预处理器的计算性能不可接受时，构造可替代的预处理器以由所述迭代求解器用于求解所述线性方程系统。
15.根据权利要求14所述的计算机可执行软件代码，其中所述可替代的预处理器不基于所述确定的近似。
16.根据权利要求14所述的计算机可执行软件代码，其中所述可替代的预处理器是使用紧缩构造的。
17.根据权利要求14所述的计算机可执行软件代码，其中确定所述至少一个奇点的近似包括确定近似是否可用于所述至少一个奇点；以及其中当确定所述近似不可用于所述至少一个奇点时，则构造所述可替代的预处理器以由所述迭代求解器用于求解所述线性方程系统。
18.根据权利要求14所述的计算机可执行软件代码，其中所述方法进一步包括 其中所述识别包括识别多个奇点；以及其中所述确定近似包括确定所述多个奇点的至少第一个奇点的近似。
19.根据权利要求18所述的计算机可执行软件代码，其中所述方法进一步包括由所述迭代求解器使用所述第一预处理器提取所述多个奇点中所述至少第一个奇点， 以求解所述线性方程系统。
20.根据权利要求19所述的计算机可执行软件代码，其中所述方法进一步包括 由所述迭代求解器使用所述可替代的预处理器提取所述多个奇点中的至少第二个奇点，以求解所述线性方程系统。
21.根据权利要求20所述的计算机可执行软件代码，其中所述方法进一步包括 确定近似不可用于所述多个奇点中的所述至少第二个奇点。
22.根据权利要求14所述的计算机可执行软件代码，其中所述方法进一步包括 其中所述识别包括识别存在于所述线性方程系统中的多个奇点；为所述多个奇点的每个确定相应的近似是否是可接受有效的；以及对于所述多个奇点中相应的近似是可接受有效的每个奇点，使用所述相应的近似构造所述第一预处理器以便由所述迭代求解器用于提其取相应的近似可用的所述奇点。
23.根据权利要求22所述的计算机可执行软件代码，其中所述方法进一步包括 构造所述可替代的预处理器以便由所述迭代求解器用于提取所述多个奇点中相应的近似被确定为不可用的每个奇点。
24.一种方法，其包括由自适应迭代求解器识别存在于线性方程系统中的多个奇点； 由所述自适应迭代求解器构造第一预处理器，用于提取所述奇点的第一部分以求解所述线性方程系统，其中所述第一预处理器基于所述多个奇点的至少一个的近似；由所述自适应迭代求解器构造第二预处理器，用于提取所述奇点的第二部分以求解所述线性方程系统，其中所述第二预处理器不是基于所述多个奇点的至少一个奇点的近似； 以及由所述自适应迭代求解器处理所述第一预处理器和所述第二预处理器以求解所述线性方程系统。
25.根据权利要求M所述的方法，其中所述第二预处理器是通过将解分解为坏的部分和剩余好的部分而构造的。
26.根据权利要求25所述的方法，进一步包括 使用紧缩算法求解所述线性方程系统的至少一部分。
27.一种方法，其包括通过用于求解线性方程系统的迭代求解器处理接收的模型； 通过所述迭代求解器识别至少一个奇点；基于观察的所述迭代求解器在求解所述线性方程系统中的性能，通过所述迭代求解器确定是否排除所识别的至少一个奇点的一个或多于一个；以及当确定要排除所述识别的至少一个奇点的一个或多于一个时，所述迭代求解器自适应以排除所确定的所述识别的至少一个奇点的一个或多于一个。
28.根据权利要求27所述的方法，其中所述自适应包括构造预处理器以排除所述确定的所述识别的至少一个奇点的一个或多于一个。
29.根据权利要求27所述的方法，其中所述确定包括基于所观察的性能，所述迭代求解器自动确定是否排除所述识别的至少一个奇点的所述一个或多于一个。
30.一种方法，其包括由用于求解线性方程系统的迭代求解器处理接收的模型，所述迭代求解器具有收敛于解所要求的预定的预期数目的迭代；所述迭代求解器识别至少一个奇点；以及所述迭代求解器确定所识别的至少一个奇点是否导致所述收敛要求的迭代数目增加超过预定的预期迭代数目。
31.根据权利要求30所述的方法，进一步包括当确定所述至少一个奇点导致所述收敛要求的迭代数目超过预定的预期迭代数目时， 所述迭代求解器自适应排除所述识别的至少一个奇点。
32.根据权利要求31所述的方法，进一步包括 加权所述识别的至少一个奇点；以及至少部分基于所述加权确定是否自适应以排除所识别的至少一个奇点。
33.根据权利要求30所述的方法，进一步包括所述迭代求解器确定是否自适应处理所述线性方程系统以排除所述识别的至少一个奇点O
34.根据权利要求33所述的方法，进一步包括确定与排除所述识别的至少一个奇点关联的计算成本；以及其中所述确定是否自适应包括平衡所确定的计算成本和确定的所述收敛要求的迭代次数的增加。
35.根据权利要求30所述的方法，进一步包括至少部分基于所述迭代求解器在收敛于解的计算性能，所述迭代求解器自动自适应其处理以选择性排除所述识别的至少一个奇点的一个或多于一个。
36.一种方法，其包括由自适应迭代求解器识别存在于线性方程系统中的可能奇点，所述自适应迭代求解器可操作用于采用迭代方法求解所述线性方程系统；由所述自适应迭代求解器分析求解所述线性方程系统的计算性能；以及基于其计算性能，所述自适应迭代求解器自适应处理提供所需性能的所述可能奇点。
37.根据权利要求36所述的方法，其中所述自适应处理所述可能奇点包括 构造预处理器用于排除所述可能奇点中选择的奇点。
全文摘要
本发明提供了一种自适应迭代求解器，其采用自适应处理提取奇点以求解线性方程系统。自适应迭代求解器动态确定如何在线性方程系统中存在一个或多于一个奇点时调整其性能。在某些实施例中，自适应迭代求解器可识别可能的奇点，且然后分析其性能以调整对可能奇点的处理，以提供理想的性能(即，为实现对解的收敛)。因此，不是被预先配置以提供对某些被识别的奇点的某种处理(如消除)，在某些实施例中，迭起求解器基于其计算性能调整其对奇点的处理。
文档编号G06F7/60GK102165413SQ200980138527
公开日2011年8月24日 申请日期2009年7月17日 优先权日2008年9月30日
发明者A·马特索金, I·米谢夫, S·涅波姆亚什 申请人:埃克森美孚上游研究公司
技术领域：
本发明一般涉及求解线性方程系统的迭代求解器，且更具体地涉及自适应迭代求解器，其可操作用于调整/适应(adapt)存在奇点时的性能。
背景技术：
已知有各种技术用于求解线性方程系统。通常会在给定真实世界系统的各种基于计算机的三维(“3D”)模拟或建模中碰到线性方程系统(并需要求解)。例如，这样的基于计算机的3D建模可用于将这样的真实世界系统建模为机械和/或电子系统(如可用于汽车、飞机、轮船、潜水艇、宇宙飞船等)，建模人体(如人体全部或部分建模，如重要器官等)、天气形势，地下碳氢化合物储层(如气田或油田)以及各种其他要建模的真实世界系统。通过这样的建模，可以分析和/或预测被建模的系统的将来潜在性能。例如，呈现给建模系统的某些变化的条件对系统未来性能的影响可通过与基于计算机的的模型的交互以及对这种模型的分析进行评估。作为例子，多孔介质中流体流量/流动(fluid flow)的建模是石油工业的焦点。 不同的基于计算机的模型用于石油工业的不同领域，但大多包括以偏微分方程(PDE’ s)系统描述模型。一般地，这种建模通常要求针对给定网格在空间和时间上离散PDE’ s，并针对每个时间步骤执行计算直到达到规定的时间。在每个时间步骤中，离散方程被求解。通常离散方程是非线性的，并且求解过程是迭代的。非线性迭代方法的每个步骤通常包括非线性方程系统的线性化(如，雅可比(Jacobian)构造)、求解该线性系统和属性计算，其用于计算下一雅可比构造。图1示出一般工作流，其通常用于地下碳氢化合物储层中流体流量对时间的基于计算机的模拟(或建模)。内循环101是求解非线性系统的迭代方法。每次通过内循环101 通常包括非线性方程系统11的线性化(如，雅可比构造)、求解线性系统12和属性计算13， 其用于计算下一雅可比构造(当循环到方框11时)。外循环102是时步(time step)循环。如图所示，对于每个时步循环，边界条件可以在方框10中定义，并且然后在执行完内循环101后，可以在方框14中输出针对时步计算的时步结果(如，结果可存储到数据存储介质和/或提供给软件应用程序以生成表示针对相应时间步建模的地下碳氢化合物储层中流体流量的显示)。如上所述，除了地下碳氢化合物储层中流体流量建模外，真实世界系统的基于计算机的3D建模可以类似方式执行，即可采用迭代方法求解线性方程系统(如图1 中方框12所示)。线性方程系统的求解是计算量非常大的任务，因此需要有效算法。有两类线性求解器1)直接法和幻迭代法。直接法通常依靠有效形式的(Russian消元法来分解线性系统矩阵。该解是通过执行后向求解(backward solve)，然后执行前向求解(forward solve) 获得的。分解因子的计算成本和存储成本会很高，因为必须计算和存储所有新的填充项。计算效率很大程度上依赖于矩阵大小和带宽。三维模型导致矩阵非常大、稀疏，并具有相当的带宽。该大小和大带宽导致非常大量的必须计算和存储的新填充项。因此，无论是从计算成本还是存储成本的角度，直接法用于实际3D建模的成本通常是无法想象的。迭代法提供求解大稀疏线性系统的另一种方法。当采用迭代法时，解在每次迭代中被更新直到达到收敛。每次迭代仅要求以稀疏矩阵进行运算且通常与未知数的数目成比例。不幸的是，对于大的线性方程系统，标准迭代方法收敛非常慢。可以通过使用预处理矩阵的新矩阵取代原矩阵显著改善这种情形。例如，原问题Ax = b可以由具有相同解的修正的问题B4Ax = Β_、取代，其中B是预处理矩阵(或简称为“预处理器(preconditioner) ”)。 具有修正的矩阵的每次迭代以矩阵B求解问题，Bu = r。针对椭圆和抛物线问题开发高效预处理器已经取得了相当进展。主要进展是开发了计算成本低(如运算数目与未知数的数目成比例)且有效的(如具有不随问题大小变化的少量迭代)的预处理器。这种预处理器的最佳已知示例是多重网格(MultiGrid)和域分解(Domain Decomposition)算法。这样的预处理器在本文中可称为“最优预处理器”，在这种预处理器中收敛所需的迭代数目不随问题(或模型)的大小增大而增加。最优预处理器的第一个已知示例是多重网格，其通过作用于不同网格上误差的不同成分减少误差。最优预处理器的第二已知示例是域分解。域分解算法通过求解部分原始域中相同或类似的问题来构造解。非迭代域分解法在域的每部分(所谓的子域，图2所示例子的Q1 和Ω2)中求解类似问题以及公共接口 Y上的不同问题。迭代域分解法求解扩展域上的问题，扩展域由原始域和交迭带(strip)形成，如图3所示。全局问题的解由子域问题的解组成。可以以加法或乘法方式应用域分解算法。加法域分解算法同时计算其解的各部分。乘法方法中的每个步骤都包括几个子步骤。在第一子步骤，一组子域首先计算解。在下一子步骤，下一组子域使用第一组的结果计算其解，如此类推。因此，如果模型尺寸增长，则如多重网格和域分解的最优预处理器已知是最优的。 例如，假定模型以100，000个单元开始，但在随后的某个时间使用具有上百万个单元的更大模型。一般地，可采用诸如多重网格或域分解的最优预处理器，并且对于所有的三种模型，其可以在固定数目的迭代(例如10次迭代)中收敛于解。其他已知预处理器随着模型尺寸增长要求更多次迭代以达到收敛，而最优预处理器将通常在固定次数的迭代中收敛， 与模型尺寸是否增长无关。不幸的是，如果PDE’ s的原始系统或线性系统具有某些特殊特征，那么即使最优预处理器的性能也会显著恶化。例如，如果PDE’s的系统的解在域的某部分极其大，或没有导数，则在求解线性系统时会产生困难。解的这类行为通常称为“奇点”。当建模地下碳氢化合物储层中的流体流量时，各种特殊影响或特征可能存在于被建模的地下区域中，如井、断层或其他地质特征。被建模的真实世界系统中出现的这类特殊影响或特征可能产生奇点。一般地，“奇点”是指线性系统或物理模型中的任何特征，其削弱求解器使用的迭代方法(如预处理器)的收敛性。例如，奇点的存在可导致最优预处理器不能在预期的迭代次数内收敛。例如，如上所述，最优预处理器通常在固定的迭代次数内收敛，无论模型尺寸是否增长。然而，如果在模型中碰到奇点，则传统最优预处理器，如多重网格和域分解将不能在模型的固定迭代次数内收敛。通常，奇点是由地下碳氢化合物储层的建模中出现的井或不连续系数及其特殊行为引起的，特殊行为如被建模的地下岩石属性。井通常被建模为点或线源，并且在具有非常小尺寸的区域中(数学抽象中的零)，某些有限量的流体或者注入到地下，或者由井产生 (即从地下抽取)。这导致解及其导数极其大(数学意义上的无穷大)。解的这种行为频繁地导致预处理的迭代方法收敛性降低。许多不同井模型用于石油工业。其中大多数都不会写为椭圆或抛物线方程。因此，上述多重网格和域分解对于这类线性系统不是很有效。此外，某些地质特征，如断层、裂缝(fracture)或尖灭(pinch-out)也可能在预处理的迭代方法中引起问题。也就是，某些地质特征也可能引起奇点，该奇点降低 (deteriorate)预处理方法的收敛性。某些地质特征可能引起问题的一个原因是这类地质特征中的流体流动可能与周围的多孔介质中的流动显著不同。如上面所考虑的，已经做出了许多努力来为线性系统开发有效的预处理器。作为一个例子，使用不完全LU分解的预处理器不受井的存在、断层或裂缝的影响，但对于非常大的线性系统也不是有效的。作为另一个例子，有人提出消除某些最优预处理器中奇点的技术，如在域分解和多重网格中。例如，已经尝试使用某些域分解法消除奇点，但收敛性取决于交迭且被降低，参看 H. Cao，H. A. Tchel印i，J. Wallis 和 H. Yardumian 的 “Parallel Scalable Unstructured CPR-Type Linear Solver for Reservoir Simulation，，， SPE Annual Conference and Exhibition，2005 年 10 月，德克萨斯的达拉斯。多重网格法更成功，参看 K. Stuben, T. Clees, H. Klie, B. Lu 和 M. F. Wheeler 的 Algebraic multigrid methods for the efficient solution of fully implicit formulations in reservoir simulation, SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨斯休斯顿；Τ· Clees 禾口 L. Ganzer 的 An efficient multigrid solver strategy for adaptive implicit methods in oil reservoir simulation,SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨斯休斯顿；以及 H. Klie,M. F. Wheeler, K. Stuben 和 T. Clees 的 Deflation AMG solvers for highly ill-conditioned reservoir simulation problems, SPE Reservoir Simulation Symposium, 2007 年 2 月，德克萨其jf休其jf顿。然而，上面提出的消除最优预处理器中奇点的技术无法保持最优预处理器的性能。例如，假定预期最优预处理器在例如10次迭代内收敛于解，无论模型的大小(假定没有碰到奇点)；则模型中特殊特征的存在可能产生奇点，其导致最优预处理器要实现收敛需要100次迭代。已经提出的用于消除奇点的传统技术可改善最优预处理器的性能，以便其可在例如25次迭代内收敛，但不能实现其预期的性能(在该例子中为10次迭代)，如果模型中不存在引起奇点的特殊特征，则将实现该预期性能。进一步，上面提出的消除奇点的技术依靠预先识别奇点的存在，然后遵从消除任何这类预先识别的奇点的预定方案(regiment)。也就是说，求解器被预先配置以消除预先识别的奇点。因此，要求用户(如工程师、分析人员等)预先识别模型中被认为可能产生奇点的特殊特征，且用户预先配置求解器以消除预先识别的奇点。求解器本身不用于识别奇点，也不涉及判断是否消除预先识别的奇点。而是所有这类奇点的识别和关于如何预先配置求解器以消除识别的奇点的判断都是在求解器外进行的(如，通过工程师、分析人员或其他用户完成)。
发明内容
本发明公开一种采用自适应迭代求解器的系统和方法。也就是说，提供了一种迭代求解器，其采用自适应过程提取奇点以求解线性方程系统。因此，根据某些实施例，提供了自适应迭代求解器，其可操作用于确定如何在存在一个或多于一个奇点的情况下调整其性能。因此，根据本发明的某些实施例，提供的自适应迭代求解器用于求解线性方程系统，如通常用于基于计算机的3D建模。在某些实施例中，自适应迭代求解器可识别可能的奇点，并且之后分析其性能以调整对可能奇点的处理，从而提供所需的性能(即，用于实现至解的收敛性)。因此，并不是被预先配置为提供对某些预先识别的奇点的某种处理(如消除)，在某些实施例中，迭代求解器基于其计算性能调整其对奇点的处理。例如，自适应迭代求解器的实施例可尝试第一奇点处理(如采用第一预处理器提取某些奇点)，并基于其计算性能的分析(如收敛所要求的迭代次数和/或每次迭代的计算成本等)，自适应迭代求解器可调整其奇点处理(如通过将不同预处理器用于提取奇点)， 从而实现以提供所需性能的方式求解线性方程系统的技术。在调整其性能过程中，在某些实施例中，自适应迭代求解器可提取比所有预先识别的奇点较少的奇点和/或可识别要提取的额外奇点。例如，自适应迭代求解器可推导出存在于被建模的真实世界系统中且最初被认为可能引起奇点的某些特殊影响或特征实际上不产生为改善性能而应当被提取的奇点。作为另一个例子，在其处理的过程中，自适应迭代求解器可能检测进一步的奇点(这些奇点并不被预先识别为可能的奇点)，其应被提取以改善求解器的性能。在某些实施例中，自适应迭代求解器调整迭代求解过程中使用的预处理器，从而以提供所需性能水平的方式处理奇点。例如，在某些实施例中，自适应迭代求解器构造预处理器以提取某些奇点，且其处理自适应迭代求解器的过程可修正/调整其构造的预处理器 (例如，以提取可能被发现的额外奇点和/或不提取某些预先识别的可能奇点)以求解线性方程系统。在某些实施例中，自适应迭代求解器是最优求解器，其调整其性能，从而以维持模型中不存在奇点时遇到的迭代次数的方式处理奇点。在某些实施例中，自适应迭代求解器可选择以导致迭代次数增加超过模型中不存在奇点时碰到的迭代次数的方式调整其性能。 然而，增加迭代次数的这类自适应可以由自适应迭代求解器智能地执行(相对于由求解器操作的预先配置产生)。例如，自适应迭代求解器可以确定在某些实例中，迭代次数增加相对于具有每次计算成本极其高昂的较少迭代更为理想。在某些实施例中，在分析其性能时，自适应迭代求解器考虑迭代的次数和每次迭代的计算成本。例如，在某些情形中，特定预处理器可用于以显著减少实现收敛所需迭代次数的方式处理奇点，但是处理每次迭代的计算成本(如要求的CPU时间量和/或要求的内存)可能很高。因此，在某些情形中，自适应求解器可得出这样的结论，每次迭代计算成本不是很高的迭代次数的少量增加是适当的解决方案。给定奇点的相对重要性可能基于各种考虑的一个或多于一个方面，如由奇点导致的迭代求解器性能的相应退化量(如果奇点没有被预处理器提取)。有不同的可能方式对奇点排序。一种排序方式是给不同的奇点分配不同的权重。在某些实施例中，奇点越重要， 分配的权重越大。自适应迭代求解器可至少部分基于分配给奇点的相对权重来确定其对奇点的可能的处理(例如，确定预处理器用于提取可能奇点中选择的奇点)。在某些实施例中，分配的权重可以由自适应迭代求解器在其处理过程中更新(例如，基于在存在奇点时自适应迭代求解器对其性能的评估等)。在很多实例中，忽略某些低权重的可能奇点不会不利地影响迭代求解器的收敛，因为迭代方法考虑这些奇点。下面进一步说明可由自适应迭代求解器采用的用于识别可能奇点并基于其计算性能自适应其对这些可能奇点的处理的各种示例性技术。在某些实施例中，自适应迭代求解器采用两步法构造预处理器。在这样的实施例中，自适应迭代求解器首先尝试从可用于被识别的奇点的近似构造预处理器。对于每个这种近似，自适应迭代求解器可以评估其性能，并确定预处理器的性能不可接受的那些近似(如，要么收敛太慢，每次迭代具有不理想的计算成本，等)。对于近似不可用或性能被确定为不可接受的那些奇点，自适应迭代求解器采用可替换的预处理器构造技术，如基于将解表示为奇点部分及其补元(complement) 的和的技术。本文将进一步说明可以在某些实施例中采用的示例性预处理器构造算法。前面已经相当宽泛地概括了本发明的特征和技术优点，从而可以更好地理解本发明以下的详细说明。将在下文描述本发明的额外特征和优点，其形成本发明权利要求的主题。本领域技术人员应该理解公开的概念和具体实施例易于用作修改或设计执行本发明相同目的的其他结构的基础。本领域技术人员还应该认识到这样的等效构造不偏离权利要求中限定的本发明的精神和范围。根据以下说明并结合附图可以更好地理解被认为是本发明特征的新颖特征(包括运算的组织和方法)以及本发明的进一步的目的和优点。然而应当清楚地理解，提供的每附附图目的在于例示和说明，而非意在限制本发明。
为了更完整地理解本发明，可参考结合附图的以下说明，其中图1示出通常用于地下碳氢化合物储层中流体流量对时间的基于计算机的模拟 (或建模)的一般工作流；图2示出可以在非交迭域分解方法中求解的子域；图3示出可以在交迭域分解方法中求解的交迭子域；图4示出根据本发明一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图5示出根据本发明另一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图6示出根据本发明另一个实施例实施自适应迭代求解器的基于计算机的示例性系统的方框图；图7示出根据本发明一个实施例构造预处理器的自适应迭代求解器的示例性操作流；图8示出根据一个实施例构造用于奇点(一个或多个)的预处理器的自适应迭代求解器的示例性操作流，对于所述奇点近似不可用或被确定为不可接受；以及
图9示出可实施根据本发明某些实施例的自适应迭代求解器的所有或部分的示例性计算机系统。
具体实施例方式参考图4，其示出根据本发明一个实施例的示例性基于计算机的系统400的方框图。如图所示，系统400包括基于处理器的计算机401，如个人计算机(PC)、膝上型计算机、 服务器计算机、工作站计算机、多处理器计算机、计算机集群等。此外，自适应迭代求解器 (如软件应用程序)402在这类计算机401上执行。计算机401可以是能够执行自适应迭代求解器402的任何计算设备，如本文的进一步说明。尽管在图4中自适应迭代求解器402 示为在计算机401上执行，以易于图示，但是应该认识到这类求解器402可以在本地计算机 401或经通信网络与计算机401通信连接的远程计算机(如，服务器计算机上)上驻存和/ 或执行，通信网络如局域网(LAN)、因特网或其他广域网(WAN)等。而且，应该理解计算机 401可包括多个集群的或分布的计算设备(如服务器)，如本领域所熟知的，自适应迭代求解器402可跨这些计算设备存储和/或执行。如同许多传统的基于计算机的迭代求解器，自适应迭代求解器402包括存储到计算机可读介质的计算机可执行软件代码，这些代码可以由计算机401的处理器读取，并且由这类处理器执行时会引起计算机401执行下文进一步说明的这种自适应迭代求解器402 的各种操作。自适应迭代求解器402可操作为使用迭代过程来求解线性方程系统。如上所述，这样的迭代求解器通常用于3D基于计算机的建模。例如，自适应迭代求解器402可用于(图1的)传统工作流的运算方框12，以进行地下碳氢化合物储层中流体流的3D基于计算机的建模。在图4所示的例子中，模型406(例如，包含有关要建模的真实世界系统的各种信息，如关于地下碳氢化合物储层的信息，针对该储层，将建模流体流量随时间的变化) 存储在通信耦合到计算机401的数据存储装置405中。数据存储装置405可包括硬盘、光盘、磁盘和/或其他可操作用于存储数据的计算机可读数据存储介质。如同用于3D基于计算机的建模的许多传统迭代求解器，自适应迭代求解器402可操作用于接收模型信息406，并执行用于求解线性方程系统的迭代方法，所述线性方程系统用于生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量随时间变化的模型。根据本发明的实施例，自适应迭代求解器402可操作用于分析其计算性能以确定是否自适应其对模型406中可能奇点(singularity)的处理，如方框403所示。如方框404 所示，当确定应当自适应其对模型中可能奇点的处理时，自适应迭代求解器402自适应其对可能奇点的处理以提高其在求解用于3D基于计算机的建模的线性方程系统的性能。例如，自适应迭代求解器402可适于使用预处理器(多个)来提取可能奇点的多个不同奇点以获得所需的计算性能。因此，无需局限于对预先识别的奇点(一个或多个)执行某种预先配置的消除，实施例自适应迭代求解器402可操作用于自适应其奇点处理。作为一个例子，自适应迭代求解器402可以是预计在给定次数的迭代即10次迭代内收敛的最优求解器，其中不考虑模型 406的大小。然而，由于遇到模型406中的某些奇点，自适应迭代求解器402的性能可能会衰减，导致要求10次以上迭代才能收敛，除非自适应迭代求解器402调整其对这类奇点的处理。在某些实施例中，自适应迭代求解器402调整其对奇点的处理(例如，通过构造预处理器来提取识别的可能奇点中选择的奇点)，以实现在要求的10次迭代内收敛的处理技术。如上所述，在某些实施例中，如果认为每次迭代的计算成本在不同情况下太昂贵，则自适应迭代求解器402可以智能选择使用增加收敛的迭代次数(如在上述示例中超过10次) 的处理技术。下面进一步讨论不同示例性方式，其中自适应迭代求解器402的实施例可评估其性能并调整其对奇点的处理。参考图5，其示出根据本发明实施例的另一个示例性基于计算机的系统500的框图。类似于图4中的示例性系统400，系统500包括基于处理器的计算机401，其上执行自适应迭代求解器402的实施例，在该例子中示为自适应迭代求解器402A。而且，如图4的示例，模型406 (如包含关于要建模的真实世界系统的各种信息，如地下碳氢化合物储层的信息，为此信息将建模流体流量随时间的变化)存储在通信连接到计算机401的数据存储装置405中。如上所述，自适应迭代求解器402A可操作用于接收模型信息406并执行求解线性方程系统的迭代方法以生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量对时间的模型，其可用于图1的示例性流中方框12中。在图5的示例性实施例中，方框501中，自适应迭代求解器402A识别可能的奇点。 可以以各种方式识别模型中可能的奇点。例如，可以基于有关被建模的真实世界的已知信息预先识别(如由用户，如工程师、分析人员等识别)某些可能的奇点，并且模型406的预先被识别的可能奇点可以分类(存储)到存储在数据存储装置405中的目录(catalog) 505 中(如任何适当的计算机可读数据结构，如文件、数据库等)。因此，已知存在于被建模的真实世界系统中并被怀疑将产生奇点的各种特征可以在目录505中被预先识别。例如，在地下碳氢化合物储层中流体流量的建模中，可能引起模型中的奇点并且可以在要建模的目标区域中被预先识别的公知特征可以包括某些地质特征(如断层、大裂缝、尖灭等等)和/或某些工程特征(如水平井、倾斜井和垂直井、连接的设施网络等)的存在。此外，在某些实施例中，自适应迭代求解器402A自身可以在处理模型的过程中发现某些可能的奇点。例如，在处理过程中，求解器402A可以通过其对被处理的方程(如矩阵)的分析来识别可能的奇点。例如，对于给定的建模过程，自适应迭代求解器402A可以将异常矩阵项或结构(如极大项、非对角占优矩阵、M矩阵中非对角正项等)辨认为存在于模型的相应部分的可能奇点。在某些实施例中，自适应迭代求解器402A保持列表506 (其可采用任何适当的计算机可读数据结构的形式，如文件、数据库等)，该列表存储在数据存储装置405内，其中这类列表506识别自适应迭代求解器402A要提取的当前奇点。可用于提取奇点的示例性技术在下面进一步讨论。在一个实施例中，当可能的奇点在方框501中被识别时，其被加入到要提取的当前奇点的列表506中。当然，如下面进一步的讨论，列表506是动态的并且可以由自适应迭代求解器402A修改，因为其确定如何最好地调整其对奇点的处理以提供所需水平的性能。如下面进一步的讨论，在某些实施例中，当前奇点的列表和/或预先识别的可能奇点的目录可包括分配给奇点的相应权重。在方框502中，自适应迭代求解器402A构造预处理器，其提取当前奇点(S卩，列表 506上被识别的奇点)。最初，列表506可包括在目录505中预先定义的所有可能的奇点。 如下面进一步讨论，在某些情形中，可以从当前列表506中去除一个或多于一个这类可能的奇点(因此，其不被抽取)和/或可以将自适应迭代求解器402A发现的(如通过分析正被处理的矩阵)一个或多于一个可能的奇点加入到当前列表506中。再次，可在方框502 中用于构造预处理器以提取所选奇点(即，当前列表506上的奇点)的示例性技术在下面进一步讨论。在某些实施例中，要包括在当前列表506中的奇点(由预处理器提取)和要从列表506中去除的奇点的确定可至少部分基于分配给奇点的相对权重。例如，如果分配有高权重的奇点没有被提取，则可以认为其对迭代求解器的性能有高退化作用，并且可以认为分配有低权重的奇点对迭代求解器的性能有较低退化作用；在此情形下，具有最高权重的奇点可以被选择为包含在当前列表506上由预处理器提取。在方框503中，自适应迭代求解器402A在迭代求解线性方程系统中使用构造的预处理器来确定3D基于计算机的模型的相应部分。可用于某些实施例并用于迭代求解线性方程系统的示例性预处理器在下面进一步说明。当然，本发明的实施例并不限于使用任何特定预处理器，某些实施例可以被实施为自适应任何各种不同预处理器的应用。在方框403中，自适应迭代求解器402A分析其性能以确定是否自适应模型中可能奇点的处理。虽然图5中为了图示的便利示为线性流，但应该理解各种操作不限于所示的顺序，且其中的某些方框可并行执行。例如，在某些实施例中，在方框503中处理构造的预处理器的同时，自适应迭代求解器402A可分析其性能以确定是否调整其对奇点的处理。当确定应当自适应处理可能的奇点时，在方框404中，自适应迭代求解器402A自适应其对可能奇点的处理。在某些情形下，这可能在方框503的迭代过程收敛于一个解之前中断其在方框503中的处理，以在方框404中自适应其对可能奇点的处理。在某些实施例中，作为方框403中的分析的一部分，方框504中自适应迭代求解器 402A权衡利用排除所选奇点(列表506上)的预处理器获得的迭代性能的增益和每次迭代中预处理器的计算成本。例如，在方框403中分析其性能时，自适应迭代求解器402A可同时考虑收敛的迭代次数和每次迭代的计算成本。例如，在某些情形中，可以以显著减小实现收敛的迭代次数的方式使用特定预处理器来处理当前奇点(列表506中)，但处理每次迭代的计算成本(如需要的CPU时间量和/或需要的内存)可能非常高。因此，在某些情形下， 在方框504中，自适应迭代求解器402A可得出这样的结论，如果每次迭代的计算成本不是如此高昂，那么迭代次数的少量增加是适当解。参考图6，其示出根据本发明实施例的另一个示例性基于计算机的系统600的方框图。类似于图4的示例性系统400和图5的系统500，系统600包括基于处理器的计算机 401，其上执行自适应迭代求解器402的一个实施例，在此示例中显示为自适应迭代求解器 402B。而且，和图5的例子一样，模型406(如包含关于要建模的真实世界系统的各种信息， 如关于地下碳氢化合物储层的信息，为获得此信息建模流体流量随时间的变化)、预先识别的可能奇点的目录505和当前要提取的奇点的列表506存储在与计算机401通信连接的数据存储装置405中。如上所述，自适应迭代求解器402B可操作用于接收模型信息406，并执行求解线性方程系统的迭代方法以生成3D基于计算机的模型，如地下碳氢化合物储层中流体流量对时间的模型，其可用于图1的示例性流程的方框12中。在图6的示例性实施例中，自适应迭代求解器402B可用于工作流，如以上图1中所述。例如，自适应迭代求解器402B可用于时步循环601中，如图1中的示例性外部循环 102，其中下面讨论的各种操作可在时步循环601中执行。在方框602中，检查物理问题(例如，模型406和/或相应的真实世界系统)和/或线性系统以识别当前和可能的新奇点。可以以各种方式识别模型中可能的奇点。例如， 某些可能的奇点可基于已知的关于被建模的真实世界系统的信息被预先识别(如由用户识别，如工程师、分析人员等)，并且预先识别的模型406的可能奇点可分类(存储)到存储在数据存储装置405中的目录505中(如任何适当的计算机可读数据结构，如文件、数据库等)。也就是说，可执行某种预处理610以由预先识别的可能奇点初始构成目录505。因此，已知存在于被建模的真实世界系统中并且可能产生奇点的各种特征可能在目录505中被预先识别。例如，在建模地下碳氢化合物储层的流体流量的过程中，可能产生模型中的奇点并且可以在要建模的目标区域中被预先识别的共同特征可包括某些地质特征(如断层、 大裂缝、尖灭等)和/或某些工程特征(如水平井、倾斜井和垂直井、连接的设施网络等) 的存在。在此示例性实施例中，在时步循环601的每个时步中，检查线性系统以获得当前奇点和由于物理系统变化导致的可能新奇点，物理系统变化如井被打开和关闭、井从主要生产到排放水或气的切换和/或发生在正被建模的地下碳氢化合物储层内的其他变化。一开始，检查所有分类的可能奇点。也就是，自适应迭代求解器可评估目录505中分类的每个可能奇点以确定其是否为真正的奇点(即，它们的存在是否真正退化(degrade)求解器 402B采用的迭代方法的收敛性)，并且那些被确定为一定程度上退化迭代方法性能的真正奇点被加入到要去除的当前奇点的列表506。此外，在方框603中，自适应迭代求解器402B自身可基于对针对模型406处理的矩阵的检查发现某些可能奇点。例如，对于给定的建模过程，异常矩阵项或结构(如极大项、非对角占优的矩阵、M矩阵中非对角正项等)可以被自适应迭代求解器402B辨认为模型相应部分中存在的可能奇点。在某些实施例中，自适应迭代求解器402B保持列表506 (其形式可以是任何适当的计算机可读数据结构，如文件、数据库等)，其存储在数据存储装置405中，其中这种列表 506识别自适应迭代求解器402B要提取的当前奇点。最初，列表506可包括目录505中预先识别并在方框603中确定的所有可能的奇点。然而，要提取的当前奇点的列表506是动态的，且因此可通过自适应迭代求解器402B在处理模型406的过程中进行调整。在方框604中，自适应迭代求解器402B构造提取当前奇点的预处理器(即在列表 506上识别的那些奇点)。如下面进一步的讨论，在某些情形中，可以从当前列表506中去除一个或多于一个这种可能的奇点(以便它们不能被提取)，并且/或者可以将一个或多于一个自适应迭代求解器402B发现的可能奇点(如通过分析被处理的矩阵)加入到当前列表506中。再次，下面进一步详细讨论可在方框604中用于构造提取所选奇点(即，当前列表506上的奇点)的处理器的示例性技术。在方框605中，自适应迭代求解器402B在迭代求解线性方程系统中使用构造的预处理器以确定3D基于计算机的模型的相应部分。下面进一步说明可用于某些实施例的示例性预处理器，以及其在迭代求解线性方程系统中的使用。当然，本发明实施例并不限于使用任何特定预处理器，某些实施例可实施为自适应于各种不同预处理器中任何预处理器的应用。在方框606中，自适应迭代求解器402B分析预处理器的性能，且如果需要，调整预处理器从而改善求解器的计算性能。在方框607中，可更新当前奇点的列表506以反映要提取奇点中的任何变化，如方框606中确定的那样。虽然图6中为了便于图示而示为线性流，但是应该认识到各种操作不限于显示的顺序，并且某些方框可并行执行。例如，在某些实施例中，自适应迭代求解器402B在方框605中处理构造的预处理器的同时，可分析其性能(方框606)从而确定是否调整其对奇点的处理。当确定应自适应可能奇点的处理时，自适应迭代求解器402B通过更新要提取的当前奇点的列表506(在方框607中)自适应可能奇点的处理。在某些情形中，可以在方框605的迭代过程收敛到解之前中断方框605中的处理，以在方框607中自适应要提取的当前奇点的列表506，其中操作可返回到方框602以最终构造(在方框604中)另一个预处理器以提取修订的奇点的当前列表506。当在方框608中确定对于被处理的模型的当前时间间隔，自适应迭代求解器402B 已收敛到解时，在方框609中，操作可进入要处理的下一时间间隔，如图1的示例性工作流的外部循环102。并不是所有奇点总是以坏的方式影响线性系统。例如，如果建模的地下碳氢化合物储层的井关闭(shut in)，则对线性系统没有影响。在该示例性实施例中，自适应迭代求解器402B可通过针对小块模型并分析相应线性系统及其解来研究每个可能的奇点(物理限定的)。如果线性系统(如大条件数)或者是其解有某种异常行为，则奇点被选择以供提取(即，被加入到当前奇点的列表506中)。否则，可能的奇点不包括在当前时步的列表 506中(即，可从其中除去)。通常，仅检查模型406中是否有变化是足够的。例如，如果井正在生产，并且曾经常常引起线性系统的问题，则假定其将持续该行为。在一个实施例中，性能分析(如图4的方框403或图6的方框606)检查迭代求解器的行为以尝试改善自适应迭代求解器的迭代性能和/或CPU/Wall时钟性能。可通过加入忽略的奇点、发现新奇点和/或改善当前奇点的处理来改进迭代性能。在某些实施例中， 可以通过调整预处理器的操作改善CPU/Wall时钟性能。例如，如果迭代性能是好的，但预处理器计算成本高昂，则在某些实施例中，自适应迭代求解器可选择忽略某些奇点和/或放宽(relax)对某些奇点的处理。理想地，改善迭代性能应改善CPU/Wall时钟性能，但不总是这样。使预处理器非常昂贵，即“很好”，会导致少但非常昂贵的迭代。使用非常便宜但不高效的预处理器通常无法提供好的解。某些实施例用来实现折衷的方式是按重要性排序当前奇点并保持最重要的，即具有最高排序的奇点。一种可能的方式是为不同奇点提供权重，且权重越高，则排序越高。权重在模拟运行中更新，并且变化反应性能。忽略某些低级奇点通常不会不利地影响收敛，因为迭代方法会考虑这些奇点。有几种方法可用于分配权重给不同奇点。根据某些实施例可以采用的一种方法是基于奇点的类型分配静态权重。例如，垂直井可分配以权重1，倾斜井可分配以权重2，水平井可分配以权重3，等等。这些静态权重可基于之前运行(以某些静态工具处理)的结果分析和/或可基于某些理论假设的应用。根据某些实施例，可以使用的更复杂的方法是基于迭代求解器性能动态调整权重。例如，该方法在第一次运行中可以使用固定权重作为开始 (如第一次3D建模采用迭代求解器)，且在下一次运行时，可改变某些权重并且分析迭代求解器的相应性能。例如，该方法可以按如下权重分配求解线性方程系统一次，第一水平井权重为3，第二水平井权重为3。然后，可以以分配给第一水平井权重2和分配给第二水平井权重4求解线性方程系统。可比较第一和第二迭代方法的性能，并且该方法可基于确定的性能比较继续调整权重。例如，可以证明第一井不重要，且其可从当前奇点列表中去除。例如，通过采用仅考虑被分配最高权重的固定数目的奇点的方法，一旦该方法有效地降低其相对权重，则可从当前奇点列表中去除第一井。可使用各种不同算法提取奇点。不同的奇点可能要求不同的方法进行提取。可以使用的一个示例性算法考虑物理限定(bound)的奇点，如被物理限定的地下碳氢化合物储层中流体流量模型的部分中碰到的奇点。在一个实施例中，假定给定奇点中的流体行为和给定奇点周围的流体行为可以较为简单的模型近似，并且该较为简单的模型不会不利地影响线性系统。例如，复杂的井模型通常不利地影响预处理器的质量。简单的井模型表现得更好。如果复杂的井模型可以简单的井模型近似，则预期最终的预处理器会更好。有时，近似不能解决该问题，但“坏的”部分的维度显著减小。在一个实施例中，应用第二步，其涉及特定的小的排序更新过程。类似方法可用于地质奇点，如在被建模的地下碳氢化合物储层中碰到的裂缝。根据一个实施例，对于识别的物理限定的奇点，两个预处理器被考虑。最初，对于每个物理限定的奇点，选择子域，其包含该奇点及其周围的小的带。以下讨论在某些实施例中可用于构造用于这种奇点的预处理器的示例性的两步过程。也就是，在某些实施例中，下面说明的示例性两步方法用于构造预处理器(如图6的方框604)。首先，以适当的近似取代每个奇点(如，其可作为图6中方框604的部分执行)。 然后，构造全局预处理器(如其可作为图6中方框604的部分执行)，其中全局预处理器包括在奇点之外的原始问题和在奇点内确定的近似。在某些实施例中，可以通过全局预处理器和子域应用加法和乘法khwarz。可使用重叠或不重叠版。然后，评估给定奇点的近似的质量(如其可作为图6中方框606的部分执行)。例如，近似的质量可以使用包含该近似的本地块并检查线性系统进行评估，或者通过观察预处理器的收敛行为进行评估。也就是说，给定奇点可以被近似，且可对近似执行线性解。然后确定在使用近似时，收敛是否可接受。如果确定收敛不可接受，则以下讨论的替换的预处理器构造技术用于下一时步(如，在图6的示例性时步循环中的下一时间间隔609之后)。在该示例性实施例的可替换的预处理器构造技术中，当没有可用的好的近似或近似仍然不利地影响线性系统时，使用另一个预处理器。在一个实施例中，解被计算为两项的和。第一项是对“奇点空间”的正交投影，第二项是其补元。可针对“好的部分”使用任何预处理器，其包括前面步骤中的预处理器。给定奇点可视为包含在奇点空间中，其可包括可很好近似的某些特征/特性，并且也可以包括无法达到好的近似的某些其他特征/特性。根据某些实施例，奇点空间可分成能很好近似的部分(其可称为“好的”部分)和不能很好近似的部分(其可称为“坏的” 部分)。因此，在某些实施例中，自适应迭代求解器可操作用于从奇点空间提取“坏的”部分，从而得到可很好近似的好的剩余部分。给定奇点空间“X”可视为具有对应的维度(对应于描述奇点的子矩阵的大小)， 如维度“dim(X)”。求解器可首先尝试以具有减小维度的较为简单的模型近似/近似 (approximate)奇点，如在维度为“dim⑴”的空间“Y”中(其中dim(Y) < dim(X))0空间 “Y”是奇点空间“X”的一部分。可以保留没有良好近似的奇点的一部分。该部分在具有维度“dim(Z) ”的空间“Z”中，其中“dim(Z) = dim(X)-dim(Y) ”，即，在从奇点空间取出“Y”后留下的部分。在某些实施例中，奇点空间的空间“Y”中近似的部分被当作奇点空间的“好的”部分，可以用适当的预处理器对其进行处理，而奇点空间剩余的“Z”部分被称为奇点空间的“坏的”部分，可以以不同方式对其进行处理。因此，根据某些实施例，对于无法获得近似(如方框701中所确定的)或近似的质量被确定为不可接受(方框703中)的任何奇点， 自适应迭代求解器402尝试提取“坏的”部分。因此，当对于给定奇点无法获得适当近似时或者这种近似的质量不可接受时，在某些实施例中，求解器提取奇点的“坏的”部分，从而剩余的好的部分可通过可接受的近似来建模。作为例子，假定原始问题维度为1，000, 000，且存在维度100的奇点。进一步假定求解器尝试以具有维度如90的较为简单的模型近似该奇点。如果第一预处理器的性能被确定为可接受，则使用该预处理器。否则，如果第一预处理器的性能被确定为不可接受的， 则采用本文进一步讨论的第二步。因此，借助奇点近似，100个奇点模式中的一些奇点模式被抑制，例如90个奇点模式可能被近似抑制。10个剩余奇点模式称为仍需考虑的“坏的” 模式(或“坏的”部分)。不幸的是，我们不能明确知道哪些是“坏的”模式。在该例子中， “坏的”或奇点部分的维度为10，且“好的”部分的维度为1，000，000-10。进一步，在该例子中，去除“坏的”部分的迭代次数将与10成比例，如0(10)。一般地，我们仅使用第二算法， 但计算量取决于“坏的”模式的数目，并且首先近似并减少未解析模式的数目在计算上更有效。因此，可通过辨认被识别奇点空间的“好的”和“坏的”部分和适当地处理每个好的和坏的部分来实现性能的改善，如下面进一步讨论。因此根据某些实施例，响应于识别奇点，自适应迭代求解器可操作用于确定是否有奇点的可接受的近似可用。如果有好的近似可用，则用于近似的相应预处理器用于迭代求解奇点。当确定没有可接受的近似可用(即，要么没有可用的好的近似或近似被确定为还不利地影响线性系统)，则迭代求解器提取奇点的坏的部分从而得到有好的近似可用的奇点的剩余的好的部分。然后，用于奇点的好的部分的适当预处理器用于迭代地求解奇点好的部分。在某些实施例中，可以以不同方式处理提取的奇点坏的部分。对奇点坏的部分的处理在计算上的效率比好的部分的处理在计算过上的效率低，但由于从奇点提取“坏的” 部分，使计算总体上得到改善，因而使得“好的”部分能够以计算有效的方式被迭代求解。现在，考虑难于物理分离的奇点群，但是它们可以某些其他方式分离。例如，如果预处理的系统仅有几个分离的特征值，则可使用紧缩(deflation)。关于紧缩的更多信息， 请参见R. Nabben禾口 C. Vuik 的"A Comparison of deflation and Coarse grid correction applied to porous media flows", SIAM H. Numer. Anal. , v. 42,1631-1647 ；以及 J.Frank 禾口 C. Vuik 的"On the construction of deflation-based preconditioners", SIAM J. ki.Comput.，v. 23,442-462。一般地，更难于检查这类奇点的存在。在某些实施例中，其存在是从预处理器的迭代行为推导来的。因此，参考图7进一步说明根据自适应迭代求解器402的一个实施例构造预处理器的示例性工作流(如，图6的方框604中)。在方框71中，自适应迭代求解器402将当前奇点分为两组a)物理限定的，和b)特征值限定的。在一个实施例中，特征值限定的奇点更为通用并且包括物理限定的奇点。物理限定的奇点的算法通常更易于实施，且通常更为有效。如果仅几个特征值没有被抑制，则紧缩算法可能是有帮助的，但其更难于实施且计算成本高。会导致问题的物理特征(非受抑制的特征值)的示例是被建模的地下碳氢化合物储层的多孔介质中具有完全不同属性的层。这类问题可由建模的用户识别，或者对于非常复杂的模型，可由模式识别算法识别。对于这类简化情形，存在有效的紧缩算法。在方框72，自适应迭代求解器402尝试针对物理限定的奇点构造预处理器。对于物理限定的奇点，在方框701中，自适应迭代求解器402为每个物理限定的奇点确定奇点的近似是否可用。对于近似可用的奇点，在方框702中这些近似(多个)被用于近似奇点。 在方框703中，自适应迭代求解器402评估近似的质量(如，确定收敛是否可接受，如上所述)。对于在方框703中，其质量被确定为可接受的每个奇点，这类奇点的近似被用于构造预处理器，如方框704所示。对于近似不可用(如方框701中确定的那样)或对于近似质量被确定为不可接受(方框703中)的任何奇点，在方框73中，自适应迭代求解器402尝试提取“坏的”部分 (如使用下文进一步讨论的第二算法)。传统上，迭代求解器并不使用构造预处理器的自适应方法，如图7中的示例性方法。而是，传统迭代求解器可预先配置从而利用奇点近似或使用紧缩来构造预处理器，但传统迭代求解器一直不是自适应的从而不可能使用这两种构造技术中的一种或两种，如图7 的示例性方法所使用的。针对传统迭代求解器实施的预先配置的方法通常无法提供所需的计算性能，且如这里所述的自适应迭代求解器的某些实施例可自适应其方法以构造预处理器(如在图7的上述示例中所讨论的)，以便改善计算性能。根据一个实施例，给定矩阵A的迭代方法的收敛是通过特征值的分布确定的(至少对于对称矩阵)。假定特征值在数字a = 1和b = 1，000, 000之间。则迭代求解器中的迭代次数应与(b/a)的平方根 1000成比例。为了改善收敛，在某些实施例中，预处理器是作为B-IA引入的，其可减少特征值的数目。例如，继续上面的例子，B4A的特征值可在c =1和d = 100之间。然后，处理预处理器的迭代求解器的迭代次数与(d/c)的平方根成比例。一般地，MultiGrid和域分解算法“移动”特征值到谱的左手侧并改善迭代求解器的收敛。然而，如果存在奇点，则其特征值不动(即，不会移动到方程的左手侧)。根据本发明的某些实施例，可以使用算法“移动”未改动的特征值。本文提及的紧缩算法也可在某些实例中用于“移动”特征值到左侧，但它们需要具有特征向量的近似，这并不常用。为此，某些实施例中，紧缩算法通常视为处在最后的解决方案。在某些很好研究的情形中，如具有显著不同特性的多孔介质层，这可以有效地实现。现在简单地讨论可根据某些实施例构造的示例性预处理器。也就是，下面进一步讨论可根据某些实施例用于构造预处理器的示例性算法。当然，本发明的实施例不限于使用下述示例性预处理器构造算法。首先讨论可用于基于一个或多于一个奇点的近似构造预处理器的算法。因此，该示例性算法可在图7的方框72中采用。考虑矩阵
A10
A =為2為3，其中块^3对应于复数个奇点，^2是这些奇点周围的带，_ 0為2
而A11为剩余部分。假定我们可以另一个矩阵為3近似A33。则交迭相加(overlapping additive)形式的第一预处理器为
权利要求
1.一种方法，其包括通过自适应迭代求解器识别存在于线性方程系统中的至少一个奇点； 通过所述自适应迭代求解器构造第一预处理器以用于求解所述线性方程系统； 通过所述自适应迭代求解器确定所述第一预处理器的计算性能是否可以接受；以及当确定所述第一预处理器的计算性能不可接受时，通过所述自适应迭代求解器构造可替代的预处理器来求解所述线性方程系统。
2.根据权利要求1所述的方法，其中所述可替代的预处理器抑制被识别的至少一个奇点的被确定的坏的部分，从而导致被识别的至少一个奇点的剩余的好的部分的计算性能可以接受。
3.根据权利要求2所述的方法，其中所述可替代的预处理器包括所述第一预处理器， 其用于迭代求解所述被识别的至少一个奇点的剩余的好的部分。
4.根据权利要求1所述的方法，其中所述识别包括识别多个奇点，且其中所述第一预处理器用于提取所述多个奇点中的一些，用于求解所述线性方程系统，且其中所述可替代的预处理器用于提取所述多个奇点的剩余部分，用于求解所述线性方程系统。
5.根据权利要求4所述的方法，进一步包括采用紧缩算法提取所述多个奇点的进一步剩余部分以求解所述线性方程系统。
6.根据权利要求4所述的方法，进一步包括由所述自适应迭代求解器确定近似对于所述多个奇点中的至少某些奇点是可接受地有效的；并且其中构造所述第一预处理器包括根据所述近似构造所述第一预处理器。
7.根据权利要求6所述的方法，进一步包括由所述自适应迭代求解器确定近似对于所述多个奇点中的至少第二部分是不可接受地有效的。
8.根据权利要求6所述的方法，其中构造所述可替代的预处理器包括使用紧缩构造所述可替代的预处理器以用于提取所述多个奇点的所述至少第二部分。
9.一种方法，其包括通过自适应迭代求解器识别线性方程系统中存在的奇点； 通过所述自适应迭代求解器确定是否可接受近似可用于被识别的奇点； 当确定没有可接受的近似可用于所述被识别的奇点时，通过所述自适应迭代求解器提取所述被识别的奇点的坏的部分从而产生所述奇点的剩余好的部分，对于所述剩余好的部分，可接受的近似是可用的；以及通过自适应迭代求解器迭代求解所述奇点的剩余的好的部分的近似。
10.根据权利要求9所述的方法，其中所述确定是否可接受近似可用于被识别的奇点包括通过所述自适应迭代求解器构造用于求解所述线性方程系统的第一预处理器；以及通过所述自适应迭代求解器确定所述第一预处理器的计算性能是否可接受。
11.根据权利要求10所述的方法，进一步包括当确定所述第一预处理器的计算性能不可接受时，通过所述自适应迭代求解器构造可替代的预处理器用于求解所述奇点的所述剩余的好的部分。
12.根据权利要求11所述的方法，其中所述可替代的预处理器包括所述第一预处理器。
13.根据权利要求9所述的方法，进一步包-·-括通过所述自适应迭代求解器求解所述被识别的奇点的被提取的坏的部分。
14.存储在计算机可读介质中的计算机可执行软件代码，当其由计算机执行时使得所述计算机执行一种方法，所述方法包括识别存在于线性方程系统中的至少一个奇点； 确定所述至少一个奇点的近似；基于所确定的近似构造第一预处理器以由迭代求解器用于求解所述线性方程系统； 确定所述预处理器的计算性能是否可接受；当确定所述预处理器的计算性能不可接受时，构造可替代的预处理器以由所述迭代求解器用于求解所述线性方程系统。
15.根据权利要求14所述的计算机可执行软件代码，其中所述可替代的预处理器不基于所述确定的近似。
16.根据权利要求14所述的计算机可执行软件代码，其中所述可替代的预处理器是使用紧缩构造的。
17.根据权利要求14所述的计算机可执行软件代码，其中确定所述至少一个奇点的近似包括确定近似是否可用于所述至少一个奇点；以及其中当确定所述近似不可用于所述至少一个奇点时，则构造所述可替代的预处理器以由所述迭代求解器用于求解所述线性方程系统。
18.根据权利要求14所述的计算机可执行软件代码，其中所述方法进一步包括 其中所述识别包括识别多个奇点；以及其中所述确定近似包括确定所述多个奇点的至少第一个奇点的近似。
19.根据权利要求18所述的计算机可执行软件代码，其中所述方法进一步包括由所述迭代求解器使用所述第一预处理器提取所述多个奇点中所述至少第一个奇点， 以求解所述线性方程系统。
20.根据权利要求19所述的计算机可执行软件代码，其中所述方法进一步包括 由所述迭代求解器使用所述可替代的预处理器提取所述多个奇点中的至少第二个奇点，以求解所述线性方程系统。
21.根据权利要求20所述的计算机可执行软件代码，其中所述方法进一步包括 确定近似不可用于所述多个奇点中的所述至少第二个奇点。
22.根据权利要求14所述的计算机可执行软件代码，其中所述方法进一步包括 其中所述识别包括识别存在于所述线性方程系统中的多个奇点；为所述多个奇点的每个确定相应的近似是否是可接受有效的；以及对于所述多个奇点中相应的近似是可接受有效的每个奇点，使用所述相应的近似构造所述第一预处理器以便由所述迭代求解器用于提其取相应的近似可用的所述奇点。
23.根据权利要求22所述的计算机可执行软件代码，其中所述方法进一步包括 构造所述可替代的预处理器以便由所述迭代求解器用于提取所述多个奇点中相应的近似被确定为不可用的每个奇点。
24.一种方法，其包括由自适应迭代求解器识别存在于线性方程系统中的多个奇点； 由所述自适应迭代求解器构造第一预处理器，用于提取所述奇点的第一部分以求解所述线性方程系统，其中所述第一预处理器基于所述多个奇点的至少一个的近似；由所述自适应迭代求解器构造第二预处理器，用于提取所述奇点的第二部分以求解所述线性方程系统，其中所述第二预处理器不是基于所述多个奇点的至少一个奇点的近似； 以及由所述自适应迭代求解器处理所述第一预处理器和所述第二预处理器以求解所述线性方程系统。
25.根据权利要求M所述的方法，其中所述第二预处理器是通过将解分解为坏的部分和剩余好的部分而构造的。
26.根据权利要求25所述的方法，进一步包括 使用紧缩算法求解所述线性方程系统的至少一部分。
27.一种方法，其包括通过用于求解线性方程系统的迭代求解器处理接收的模型； 通过所述迭代求解器识别至少一个奇点；基于观察的所述迭代求解器在求解所述线性方程系统中的性能，通过所述迭代求解器确定是否排除所识别的至少一个奇点的一个或多于一个；以及当确定要排除所述识别的至少一个奇点的一个或多于一个时，所述迭代求解器自适应以排除所确定的所述识别的至少一个奇点的一个或多于一个。
28.根据权利要求27所述的方法，其中所述自适应包括构造预处理器以排除所述确定的所述识别的至少一个奇点的一个或多于一个。
29.根据权利要求27所述的方法，其中所述确定包括基于所观察的性能，所述迭代求解器自动确定是否排除所述识别的至少一个奇点的所述一个或多于一个。
30.一种方法，其包括由用于求解线性方程系统的迭代求解器处理接收的模型，所述迭代求解器具有收敛于解所要求的预定的预期数目的迭代；所述迭代求解器识别至少一个奇点；以及所述迭代求解器确定所识别的至少一个奇点是否导致所述收敛要求的迭代数目增加超过预定的预期迭代数目。
31.根据权利要求30所述的方法，进一步包括当确定所述至少一个奇点导致所述收敛要求的迭代数目超过预定的预期迭代数目时， 所述迭代求解器自适应排除所述识别的至少一个奇点。
32.根据权利要求31所述的方法，进一步包括 加权所述识别的至少一个奇点；以及至少部分基于所述加权确定是否自适应以排除所识别的至少一个奇点。
33.根据权利要求30所述的方法，进一步包括所述迭代求解器确定是否自适应处理所述线性方程系统以排除所述识别的至少一个奇点O
34.根据权利要求33所述的方法，进一步包括确定与排除所述识别的至少一个奇点关联的计算成本；以及其中所述确定是否自适应包括平衡所确定的计算成本和确定的所述收敛要求的迭代次数的增加。
35.根据权利要求30所述的方法，进一步包括至少部分基于所述迭代求解器在收敛于解的计算性能，所述迭代求解器自动自适应其处理以选择性排除所述识别的至少一个奇点的一个或多于一个。
36.一种方法，其包括由自适应迭代求解器识别存在于线性方程系统中的可能奇点，所述自适应迭代求解器可操作用于采用迭代方法求解所述线性方程系统；由所述自适应迭代求解器分析求解所述线性方程系统的计算性能；以及基于其计算性能，所述自适应迭代求解器自适应处理提供所需性能的所述可能奇点。
37.根据权利要求36所述的方法，其中所述自适应处理所述可能奇点包括 构造预处理器用于排除所述可能奇点中选择的奇点。
全文摘要
本发明提供了一种自适应迭代求解器，其采用自适应处理提取奇点以求解线性方程系统。自适应迭代求解器动态确定如何在线性方程系统中存在一个或多于一个奇点时调整其性能。在某些实施例中，自适应迭代求解器可识别可能的奇点，且然后分析其性能以调整对可能奇点的处理，以提供理想的性能(即，为实现对解的收敛)。因此，不是被预先配置以提供对某些被识别的奇点的某种处理(如消除)，在某些实施例中，迭起求解器基于其计算性能调整其对奇点的处理。
文档编号G06F7/60GK102165413SQ200980138527
公开日2011年8月24日 申请日期2009年7月17日 优先权日2008年9月30日
发明者A·马特索金, I·米谢夫, S·涅波姆亚什 申请人:埃克森美孚上游研究公司
最新回复(0)