An Improved KM Algorithm for Computing the Structural Index of DAE System
An Improved KM Algorithm for Computing the Structural Index of DAE System
复制标题
计算DAE系统结构指标的改进KM算法
DOI：
10.1260/1748-3018.9.3.233
复制
发表时间：
2015-09
影响因子：
0.9
通讯作者：
曹建文
中科院分区：
文献类型：
--
作者：
曾艳;吴学凇;曹建文
建模与仿真技术被广泛应用于工业中复杂产品的设计。微分代数方程求解问题是建模与仿真技术中的一个关键部分，而正确有效地计算微分代数方程的结构指数对求解微分代数方程至关重要。传统的代数方法计算结构指数是非常昂贵的。本文首先将计算DAE结构指数的问题转化为二部图的最大加权匹配问题，减少了大量的符号操作;然后根据DAE的性质，提出了一种改进的KM算法（本文称为Greedy_KM）来解决该匹配问题。为了有效地解决匹配问题，该算法首先采用贪婪策略计算尽可能多的匹配点，然后调用KM算法对贪婪策略后不匹配的顶点进行匹配搜索。本文还给出了一组数值实验来评估我们的方法的时间性能。实验结果表明，与传统的高斯消去算法和经典KM算法相比，Greedy_KM算法的时间性能有了明显的改善。
Modeling and simulation technology is widely used to design complex products in industry. The problem of solving DAEs(Differential Algebraic Equations) is a key part of modeling and simulation technology, and computing the structural index of DAEs correctly and efficiently is very important to solve DAEs. The traditional algebraic method to compute the structural index is very costly. In this paper, we firstly convert the problem of computing the structural index of DAEs into the maximum weighted matching problem of bipartite graph, reducing a mass of symbolic manipulations; and then, we present an improved KM algorithm(called as Greedy_KM in this paper) based on the properties of DAEs to solve this matching problem. In order to solve the matching problem efficiently, it firstly computes matches as much as possible using greedy strategy, and then call KM algorithm to search the matches for the unmatched vertices after the step of greedy strategy. This paper also gives a set of numerical experiments to evaluate the time performance of our method. The results show that the time performance of Greedy_KM algorithm is significantly improved compared with the traditional Gaussian elimination algorithm and classical KM algorithm.
登录
查看更多内容
DOI：
10.1007/978-3-642-03994-2
发表时间：
2000-01
期刊：
--
影响因子：
--
作者：
K. Murota
通讯作者：
K. Murota
DOI：
10.1137/1.9781611971392
发表时间：
1998-07
期刊：
--
影响因子：
--
作者：
U. Ascher;L. Petzold
通讯作者：
U. Ascher;L. Petzold
DOI：
10.1007/978-3-642-34381-0_32
发表时间：
2012-10
期刊：
--
影响因子：
--
作者：
Yan Zeng;Xuesong Wu;Jianwen Cao
通讯作者：
Yan Zeng;Xuesong Wu;Jianwen Cao
DOI：
10.6028/jres.069b.013
发表时间：
1965-01-01
期刊：
JOURNAL OF RESEARCH OF THE NATIONAL BUREAU OF STANDARDS SECTION B-MATHEMATICS AND MATHEMATICAL
影响因子：
--
作者：
EDMONDS, J
通讯作者：
EDMONDS, J
影响因子：
1.1
作者：
S. Iwata
通讯作者：
S. Iwata