An improved KM algorithm for computing the structural index of DAE system

被引：0
作者：
Zeng, Yan [1 ,2 ,3 ]
Wu, Xuesong [1 ]
Cao, Jianwen [1 ,3 ]
机构：
[1] Institute of Software, Chinese Academy of Sciences, Beijing
[2] University of Chinese Academy of Sciences, Beijing
[3] State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing
来源：
Journal of Algorithms and Computational Technology | 2015年 / 9卷 / 03期
关键词：
Bipartite graph; DAE; Greedy; Index reduction; KM algorithm; Structural index;
D O I：
10.1260/1748-3018.9.3.233
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：233 / 250
页数：17
相关论文
共 16 条
  • [1] Fritzson P., Principles of Object-Oriented Modeling and Simulation with Modelica 2.1, (2003)
  • [2] Ascher U.M., Petzold L.R., Computer Methods for Ordinary Differential Equations and Differential-Algebraic Equations, (2009)
  • [3] Kunkel P., Mehrmann V., Differential-Algebraic Equations: Analysis and Numerical Solution, (2006)
  • [4] Haier E., Wanner G., Solving Ordinary Differential Equations II. Stiff and Differential-Algebraic Problems, (1996)
  • [5] Murota K., Matrices and Matroids for Systems Analysis, (2010)
  • [6] Grcar J.F., Mathematicians of Gaussian elimination, Notices of the American Mathematical Society, 58, 6, pp. 782-792, (2011)
  • [7] Iwata S., Computing the maximum degree of minors in matrix pencils via combinatorial relaxation, Algorithmica, 36, pp. 331-341, (2003)
  • [8] Murota K., Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing smith-mcmillan form at infinity and structural indices in kronecker form, applicable algebra in engineering, Communication and Computing, 6, pp. 251-273, (1995)
  • [9] Ford L.R., Fulkerson D.R., Maximal flow through a network, Canadian Journal of Mathematics, 8, pp. 399-404, (1956)
  • [10] Edmonds J., Maximum matching and a polyhedron with 0-1 vertices, Journal of Research of the National Bureau of Standards (B), 69, pp. 125-130, (1965)
12