改进的KM算法加速DAE系统结构指标计算

本文主要探讨了计算微分代数方程（DAE）系统结构指标的一种改进的KM算法。DAE在设计和仿真领域中扮演着关键角色，其结构指数的准确计算对于理解和解决DAE问题至关重要。传统的方法，如代数方法，处理这类问题的效率往往较低，成本高昂。 作者首先将计算DAE的结构指数问题转化为了一个最大加权二分图的匹配问题，这种方法的优势在于简化了符号操作的复杂性。通过这种方法，结构指数可以被理解为二分图中顶点之间的最优配对，这使得问题更具可操作性和效率。 提出的改进的KM算法，即Greedy_KM，是建立在DAE特性基础上的。该算法采用贪心策略，试图尽可能多地找到匹配项，然后利用经典的KM算法进一步优化剩余未匹配的顶点。这种策略在解决匹配问题时展现出高效性，因为它首先关注全局匹配的最大化，然后再聚焦于局部细节。 文中强调了匈牙利算法（Hungarian Method），这是一种经典的求解任务分配问题的方法，也被广泛应用于其他问题，如匹配问题。作者运用组合松弛理论，将匈牙利算法与结构指数减少方法相结合，应用于高阶DAE系统，从而实现更高效的结构指数计算。 作者通过一组数值实验对比了Greedy_KM算法与传统的高斯消元算法以及经典KM算法在时间性能上的表现。实验结果表明，Greedy_KM算法在时间效率上显著优于传统方法，显示出其在处理DAE结构指数问题上的优势。 总结来说，本文的主要贡献是提出了一种基于结构指数减少的匈牙利方法改进版算法（Greedy_KM），它在计算DAE系统的结构指标方面展现出了高效和优越的性能，为复杂设计和仿真应用提供了更为实用的工具。这项研究对于提升DAE问题求解的效率和精度具有实际价值。