the research and analysis of hungarian algorithm in the structure index reduction for dae

ISCAS OpenIR

	the research and analysis of hungarian algorithm in the structure index reduction for dae
	Zeng Yan; Wu Xuesong; Cao Jianwen
	2012
会议名称	11th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, DCABES 2012
会议录名称	Proceedings - 11th International Symposium on Distributed Computing and Applications to Business, Engineering and Science, DCABES 2012
页码	446-450
会议日期	October 19, 2012 - October 22, 2012
会议地点	Guilin, China
收录类别	EI
ISBN	9780769548180
部门归属	(1) Laboratory of Parallel Software and Computational Science of Software Institute of Software Chinese Academy of Sciences Beijing 100190 China; (2) Graduate University Chinese Academy of Sciences Beijing 100049 China
摘要	Modeling of complex physical systems with Modelica usually leads to the high-index differential algebraic equation system (DAE), index reduction is an important part of solving the high-index DAE. The structure index reduction algorithm is one of the popular methods, but in special cases, it fails. Combinatorial relaxation algorithm can detect and correct the breakdown situation. And the maximum weight matching of bipartite graph is an important part of the combinatorial relaxation algorithm. In order to choose the proper method for the large-scale, dense bipartite graph, this paper provides three implementations of the Hungarian algorithm. The experiment results and the theory show that the BFS single-augmented method is better than others. © 2012 IEEE.; Modeling of complex physical systems with Modelica usually leads to the high-index differential algebraic equation system (DAE), index reduction is an important part of solving the high-index DAE. The structure index reduction algorithm is one of the popular methods, but in special cases, it fails. Combinatorial relaxation algorithm can detect and correct the breakdown situation. And the maximum weight matching of bipartite graph is an important part of the combinatorial relaxation algorithm. In order to choose the proper method for the large-scale, dense bipartite graph, this paper provides three implementations of the Hungarian algorithm. The experiment results and the theory show that the BFS single-augmented method is better than others. © 2012 IEEE.
关键词	Algorithms Models
语种	英语
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/15887
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Zeng Yan,Wu Xuesong,Cao Jianwen. the research and analysis of hungarian algorithm in the structure index reduction for dae[C],2012:446-450.