Computing the Degree of Determinants via Combinatorial Relaxation

ISCAS OpenIR

	Computing the Degree of Determinants via Combinatorial Relaxation
	Kazuo Murota
	1995
发表期刊	SIAM Journal on Computing
卷号	24 期号:4 页码:765 - 796
摘要	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.
收录类别	其他
合作性质	其它
语种	英语
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/1330
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Kazuo Murota. Computing the Degree of Determinants via Combinatorial Relaxation[J]. SIAM Journal on Computing,1995,24(4):765 - 796.
APA	Kazuo Murota.(1995).Computing the Degree of Determinants via Combinatorial Relaxation.SIAM Journal on Computing,24(4),765 - 796.
MLA	Kazuo Murota."Computing the Degree of Determinants via Combinatorial Relaxation".SIAM Journal on Computing 24.4(1995):765 - 796.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
bj01135893.pdf（1804KB）			开放获取	使用许可	请求全文