Computing the Degree of Determinants Via Combinatorial Relaxation
Computing the Degree of Determinants Via Combinatorial Relaxation
复制标题
通过组合松弛计算行列式的次数
DOI：
10.1137/s0097539791201897
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
K. Murota
中科院分区：
文献类型：
--
作者：
K. Murota
令$ a（x）=（a_ {ij}（x））$是一个方形矩阵，$ a_ {ij} $是$ x $中的多项式。本文提出了用于计算行列式程度的“组合放松”类型算法，$ \ delta（a）= \ deg_x \ det a（x）$，基于其组合上限$ \ widehat \ delta（a）$，它是根据相关图中完美匹配的最大重量定义的。该图是一般正方形矩阵$ a $和非偏面的二分之一的图表。该算法将$ a $转换为另一个矩阵$ a'$，$ \ delta（a）= \ delta（a'）= \ widehat \ delta（a'）$具有连续的基本操作。该算法是有效的，充分利用了加权匹配的快速算法；它在几乎所有情况下（或普遍）都是组合的，并且仅在发生意外数值取消时才调用代数消除例程。
通过传递显示（偏斜）对称的多项式矩阵$ a（x）$，存在一个单模型矩阵$ u（x）$，因此$ a'（x）= u（x）a（x）a（x）u（x）u （x）^\ tp $满足$ \ delta（a）= \ delta（a'）= \ wideHat \ delta（a'）$。
Let $A(x)=(A_{ij}(x))$ be a square matrix with $A_{ij}$ being a polynomial in $x$. This paper proposes "combinatorial relaxation" type algorithms for computing the degree of the determinant, $\delta(A) = \deg_x \det A(x)$, based on its combinatorial upper bound $\widehat \delta(A)$, which is defined in terms of the maximum weight of a perfect matching in an associated graph. The graph is bipartite for a general square matrix $A$ and nonbipartite for a skew-symmetric $A$. The algorithm transforms $A$ to another matrix $A'$ for which $\delta(A) = \delta(A') = \widehat \delta(A')$ with successive elementary operations. The algorithm is efficient, making full use of the fast algorithms for weighted matchings; it is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur.
It is shown in passing that for a (skew-)symmetric polynomial matrix $A(x)$ there exists a unimodular matrix $U(x)$ such that $A'(x)=U(x) A(x) U(x)^\tp$ satisfies $\delta(A) = \delta(A') = \widehat \delta(A')$.