利用代数串联级线性解算器改进储层模拟的装置、方法和系统

摘要

本发明公开了一种使用关注区域的储层模型进行储层模拟的方法、系统、程序存储设备和装置，其中该关注区域已网格化为单元。每个单元具有一个或多个未知变量。每个单元具有结点。结点图由稀疏矩阵表示。该图被初始分解为预指定数目的区域，使得每个单元处于至少一个区域内。单元和区域是已经编号的。每个单元具有关键字，每个单元的关键字为该单元所属的该组区域数。每个单元具有级，每个单元的级为在该单元内的元素数目。单元分组为连接器，每个连接器为共享相同关键字的单元组。每个连接器具有连接器级，连接器级为该连接器的关键字内的元素数目。每个仅具有一个高阶相邻连接器的连接器与这样的高阶相邻连接器合并。所有的局部最大级连接器的级重置为由任一连接器保持的最大级。该最大级连接器仅包含一个单元。连接器以增加的级次序排序。内插算子和限定算子由排序的连接器来构造。该内插算子和限定算子用来构造粗网格。该粗网格可用来确定单元的未知变量。

说明书

相关申请

本申请要求于2005年6月14日提交的美国临时专利申请60/690,319的优先权。

技术领域

本发明涉及用于储层模拟的装置、方法和系统。特别地，本发明提供了利用代数串联级线性解算器进行更有效并高效地模拟流体在储层中流动的装置、方法和系统。

背景技术

储层模拟通常要求描述在储层中的天然多孔介质中控制多组分、多相流体流动的复杂性状的物理学方程式的数值解。典型地常用于描述该流体流动的控制方程基于热动力平衡以及质量、动量和能量守恒定理，如在Aziz和Settari，1977中所描述的。控制储层流体流动的物理学的复杂性引出不受制于传统分析方法的耦合非线性偏微分方程体系。因此，数值解方法是必需的。

各种数学模型、公式化、离散化方法以及解法方案已经得到发展，并与强加在储层中的关注区域上的网格有关。储层模拟问题的详细讨论以及处理这样问题的方程式是可以得到的，例如，在此处引入作为参考的ExxonMobil的国际公开号为No.WO 01/40937的PCT公开专利申请，以及在此处引入作为参考的美国专利号为No.6,662,146 B1的美国专利。如果使用强加在储层中的关注区域上的网格，该网格可以是结构化的或非结构化的。这样的网格由单元构成，每个单元具有一个或多个未知特性，但是网格中的所有单元都具有压力作为未知量。其它未知特性包括但不限于流体特性，比如含水饱和度或温度，或不限于“岩石特性”，比如渗透率或孔隙率，这里仅举几个例子。被认为如果其仅具有一个未知量(一般为压力)的单元在此处被称为“单变量单元”，而当单元具有一个以上的未知量时，在此处被称为“多变量单元”。

矩阵可以构造为表示基于不同级型单元的网格化的关注区域。

以下方程式用来求解称为x的未知变量：

Ax＝b    (方程式1)

其中x为表示单元的未知特性的变量的块向量，以及b为已知量的块向量。块向量x以及块向量b为同样的长度。求解该问题的方法包括：区域多扇形分解法(Cleve Ashcraft)，Wirebasket区域分解法(BarrySmith)，层次界面分解法(Heirarchical interface decomposition)(Henon和Saad)，以及GMRES(Saad和Shultz)。但该问题通过本发明具体地处理，包括求解与既用于结构化又用于非结构化网格的大型的不同种级的问题有关的线性体系。该解法必须是鲁棒的(robust)，在计算方面高效而具有极好的收敛速度。焦点集中在开发可升级的(即对于大问题也有效的)多级代数方法，其完全依赖于一定可求解的线性方程组中的数据。此外，该解法要非常适合用于并行计算也是必要的。这些要求提出了巨大的挑战，尤其对于差异很大的非结构化的网格问题以及现有方法，包括不完全上-下(ILU)因式分解法和嵌套因式分解法，其与满足所有这些基本要求仍落后一大段距离。

发明内容

考虑到上述问题，本发明的目的在于提供用于更有效地和高效地模拟流体在储层中流动的方法、装置和系统，同时将所述问题和局限性的影响消除或减到最小。

同时，在这里的一些说明集中在处理控制通用的储层模拟问题中的压力的线性方程组上，本发明同样适用于AIM(自适应隐式方法)和完全隐式线性体系。

本发明包括借助于储层的关注区域的储层模型来进行储层模拟的方法。该关注区域已经网格化为多个单元，每个单元具有一个或多个未知变量，并且每个单元具有结点。该方法的步骤包括建立单元结点图；强制该图初始分解成预指定数目的区域，使得每个单元处于至少一个区域内；给单元和区域编号，每个单元具有关键字(key)，并且每个单元具有级(class)，其中每个单元的关键字为该单元所属的该组区域数，且每个单元的级为该单元的关键字内的元素数目；将单元分组为连接器，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；执行连接器减少步骤；重置所有局部最大级连接器的级到由任一连接器所保持的最大级；迫使最大级连接器仅包含一个单元；以增加的级次序排序连接器；由排序的连接器构造内插算子和限定算子；和使用该内插算子和限定算子构造粗网格。该粗网格可用来求出单元的未知变量。该模拟的结果可用来确定改善储层产量的机会。这些机会的一个或多个可在改善储层产量上发挥作用。网格可以为结构化或非结构化的。所述图可以为二维或三维的。该模拟是可以显示的。连接器减少步骤可以包括将每个仅具有一个高阶相邻连接器的连接器与这样的高阶相邻连接器合并。稀疏矩阵可用于表示该图，稀疏矩阵采取的形式为$A={\left\{a_{\mathrm{ij}}\right\}}_{i,j=1}^n,$其中n为单元的数目。

本发明包括机器可读取的程序存储设备，明确包含可由机器执行的指令程序，以执行使用其中关注区域已经网格化为多个单元的储层模型进行储层模拟的方法步骤。每个单元具有一个或多个未知变量，并且每个单元具有结点。该方法步骤可以包括建立单元结点图；强制该图初始分解成预指定数目的区域，使得每个单元处于至少一个区域内；给单元和区域编号，每个单元具有关键字，并且每个单元具有级，其中每个单元的关键字为该单元所属的该组区域数，且每个单元的级为该单元的关键字内的元素数目；将单元分组为连接器，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；执行连接器减少步骤；重置所有局部最大级连接器的级到由任一连接器所保持的最大级；迫使最大级连接器仅包含一个单元；以增加的级次序排序连接器；由排序的连接器构造内插算子和限定算子；和使用该内插算子和限定算子来构造粗网格。程序存储设备的方法步骤可以进一步包括使用粗网格求出单元的未知变量。该程序存储设备可用于油气储层(hydrocarbonreservoir)，程序存储设备的方法步骤还可以包括使用模拟的结果来确定改善储层产量的机会。网格可以为结构化或非结构化的。所述图可以为二维的。所述图可以为三维的。程序存储设备的方法步骤可进一步包括显示该模拟。该模拟可显示在多种显示装置上，例如计算机监视器或三维显示器装置。连接器减少步骤可以包括将每个仅具有一个高阶相邻连接器的连接器与这样的高阶相邻连接器合并。稀疏矩阵可用于表示该图，该稀疏矩阵采取的形式为：$A={\left\{a_{\mathrm{ij}}\right\}}_{i,j=1}^n,$其中n为单元的数目。该程序存储设备可包含致密盘。该程序存储设备可包含在计算机硬盘驱动器上的存储器。

本发明包括对输入数据进行响应的模拟装置，其适合于求解表示特定实体的线性方程组，当所述线性方程组解出时，所述模拟装置生成一组模拟结果，该组模拟结果包括表征所述特定实体的一个或多个参数。该实体的表示已经网格化为多个单元，每个单元具有一个或多个未知变量，并且每个单元具有结点。该模拟装置包括用于用图表示单元结点的装置；用于强制该图初始分解成预指定数目的区域，使得每个单元处于至少一个区域内的装置；用于给单元和区域编号的第二装置；用于给每个单元分配关键字使得每个单元的关键字为该单元所属的该组区域数的分配装置；用于给每个单元分配级的第二分配装置，每个单元的级为该单元的关键字内的元素数目；用于将单元分组为连接器的分组装置，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；连接器减少装置；用于重置所有局部最大级连接器的级到由任一连接器所保持的最大级的重置装置；用于迫使最大级连接器仅包含一个单元的限制装置；用于以增加的级次序排序连接器的排序装置；用于由排序的连接器构造内插算子和限定算子的装置；和使用该内插算子和限定算子构造粗网格的第二构造装置。该模拟装置还可以包括使用粗网格来求出单元的未知变量的确定装置。如果特定实体为油气储层，那么该模拟装置还可以包括使用根据该模拟装置产生的结果来确定改善储层产量的机会的装置。如果该特定实体为产水储层，那么该模拟装置还可以包括使用根据该模拟装置产生的结果来确定改善储层产量或禁止储层的盐水侵蚀的机会的装置。网格可以为结构化或非结构化的。所述图可以为二维的。所述图可以为三维的。模拟装置还可以包括用于显示该模拟的显示装置。该显示装置可包括计算机监视器。该显示装置可包括三维显示器装置。连接器减少装置可以包括确定每个仅具有一个高阶相邻连接器的连接器，并将每个这样的连接器与它的高阶相邻连接器合并。稀疏矩阵可用来表示该图，该稀疏矩阵采取的形式为：$A={\left\{a_{\mathrm{ij}}\right\}}_{i,j=1}^n,$其中n为单元的数目。

本发明包括对一组输入数据进行响应的装置，其用于显示土层(earth formation)的网格表示。该网格表示由多个网格单元和分别与该多个单元有关的多个模拟结果构成。每个单元具有一个或多个未知变量，且每个单元具有结点。该模拟装置包括建立单元结点图的装置；用于强制该图初始分解成预指定数目的区域，使得每个单元处于至少一个区域内的装置；用于给单元和区域编号的第二装置；用于给每个单元分配关键字使得每个单元的关键字为该单元所属的该组区域数的分配装置；用于给每个单元分配级的第二分配装置，每个单元的级为该单元的关键字内的元素数目；将单元分组为连接器的分组装置，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；连接器减少装置；用于重置所有局部最大级连接器的级到由任一连接器所保持的最大级的重置装置；迫使最大级连接器仅包含一个单元的限制装置；以增加的级次序排序连接器的排序装置；由排序的连接器构造内插算子和限定算子的装置；和使用该内插算子和限定算子构造粗网格的第二构造装置。该模拟装置还可以包括使用粗网格求出单元的未知变量的确定装置。该装置还可以包括使用该模拟的结果以便确定由土层形成改善产量的机会的装置。网格可以为结构化或非结构化的。所述图可以为二维的。所述图可以包括三维。模拟装置可包括用于显示该模拟的显示器。该显示器可为多种物件，包括但不限于计算机监视器或三维显示系统。连接器减少装置可以包括将每个仅具有一个高阶相邻连接器的连接器与这样的高阶相邻连接器合并。稀疏矩阵可用来表示该图，该稀疏矩阵采取的形式为：$A={\left\{a_{\mathrm{ij}}\right\}}_{i,j=1}^n,$其中n为单元的数目。

本发明包括借助于关注区的储层模型进行储层模拟的方法，关注区已经网格化成为多个单元。每个单元具有一个或多个未知变量。该方法的步骤包括强制网格初始分解成预指定数目的区域，使得每个单元处于至少一个区域内；给单元和区域编号，每个单元具有关键字，并且每个单元具有级，其中每个单元的关键字为该单元所属的该组区域数，且每个单元的级为该单元的关键字内的元素数目；将单元分组为连接器，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；执行连接器减少步骤；重置所有局部最大级连接器的级到由任一连接器所保持的最大级；迫使最大级连接器仅包含一个单元；以增加的级次序排序连接器；由排序的连接器构造内插算子和限定算子；和使用该内插算子和限定算子构造粗网格。该模拟方法还可以包括使用粗网格求出单元的未知变量的确定装置。网格可以为结构化或非结构化的。所述图可以为二维或二维以上的。该方法可包括显示该模拟。连接器减少装置可以包括将每个仅具有一个高阶相邻连接器的连接器与这样的高阶相邻连接器合并。

本发明包括机器可读取的程序存储设备，明确包含可由机器执行的指令程序，以执行使用其中关注区域已经网格化为多个单元的储层模型进行储层模拟的方法步骤。每个单元具有一个或多个未知变量。所述方法步骤可以包括强制网格初始分解成预指定数目的区域，使得每个单元处于至少一个区域内；给单元和区域编号，每个单元具有关键字，并且每个单元具有级，其中每个单元的关键字为该单元所属的该组区域数，且每个单元的级为该单元的关键字内的元素数目；将单元分组为连接器，每个连接器为共享同样的关键字的单元组，以及每个连接器具有连接器级，连接器级为每个连接器的关键字内的元素数目；执行连接器减少步骤；重置所有局部最大级连接器的级到由任一连接器所保持的最大级；迫使最大级连接器仅包含一个单元；以增加的级次序排序连接器；由排序的连接器构造内插算子和限定算子；和使用该内插算子和限定算子来构造粗网格；和使用该粗网格求出单元的未知变量。

参考附图、下述说明和权利要求，本发明的其它的目的、特征和优点将对本领域技术人员变得明显。

附图说明

图1a举例说明了储层的表示。

图1b举例说明了图1a中描绘的储层中一部分的展开图。

图2为本发明的优选实施例的流程图。

图3示出了储层内关注区域的简化三维图，依照本发明的优选实施例进行了网格化。

图4示出了储层(在图4中未单独示出)内的关注区域25的二维图，依照本发明的优选实施例被细网格化。

图5示出了储层内的关注区域的简化二维图，依照本发明的优选实施例该关注区域已经网格化为单元。

图6示出了依照本发明的优选实施例的一组连接器的简化二维图，

图7示出了依照本发明的优选实施例的ACC排序。

图8示出了依照本发明的优选实施例的多线性基函数。

图9示出了依照本发明的优选实施例的具有900个结点(各向同性的情况)的三角形划分的有限元。

图10示出了依照本发明的优选实施例的在矩阵结构上的ACC排序。

图11示出了依照本发明的优选实施例的具有900个结点(各向异性的情况)的三角形划分的有限元。

图12示出了依照本发明的优选实施例执行图2中某些步骤的结果，参照图6所示的连接器。

图13示出了依照本发明的优选实施例的图2中的详细步骤152的流程图。

图14示出了依照本发明的优选实施例，粗网格矩阵的曲线图的实施例。

具体实施方式

在下文中，参照附图，详细说明本发明的优选实施例及其他实施例。应理解的是，本领域技术人员将容易明白在不脱离本发明的范围的情况下可以进行其他实施例和变化。

图1a举例说明了储层10的表示，其具有部分12，其在图1b的分解(二维的)图中示出。储层10(低于地下水位)典型地包含流体20，比如石油、气体、水或在形成储层岩石的多孔介质22(比如，砂岩或石灰岩)之间填充孔隙空间的那些物质中的两个或三个的混合物。

图2示出了本发明的优选实施例的流程图。在开始步骤100之后，第一步为将关注区域网格化110成单元，每个单元在它的中心具有结点。通过稀疏矩阵表示120单元结点图：

$A={\left\{a_{\mathrm{ij}}\right\}}_{i,j=1}^n$(方程式2)

其中n为单元的总数。图2在这里进行进一步论述。

图3示出了储层(在图3中未单独示出)内的关注区域25的三维图，其依照本发明的优选实施例被细网格化。网格30将关注区域25划分为单元35，每个单元35在它的中心具有结点40(仅在图3中示出)。虽然图3中示出了结构化网格，但本发明的网格可以是结构化的或非结构化的。给定网格，则描述物理学的方程式在此网格上进行离散(有多种不同的可用的离散化方案)。其结果可表示为图表(即结点和边缘)。该“图”为完全的然而十分普遍的表示，如果不考虑底层网格(例如，结构化或非结构化的)的特性则是有效的，或是在该网格上离散化方程式的方法。

图4示出了储层(在图4中未单独示出)内的关注区域25的二维图，其依照本发明的优选实施例被细网格化。正如图3的情况那样，网格30将关注区域25划分为单元35。图4中的密网格30为49×49。图4中每个单元35的中心为结点40，但这些结点在图4中没有单独示出。

每个结点40为单元的数学中心。可在结点图内连接单元的各结点。

图5用储层内的关注区域25的简化二维图示出了本发明的优选实施例，关注区域25已经网格化为单元，比如单元45，每个单元45在它的中心具有结点。依照本发明的优选实施例的结点图50、55(其通过单元结点具有图形线)划分为网格。图5中的网格包括8×8的粗分结点图50，叠加于49×49的细分结点图55之上。这会产生81个区域60，其在8×8的结点图的线上具有重叠65。图5还示出了结点图的交点63，边缘65和顶点，比如顶点70。三维实施例还包括面，在图5中未示出。

在图5中所示的重叠65将区域彼此分开，也被称为多部分(multisector)。将区域加到其多部分，得出重叠区域，

重新参照图2，强制130该图初始分解成预指定数目的重叠区域，使得每个单元处于至少一个重叠区域内。在图5中，该预指定数目的区域可为八十一(81)个重叠区域60。图2中的下一步为给单元和重叠区域编号140。每个单元具有关键字，其为单元所属的一组区域数目。每个单元具有级；每个单元的级为在它的关键字内的元素数目(区域数目)。例如，各个单元在结点图的(仅仅)交点63处具有结点(这样的结点由图5中的虚线(dot)表示)，比如单元45，每个仅在一个区域中，具有一个级。在边缘65上具有它们的结点(这样的结点在图5中用圆圈表示)的单元在具有两个级的两个重叠区域内，而在图结点(这样的图结点在图5中用三角形表示)处在顶点70处的单元在具有四个级的四个重叠区域内。

再次参考图2，下一步为将单元分组150成连接器，每个连接器具有级，并且每个连接器为共享同样的关键字的单元组。每个连接器的级为该连接器的关键字内的元素数目。级n的连接器将因此分为级n-1或更低。

图6示出了依照本发明的优选实施例的一组连接器200、210、220、230、240、250、260、270、280的简化二维图，每个连接器为相同的关键字的单元组。在图6中，连接器200为具有关键字[1](即，连接器200包括仅在重叠区域1中的单元)的单元组，连接器210为具有关键字[2](即连接器210包括仅在重叠区域1中的单元)的单元组，连接器220为具有关键字[3]的单元组，连接器230为具有关键字[4]的单元组，连接器240(呈粗的垂直的条纹状的单元)为具有关键字[1，2](即连接器240包括在重叠区域1和重叠区域2内的单元)的单元组，连接器250(呈粗的水平的条纹状的单元)为具有关键字[2，3]的单元组，连接器260(呈垂直的条纹状的单元)为具有关键字[3，4]的单元组，连接器270(呈水平的条纹状的单元)为具有关键字[4，1]的单元组，和连接器280为在具有关键字[1，2，3，4]的顶点处具有单个单元(呈点状)的组。连接器200、210、220和230在级1中，并且没有示出构成这些连接器的各个单元。连接器240、250、260和270在级2中，并且分开级1的连接器，其为连接器240、250、260和270的近邻。连接器280在级4中，并且分开级1和2的连接器。连接器280为最大级的连接器，其在图6的实例中为级4。

单元间的关系可用数学式表示。由D_i i＝1，...，m表示组的集合。每个组包含相应于网格(或结点图)的区域或区的单元(或结点)数目。这些区域可采用先前提及的多种众所周知的方法被重叠或不重叠，并且所有的m区域的并集为整个网络(或结点图)。对每一单元i，i＝1，...，n，由K_i表示包含单元i的所有区域组。K_i被称为单元i的关键字。由V表示组，并且由|V|表示在组V中的元素数目。单元i的级c_i表示包含单元i的区域数目：

c_i＝|K_i|                    (方程式3)

定义L_j j＝1，...，q为级j的单元组：

L_j＝{i|c_i＝j}               (方程式4)

由q表示最大级(其在图6的实例中为4)：

$q=\underset{i=1,...,n}{\max }\left(c_i\right)$(方程式5)

由N_i表示单元i的相邻单元组：

N_i＝{j|a_ij≠0且j≠i}        (方程式6)

单元i的近邻可被称为n_i，r，r＝1，...，|N_i|。让$E=\underset{i=1}{\overset{n}{\cup }}\left\{K_i\right\}$作为唯一关键字的组。E为由v个唯一关键字构成的组：

E＝{E₁，E₂，...，E_v}        (方程式7)

从而|E₁|≤|E₂|≤...≤|E_v|。

连接器组B_i，i＝1...，v是这样的：

B_i＝{x|K_x＝E_i}              (方程式8)

记得连接器为具有同样的关键字的所有的单元组以及连接器的级为它的关键字内的区域数目。每个连接器B_i，i＝1，...，v的级κ_i定义为：

κ_i＝|E_i|                   (方程式9)

再次参考图2，通过执行连接器减少步骤152开始ACC(代数串联级)分解。步骤152可检验出在这里由B_i表示的任一连接器是否仅具有一个高阶相邻连接器(“高阶近邻”在这里由B_j表示)，也就是说，相邻连接器具有比连接器B_i的级更高的级。图13示出了图2中的步骤152的执行过程。N_i表示连接器i，i＝1，...，v的相邻连接器的组数。Q_l表示级l的该组连接器数目。符号h为连接器具有的高阶近邻的数目。以级1连接器开始，逐级进行到级q连接器。为了这样做，设定500l等于1。设定505W等于Q_l且j＝1。设定510 i＝W_j，其中h＝0且r＝1。设定515 t＝n_i，r。确定520是否κ_t＞l，并且如果是，则设定525 h＝1并且s＝t。设定530 r＝r+1。确定535是否r≤|N_i|，并且如果是，则转到步骤515。如果不是，则通过确定540是否h＝1，合并任何正好具有一个更高级相邻连接器B_j的连接器B_i到该更高级连接器B_j中，并且如果是，则设定545：

k＝κ_s

Q_l＝Q_l-{i}

B_s＝B_s∪B_i。

然后设定550j＝j+1。确定560是否j≤|W|，然后转到步骤510。否则，设定565l＝l+1。确定570是否l≤q，并且如果是，则转到步骤505。否则，结束(并且进行到图2的步骤160)。

局部最大级连接器定义为其级大于其每一个相邻连接器的级的连接器。再次参考图2，在ACC分解的下一步为重置165所有局部最大级连接器B_j的级κ_j为q，其为任何连接器的最大级。

${\kappa }_j=\underset{i=1,...,v}{\max \left|E_i\right|}$(方程式10)

在本发明的优选实施例中，再次参考图2，所有最大级连接器被迫168包含仅一个单元。这通过从每个局部最大级连接器中选择一个单元完成，从它的包含的连接器删去每一个并且从每个被选单元中生成新的级q+1的连接器。然后重置q至值q+1。

在图6所示的连接器的子集上的步骤160以及165的结果如图12所示。在图12中，连接器240、250、260和270均具有仅一个相邻高阶连接器(其为用于这些中的每个上的连接器280)，这样连接器240、250、260和270的每个均与连接器280合并以形成一个大的连接器。(这在图12中通过具有相同的点状图案的连接器240、250、260和270中的所有单元表示。)连接器200、210、220和230(其中的单元未单独示出)具有一个以上的高阶相邻连接器，因此使连接器200、210、220和230保持无变化。

对于步骤168，最初形成连接器280的单元(参见图6)可以被挑选，然后形成仅具有最初的连接器280单元的新连接器，并且仅包含该最初连接器280单元的新连接器的级将从4增加到5。

ACC排序的实例也在图7中示出，并将在图10中进一步论述。

再次参考图2，我们现在使用置换∏以增加的级次序排序170(或重新排序)连接器，使得

S_i＝B_∏(i)                  (方程式11)

其中连接器S_i的级Ω_i为

Ω_i＝κ_∏(i)               (方程式12)

且

Ω_i≤Ω_i+1 i＝1，...，v-1  (方程式13)

然后根据它的n_i单元(结点)写入连接器S_i

$S_i==\{s_1^i,s_2^i,...,s_{n_i}^i\}$(方程式14)

这个步骤可减少不同级的数目。

以它们的原始的排序绘制单元(结点)至该ACC次序的ACC排序Ψ为：

m＝0

 for i＝1，v

     for k＝1，n_i

            m＝m+1

$\Psi \left(s_k^i\right)=m$

      end

end

以矩阵形式使用该置换Ψ，方程Ax＝b变为：

$\tilde{A}y=\tilde{b}$(方程式15)

其中

$\tilde{A}={\Psi }^T\mathrm{A\Psi }$(方程式16)

y＝Ψ^Tx                    (方程式17)

且

$\tilde{b}={\Psi }^{T}b$(方程式18)

该重新排序的矩阵具有形式：

(方程式19)

其中每个${\tilde{A}}_{\mathrm{ii}}i=1,...,q$为具有由级i的连接器构成的块的块对角线。

可近似地表示为因式：

$\tilde{A}\approx \mathrm{LDU}$(方程式20)

其中L为块下三角形，U为块上三角形以及D为块对角线。

为了近似地求解：

$\tilde{A}x=r$(方程式21)

接下来，再次参考图2，由ACC排序构造172内插算子和限定算子。为了完成这个，考虑等效系统：

$L^{-1}\tilde{A}{U}^{-1}y=L^{-1}r$(方程式22)

其中

y＝Ux                       (方程式23)

因为

(方程式24)

于是

$D_q\approx W^T{L}^{-1}\tilde{A}{U}^{-1}W$(方程式25)

其中

$W=\left(\begin{array}{c}0\\ ·\\ ·\\ ·\\ 0\\ I\end{array}\right)$(方程式26)

其中I为与同维度的单位矩阵。

为了简化，该内插算子P写为

P＝U^-1W                 (方程式27)

P的每列表示基函数。P的实例如图8所示，在这里进一步论述。该限定算子写为

R＝W^TL^-1                (方程式28)

R的每行表示第二基函数。为粗网格矩阵，且依照本发明的优选实施例的实例在图14中绘制出，其在这里进一步论述。

为了利用求解线性系统，用于向量y的块q为

$y_q={\left(R\tilde{A}P\right)}^{-1}\mathrm{Rr}$(方程式29)

向量y表示为

y＝y^*+Wy_q               (方程式30)

在左边两侧乘以U^-1，得到原始解向量x：

x＝x^*+Py_q               (方程式31)

在左边乘以并重排得到：

$\tilde{A}{x}^{*}=r-\tilde{A}P{y}_q$(方程式32)

如果M为的某种近似的因式分解，则我们得到该x^*的近似解：

$x^{*}\approx M^{-1}(r-\tilde{A}P{y}_q)$(方程式33)

则该两步骤ACC前置条件通过下式给出：

$x{\approx M}^{-1}(r-\tilde{A}P{y}_q)+P{y}_q$(方程式34)

或者

$x\approx M^{-1}(r-\tilde{A}P{\left(R\tilde{A}R\right)}^{-1}\mathrm{Rr})+P{\left(R\widetilde{\mathrm{AP}}\right)}^{-1}\mathrm{Rr}$(方程式35)

该ACC代数粗网格矩阵为疏散的，并比更小(假定通过一或多个数值的排序)，且因此该粗网格线性解法可使用直接解法或者迭代解法，比如前置条件GMRES或ORTHOMIN，或者其它的不精确的局部求解法，比如块ILU(K)，嵌套因式分解，线性高斯-塞德尔法(Gauss-Seidel)，以效率很高的方式执行。参见Y.Saad和M.H.Schultz：“GMRES：a generalized minimal residual algorithmfor solving nonsymmetric linear systems(一种为求解不对称的线性系统而归纳的最小剩余算法)”，SIAM Journal on Scientific andStatistical Computing，7，PP 856-869，1986；Vinsome，“P.K.W：“Orthomin，an Iterative Method for Solving Sparse Sets ofSimultaneous Linear Equations(一种为求解联立方程的线性方程的稀疏组的迭代法)”，SPE 5729，发表在the Fourth Symposium ofNumerical Simulation of Reservoir Performance of the Societyof Petroleum Engineers of AIME(第四期美国采矿与冶金工程师学会的石油工程师学会的储层动态的数值模拟的论文集)，保存在LosAngeles，Calif.(加利福尼亚州洛杉矶)，Feb.19-20，1976，其全部在此被并入作为参考。

本发明前置条件的总收敛速度典型地大大优于通常使用的方法，比如ILU。同样，该方法适用于从结构化或者非结构化的网格生成的矩阵，包括一维的、二维的或者三维的网格。此外，该方法适用于每一单元(结点)具有一个或多个未知数的矩阵。

图7示出了依照本发明的优选实施例的ACC排序的实例。纵轴300表示方程数目；横轴310表示未知数的数目。

图7的设计可以被认为是具有多个标绘线段的矩形。矩形314中的标绘线段312在上部左手拐角为用于所有区域级1单元的在横轴310上1-1600行的ACC排序的曲线。矩形318中的标绘线段316为用于所有区域级2单元的ACC排序的曲线，其在边缘为单元。矩形322中的标绘线段320为用于所有区域级4单元的ACC排序的曲线，用于顶点上的单元。

两个矩形界定出矩形314。矩形326的标绘线段324表示从级1单元到相邻级2单元的基于ACC排序的非零耦合。矩形330的标绘线段328表示从级1单元到相邻级2单元的基于ACC排序结果的非零耦合。

矩形334的标绘线段332表示从级1单元到相邻4级单元的非零耦合。矩形338的标绘线段336表示从4级单元到相邻级2单元的基于ACC排序结果的非零耦合。

图8示出了内插算子P的实例，具体地为依照本发明的优选实施例的用于二维网格的P的具体实例的列37。(三维网格会得出四维P，其更容易表示为二维图形。)该列37400为多线性的基函数，并且(松散地)类似于具有表示P等于零的基线402(和周围面积)的锥体和表示P等于1的尖端404。

图9示出了依照本发明的优选实施例的具有900个结点(各向同性的情况)的三角形划分的有限元的实例。在图9的实例中，正方形表示级4-39连接器。三角形表示级3连接器，圆圈表示级2连接器，以及虚线表示级1连接器。

图10，如同图7，示出了依照本发明的优选实施例，在矩阵结构上的ACC排序的实例，并且类似地是结构化的，图10所示的实例具有4个连接器级。

图11示出了依照本发明的优选实施例，采取图10的实例的形式的三角形划分的有限元。图11示出了具有900个结点(各向异性的情况)的实例。在图11的实例中，正方形表示级4-20的连接器。三角形表示级3连接器，圆圈表示级2连接器，以及虚线表示级1连接器。

图14示出了ACC代数粗网格矩阵RAP的实例，举例说明了依照本发明的优选实施例的8×8粗网格稀疏图案。Y轴相应于粗网格方程式，且X轴相应于粗网格未知数。

尽管出于举例、说明和描述本发明的特定实施例的目的而提供了前述发明，尤其是细节，但是对所述方法、装置及其他实施例的调整和改进对本领域技术人员是显而易见的，并且可以进行调整和改进而不脱离本发明的范围或者精神。