Institutional Repository
| Computing the Degree of Determinants via Combinatorial Relaxation | |
| Kazuo Murota | |
| 1995 | |
| Source | SIAM Journal on Computing
 |
| Volume | 24Issue:4Pages:765 - 796 |
| English Abstract | 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. |
| Indexed Type | 其他 |
| Cooperation Status | 其它 |
| Language | 英语 |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/1330 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation 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. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| bj01135893.pdf（1804KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment