基于懒惰分层的电力系统下三角方程组求解方法和系统

摘要

本发明实施例提供的基于懒惰分层的电力系统下三角方程组求解方法和系统，所述方法包括：获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei‑1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

权利要求

1.一种基于懒惰分层的电力系统下三角方程组求解方法，其特征在于，包括：获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层；

对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解；

对同一层内的节点顺序进行调整，将同样入度的节点聚集在同一线程组中；

增加指示每个线程组需要循环次数的变量，通过无效节点填充线程组中的未填充剩余线程，使各种入度的节点正确地对应到线程组中。

2.根据权利要求1所述的方法，其特征在于，对所述稀疏矩阵进行LU分解得到下三角矩阵具体包括：基于所述稀疏矩阵生成包含全部依赖关系信息的有向无环图DAG，并对所述DAG进行LU分解，得到所述稀疏矩阵的下三角矩阵。

3.根据权利要求2所述的方法，其特征在于，基于所述稀疏矩阵生成包含全部依赖关系信息的有向无环图DAG后还包括：构造基于节点的数据结构，对DAG中的所有信息原样保存，每一个节点都包含两个列表，分别保存了自己的所有父节点和子节点的指针。

4.根据权利要求1所述的方法，其特征在于，并通过懒惰分层算法对所述下三角矩阵进行分层后，还包括：对同一层中的节点编号进行调整，使每一层中的节点编号连续。

5.一种基于懒惰分层的电力系统下三角方程组求解系统，其特征在于，包括电力系统信息获取模块和求解模块；

电力系统信息获取模块用于获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

求解模块用于对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层；

对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解；

对同一层内的节点顺序进行调整，将同样入度的节点聚集在同一线程组中；增加指示每个线程组需要循环次数的变量，通过无效节点填充线程组中的未填充剩余线程，使各种入度的节点正确地对应到线程组中。

6.一种基于懒惰分层的电力系统下三角方程组求解设备，其特征在于，包括：至少一个处理器；以及

与所述处理器通信连接的至少一个存储器，其中：

所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令能够执行如权利要求1至4任一所述的方法。

7.一种非暂态计算机可读存储介质，其特征在于，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行如权利要求1至4任一所述的方法。

说明书

基于懒惰分层的电力系统下三角方程组求解方法和系统

技术领域

[0001] 本发明涉及电力系统分析计算技术领域，更具体地，涉及一种基于懒惰分层的电力系统下三角方程组求解方法和系统。

背景技术

[0002] 在电力系统计算过程中，线性方程组的求解是一个经常遇到的问题。潮流计算与状态估计中，牛顿拉夫逊法及其各类改进算法的实现，离不开迭代过程中对修正方程(Jacobi矩阵)的求解；在暂态仿真中，描述输电网络状态的方程和描述设备运行情况的方程都属于高阶非线性方程组，对其进行求解需要进行数值积分，一般需要使用牛顿法将其差分化为相应的线性方程后迭代求解，而在此类迭代求解的过程中也需要对大型线性方程组进行求解。因此，对线性方程组的求解过程进行优化，加快其求解速度，可以有效减少各类电力系统计算的用时，提高求解的实时性。

[0003] 并行计算是计算机科学中重要的研究内容，已有几十年的发展历程。用并行计算求解问题的大致过程为：对于一个给定的应用问题，首先，计算科学家将这个应用转化为一个数值或非数值的计算问题；然后计算机科学家对此计算问题设计并行算法，并通过某种并行编程语言实现它；最后应用领域的专家在某台具体的并行计算机上运行应用软件求解此问题。由此，可以很自然的发现并行计算由以下几个部分构成：并行计算机(并行计算的硬件平台)，并行算法(并行计算的理论基础)，并行程序设计(并行计算的软件支撑)，并行应用(并行计算的发展动力)。

[0004] 现有的方法并非针对电力系统问题而设计，是一个基于稀疏矩阵的通用求解方法，其在开始分析时便以层为单位进行组织，其大致思路是将没有数据依赖的节点提取至新的一层，并除去其他节点对已经分析节点的数据依赖，重复此流程直至节点全部处理完成。这种方法简单有效，适应性强，但其生成的分层结果倾向于将节点划分至编号较小的层，使得整个算法的分层结果集中在前几层，算法的并行平均度较差，尤其是在对于前代矩阵的分析中，形成的DAG图(Directed Acyclic Graph，有向无环图)极不均匀，大大拖慢了并行求解的速度。

发明内容

[0005] 本发明提供一种克服上述问题或者至少部分地解决上述问题的基于懒惰分层的电力系统下三角方程组求解方法和系统，解决了现有技术中整个算法的分层结果集中在前几层，算法的并行平均度较差、形成的DAG图极不均匀，大大拖慢了并行求解的速度的问题。

[0006] 根据本发明的一个方面，提供一种基于懒惰分层的电力系统下三角方程组求解方法，包括：

[0007] 获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0008] 对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0009] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0010] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0011] 作为优选的，对所述稀疏矩阵进行LU分解得到下三角矩阵具体包括：

[0012] 基于所述稀疏矩阵生成包含全部依赖关系信息的有向无环图DAG，并对所述DAG进行LU分解，得到所述稀疏矩阵的下三角矩阵。

[0013] 作为优选的，基于所述稀疏矩阵生成包含全部依赖关系信息的有向无环图DAG后还包括：

[0014] 构造基于节点的数据结构，对DAG中的所有信息原样保存，每一个节点都包含两个列表，分别保存了自己的所有父节点和子节点的指针。

[0015] 作为优选的，并通过懒惰分层算法对所述下三角矩阵进行分层后，还包括：

[0016] 对同一层内的节点顺序进行调整，将同样大小的节点聚集在同一线程组中；

[0017] 增加指示每个线程组需要循环次数的变量，通过无效节点填充线程组中的未填充剩余线程，使各种大小的节点正确地对应到线程组中。

[0018] 作为优选的，并通过懒惰分层算法对所述下三角矩阵进行分层后，还包括：

[0019] 对同一层中的节点编号进行调整，使每一层中的节点编号连续。

[0020] 一种基于懒惰分层的电力系统下三角方程组求解系统，包括电力系统信息获取模块和求解模块；

[0021] 电力系统信息获取模块用于获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0022] 求解模块用于对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0023] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0024] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0025] 一种基于懒惰分层的电力系统下三角方程组求解设备，包括：

[0026] 至少一个处理器；以及

[0027] 与所述处理器通信连接的至少一个存储器，其中：

[0028] 所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令能够执行如上述基于懒惰分层的电力系统下三角方程组求解方法。

[0029] 一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行如上述基于懒惰分层的电力系统下三角方程组求解方法。

[0030] 本发明提出基于懒惰分层的电力系统下三角方程组求解方法和系统，通过对电力系统稀疏矩阵的结构分析，对前代回代求解过程中的DAG生成算法进行了改进，将矩阵生成包含全部依赖关系信息的DAG图，再在此基础上，对DAG进行分层，使用多种方法调整节点所在层的编号，将节点尽可能均匀地放入各层，提高了并行前代回代计算的效率，能够有效提升在并行处理器上的稀疏前代回代的并行度和运算速度。

附图说明

[0031] 图1为根据本发明实施例的基于懒惰分层的电力系统下三角方程组求解方法示意图；

[0032] 图2为根据本发明实施例的稀疏矩阵求解的流程图示意图；

[0033] 图3为根据本发明实施例的基于节点的数据结构示意图；

[0034] 图4为根据本发明实施例的基于懒惰分层的电力系统下三角方程组求解设备结构示意图。

具体实施方式

[0035] 下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

[0036] 如图1所示，图中示出了一种基于懒惰分层的电力系统下三角方程组求解方法，包括：

[0037] 获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0038] 对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0039] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0040] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0041] 在电力系统问题中，常常需要对多个结构相同的稀疏矩阵进行求解。为此，一般依据矩阵的结构进行符号分析，再根据符号分析的结果带入数据进行数值求解。对于同一结构的多个矩阵，符号分解只需进行一次，而数值求解需要进行多次。当数值求解进行的次数足够多时，符号分解的开销相当于均摊至每次符号分解的过程中，因此符号分解的算法效果的重要性要大大高于其速度的重要性。

[0042] 在本实施例中，对所述稀疏矩阵进行LU分解得到下三角矩阵具体包括：基于所述稀疏矩阵生成包含全部依赖关系信息的有向无环图DAG，并对所述DAG进行LU分解，得到所述稀疏矩阵的下三角矩阵。

[0043] 稀疏矩阵求解的流程图如图2所示，包括稀疏矩阵结构符号分解，得到矩阵数值，并对矩阵数值进行数值求解。在本实施例中，主要对符号分解部分进行改进处理，具体方案为对矩阵进行DAG分析。

[0044] 现有的DAG分析方法在开始分析时便以层为单位进行组织，其大致思路是将没有数据依赖的节点提取至新的一层，并除去其他节点对已经分析节点的数据依赖，重复此流程直至节点全部处理完成。这种方法简单有效，适应性强，但由于其分析结果将节点间的依赖信息逐步抽象为节点所在层的信息，DAG的大部分原始信息都被忽略了，故难以在此基础上对DAG进行优化。

[0045] 在本实施例中，为了能够保留足够的信息以对DAG进行更多的调整，本实施例中重写了DAG的分析算法，构造了基于节点的数据结构，将DAG中的所有信息原样保存，以便于进一步的优化，具体的，数据结构如图3所示。在此结构中，每一个节点都包含两个列表，分别保存了自己的所有父节点和子节点的指针，完整保留了所有原始信息。

[0046] 在本实施例中，为了对计算模型进一步抽象，以减少在并行计算及任务间同步时的复杂度，引入了层(level)的概念对并行子任务进行划分。对于所有的节点i和其所在的层数ei，需要满足条件：

[0047] 1、其所有父节点：pi1,pi2,…,pin；

[0048] 其层数 满足：

[0049]

[0050] 2、其所有子节点：ci1,ci2,…,cim；

[0051] 其层数： 满足：

[0052]

[0053] 即父节点所在层数小于当前节点所在层数，子节点所在层数大于当前结节点所在层数。

[0054] 此时，节点间的依赖关系被简化为每个节点所在层的关系，只要保证节点i计算开始时满足ek

[0055] 现有的DAG分析方法在开始分析时便以层为单位进行组织，其大致思路是将没有数据依赖的节点提取至新的一层，并除去其他节点对已经分析节点的数据依赖，重复此流程直至节点全部处理完成。这种方法简单有效，适应性强，但由于其分析结果将节点间的依赖信息逐步抽象为节点所在层的信息，DAG的大部分原始信息都被忽略了，故难以在此基础上对DAG进行优化。

[0056] 为了能够保留足够的信息以对DAG进行更多的调整，本实施中通过对DAG的分析算法进行改进，构造了基于节点的数据结构，将DAG中的所有信息原样保存，以便于进一步的优化。

[0057] 具体的，在本实施例中，在前代环节通过懒惰分层算法(即从叶节点向根节点计算层数)对所述DAG进行分层，具体包括：

[0058] 对DAG树中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；

[0059] 重复上述步骤，递归地设置节点k的父节点的层编号。

[0060] 对于电力系统问题中的L矩阵而言，其DAG分层结果倾向于前几层并行度大，后续层数并行度快速减小。因此仅在下一层需要该节点结果时开始计算，称其为懒惰分层算法。懒惰分层算法(即从根节点向叶节点计算层数)的流程如下所示，对DAG树中的每个节点i：

[0061] 如果节点i没有子节点：

[0062] 1、设置i的层编号ei为最大值；

[0063] 2、设置i的父节点的层编号；

[0064] 父节点的层编号的设置流程如下，对于节点i的每个父节点k：

[0065] 1、设置k的层编号ek为ek和ei-1中较小者；

[0066] 2、按相同流程设置k的父节点的层编号。

[0067] 在本实施例中，并对所述DAG进行分层后，还包括：

[0068] 将同一层内的节点顺序进行调整，将同样大小的节点聚集在同一线程组中；

[0069] 增加指示每个线程组需要循环次数的变量，通过无效节点填充线程组中的未填充剩余线程，使各种大小的节点正确地对应到线程组中。

[0070] 在本实施例中，采用CUDA(Compute Unified Device Architecture)来作为GPU通用计算(GPGPU)平台和编程模型，在CUDA C中，每个线程都有一个唯一的线程ID。CUDA使用一个3维向量threadIdx作为线程ID，以便于开发者在操作向量、矩阵、3阶张量时可以使用更自然的语法对各元素进行访问。在实际组织线程时，线程ID是以x、y、z的顺序组织的，即(x，y，z)的线程ID为x+yDx+zDxDy，其中Dx、Dy为线程块(block)在x、y方向上的规模。由于每个线程块上的线程需要居留于同一个流式多处理器(streaming multiprocessor)，共享其存储资源，故线程块的规模是有限的，目前来说，每个线程块最多包含1024个线程。

[0071] 在每个流式多处理器中，包含着多个流处理器(streaming processor)。在实际的执行过程中，流式多处理器将每32个线程组织为一个线程组(warp)，这是GPU上进行线程调度的最小单位。同一个线程组中包含的32个线程是基于SIMT模式运行的，同一个线程组的所有线程都使用不同的数据执行同一条指令。这意味着程序在执行过程中发生分支时，线程组会串行地执行各个分支，这样的行为导致了线程组中未处于活动分支的部分线程处于不活动状态，降低了流处理器的使用率，造成计算资源的浪费。

[0072] 线程块以相似的方式组织为线程网格(grid)，线程网格的规模一般由数据的规模或系统流式多处理器数目决定，但不受流式多处理器数目的限制。

[0073] 对于节点i而言，其计算过程如下：

[0074] xi＝(bi-∑aikxk)/aii

[0075] 其中累计求和部分，可以利用矩阵的稀疏性，跳过aik中的非零元，这也是本实施例中DAG分析的基础。

[0076] 虽然节点内的求积操作aikxk可以并行计算，但其求和过程则由于节点中非零元数量限制，导致使用归并算法等并行求和算法的开销相对在单个线程完成求积和求和操作的开销相比并不占优势。

[0077] 在本实施例中，使用单个线程完成整个节点的计算过程，其计算流程包含了根据该行非零元位置和数目的多次求积和累加操作，需要使用循环的方式来进行运算。上述的关于线程调度方面的内容可知，由单个节点的线程处于一个32线程组成的线程组中，其中各线程处理的节点情况各不相同，导致了分支的产生，使得线程组的执行效率下降。

[0078] 为了减少线程组内的分支，需要使其中的线程执行相同的逻辑。因此，在生成DAG分层的过程中，应将同一层内的节点顺序进行调整，将同样大小的节点聚集在同一线程组中，实现对齐。

[0079] 在本实施例中，为了实现上述的优化，在DAG分层的生成过程中，额外增加了指示每个线程组需要循环次数的变量。同时，由于每一层的各种大小的节点不一定能够依次填充并对齐至各线程组，因此，在本实施例中，使用了一些无效节点填充了线程组中的剩余线程，使各种大小的节点能够正确地对齐到线程组，这些无效节点使用节点编号-1进行表示。

[0080] 在本实施例中，将节点均匀的放入到各分层中后还包括：

[0081] 在所述DAG中至少设置一条关键路径，所述关键路径上的节点在上一个节点完成之后立刻开始计算；

[0082] 所述每个分层中位于关键路径上的节点关键程度最高，关键路径外节点的关键程度按照不影响DAG用时的灵活程度增加依次降低。

[0083] 本实施例中，以懒惰分层算法(即从叶节点向根节点计算层数)为基础，参考了AOE(Activity On Edge)网AOV(Activity On Vertex)网中的关键路径计算的相关思想和方法，设计了基于关键路径分析的DAG分层算法，其基本方法如下：

[0084] 1、在DAG中，设置至少一条关键路径，其所有节点必须在上一个节点完成之后立刻开始计算，否则会影响到整个DAG的用时；

[0085] 2、在整个DAG中，每一个节点所具有的关键程度是不同的，位于关键路径上的节点关键程度最高，其他节点依据其能够在不影响整个DAG用时的情况下的灵活程度的增加依次降低；

[0086] 3、在安排每一层的节点时，位于关键路径上的节点必须安排，其余节点的优先级应依照其关键程度而定。

[0087] 在本实施例中，通过节点关键程度算法实现节点的关键程度计算，具体计算流程包括：

[0088] 1、使用懒惰算法计算所需的层数nlevel；

[0089] 2、将DAG树的所有节点加入等待列表U；

[0090] 对于每一层l，l的值从0至nlevel：

[0091] 1)、遍历等待列表U，将其中所有没有依赖的节点移动到候选列表C；

[0092] 2)、遍历候选列表C，将其中所有关键程度为0的节点层编号设置为l，并移除出候选列表、移除后续节点的对其的依赖关系；

[0093] 3)、依关键程度数值从小到大(关键程序从高到低)遍历候选列表C，直至当前层达到平均并行度；

[0094] 4、更新候选列表C包含节点及其子节点组成的子树的关键程度。

[0095] 在本实施例中，还提出以下对DAG分层进行微调，以减小同一层节点种类，提高并行度的算法。其基本思路是将相同大小的节点调整至同一层，具体算法如下：

[0096] 1、对于每一个节点i，其节点大小(入度)为deg—(i)，所在的DAG层为ei；

[0097] 2、给定系数k，计算δ(i)＝[degˉ(i)+level(i)]mod k；

[0098] 3、对所有节点ei顺序进行调整，使δ(i)＝0。

[0099] 如果对于所有节点的调整都能完成(即满足3中给定的条件)，则整个DAG分层中每一层的节点大小的种类将下降至原先的1/k。

[0100] 在实际算法实现中，对以懒惰算法得到的DAG分层，从前向后遍历节点，调整时将节点向前移动。

[0101] 本实施例中还提供了一种基于懒惰分层的电力系统下三角方程组求解系统，包括电力系统信息获取模块和求解模块；

[0102] 电力系统信息获取模块用于获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0103] 求解模块用于对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0104] 对DAG树中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0105] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0106] 图4是示出本申请实施例的基于懒惰分层的电力系统下三角方程组求解设备的结构框图。

[0107] 参照图4，所述基于DAG的电力系统稀疏矩阵并行求解设备，包括：处理器(processor)810、存储器(memory)830、通信接口(Communications Interface)820和总线840；

[0108] 其中，

[0109] 所述处理器810、存储器830、通信接口820通过所述总线840完成相互间的通信；

[0110] 所述通信接口820用于该测试设备与显示装置的通信设备之间的信息传输；

[0111] 所述处理器810用于调用所述存储器830中的程序指令，以执行上述各方法实施例所提供的基于懒惰分层的电力系统下三角方程组求解方法，例如包括：

[0112] 获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0113] 对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0114] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0115] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0116] 本实施例公开一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，计算机能够执行如上述的基于懒惰分层的电力系统下三角方程组求解方法，例如包括：

[0117] 获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0118] 对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0119] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0120] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0121] 本实施例中还提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行如上述的基于懒惰分层的电力系统下三角方程组求解方法，例如包括：

[0122] 获取描述输电网络状态或描述设备运行情况的方程组在迭代求解过程中修正方程对应的稀疏矩阵；

[0123] 对所述稀疏矩阵进行LU分解得到下三角矩阵，并通过懒惰分层算法对所述下三角矩阵进行分层：

[0124] 对下三角矩阵中的每个节点i，若节点i没有子节点，则设置节点i的层编号ei为最大值，并按以下流程设置节点i的父节点的层编号：对节点i的每个父节点k，将k的层编号ek和ei-1中较小者设为节点k的层编号；重复上述步骤，递归地设置节点k的父节点的层编号；

[0125] 调整下三角矩阵中节点所在层的编号，将节点均匀的放入到各分层中，对分层后得到的矩阵数值进行前代求解。

[0126] 综上所述，本发明提出的基于懒惰分层的电力系统下三角方程组求解方法和系统，通过对电力系统稀疏矩阵的结构分析，对前代回代求解过程中的DAG生成算法进行了改进，将矩阵生成包含全部依赖关系信息的DAG图，再在此基础上，对DAG进行分层，使用多种方法调整节点所在层的编号，将节点尽可能均匀地放入各层，提高了并行前代回代计算的效率，能够有效提升在并行处理器上的稀疏前代回代的并行度和运算速度。

[0127] 本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

[0128] 以上所描述的显示装置的测试设备等实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

[0129] 通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

[0130] 最后应说明的是：以上各实施例仅用以说明本发明的实施例的技术方案，而非对其限制；尽管参照前述各实施例对本发明的实施例进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明的实施例各实施例技术方案的范围。