Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form

DOI10.1007/BF01235719zbMath0826.05044MaRDI QIDQ1894574

Kazuo Murota

Publication date: 3 August 1995

Published in: Applicable Algebra in Engineering, Communication and Computing (Search for Journal in Brave)

zbMATH Keywords

bipartite graphminormatrixmaximum weight matchingKronecker formSmith-McMillan formstructural indicessubdeterminantscombinatorial relaxation algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Matrix pencils (15A22)

Related Items (11)

Index Reduction via Unimodular Transformations ⋮ Well-layered maps and the maximum-degree \(k \times k\)-subdeterminant of a matrix of rational functions ⋮ Finding optimal minors of valuated bimatroids ⋮ Well-layered maps---a class of greedily optimizable set functions ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation ⋮ Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation ⋮ Index reduction for differential-algebraic equations by substitution method ⋮ Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors ⋮ Legendre duality in combinatorial study of matrix pencils ⋮ Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Submodular functions and optimization
• Bimatroids and invariants
• An identity for matching and skew-symmetric determinant
• An identity for bipartite matching and symmetric determinant
• On the structure at infinity of a structured system
• Structure at Infinity of Structured Descriptor Systems and Its Applications
• Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
• Computing the Structural Index
• Rational matrix structure
• Structure at inifinity of linear multivariable systems: A geometric approach
• Disturbance rejection for structured systems
• Computing the Degree of Determinants via Combinatorial Relaxation

This page was built for publication: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form