Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
Computing the Maximum Degree of Minors in Matrix Pencils via Combinatorial Relaxation
复制标题
DOI：
10.1007/s00453-003-1022-9
复制
发表时间：
1999
期刊：
影响因子：
1.1
通讯作者：
S. Iwata
中科院分区：
文献类型：
--
作者：
S. Iwata
本文提出了一种计算矩阵铅笔a (s)中k阶次元的最大度δk (a)的新算法。该问题在数值分析和系统控制领域具有重要的现实意义。该算法采用了基于murata的“组合松弛”的一般框架。首先求解加权二部匹配问题，得到δk (A)的估计，然后检验估计是否正确，利用最优对偶解。如果不正确，则在不改变δk(A)的情况下修改矩阵铅笔A(s)来改进估计。该算法通过常数矩阵的等价变换来实现这种矩阵修正，而先前的算法使用双固有有理函数矩阵。因此，本方法节省了内存空间，并减少了运行时间的a级限制。
This paper presents a new algorithm for computing the maximum degree δk (A) of a minor of order k in a matrix pencil A(s) . The problem is of practical significance in the field of numerical analysis and systems control.The algorithm adopts a general framework of ``combinatorial relaxation'' due to Murota. It first solves the weighted bipartite matching problem to obtain an estimateon δk (A) , and then checks if the estimate is correct, exploiting the optimal dual solution. In case of incorrectness, it modifies the matrix pencil A(s) to improve the estimatewithout changing δk(A) .The present algorithm performs this matrix modification by an equivalence transformation with constant matrices, whereas the previous one uses biproper rational function matrices. Thus the present approach saves memory space and reduces the running time bound by a factor of rank A.