首页 | 本学科首页   官方微博 | 高级检索  
     


Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Authors:Satoru Iwata  Mizuyo Takamatsu
Affiliation:1. Research Institute for Mathematical Sciences, Kyoto University, Kyoto, 606-8502, Japan
2. Department of Information and System Engineering, Chuo University, Tokyo, 112-8551, Japan
Abstract:Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants. In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号