Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
type: Item
instance of: scholarly article
title: Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
zbMATH Open document ID: 1284.65059
author: Satoru Iwata
author: Mizuyo Takamatsu
published in: Algorithmica
publication date: 2013-05-13T00:00:00Z
review text: The paper deals with the problem of finding the maximum degree of minors in a mixed polynomial matrix. The authors propose a combinatorial relaxation algorithm for the above problem, which avoids arithmetic operations on rational functions and appears more effective than the previous algorithm of \textit{K. Murota} [SIAM J. Matrix Anal. Appl. 20, No. 1, 196--227 (1998; Zbl 0956.05068)]. The developed algorithm reduces the solution of the considered problem to the solution of a weighted bipartite matching problem and an independent matching problem. The authors apply their algorithm to compute the Kronecker canonical form of a mixed matrix pencil and to the linear valuated independent assignment problem.
reviewed by: Svetlana A. Kravchenko
Mathematics Subject Classification ID: 65F30
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 15A22
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 91B68
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 15A54
Mathematics Subject Classification ID: 15A21
zbMATH DE Number: 6162389
zbMATH Keywords: maximum degree of minors
zbMATH Keywords: polynomial matrix
zbMATH Keywords: combinatorial relaxation algorithm
zbMATH Keywords: matching problem
zbMATH Keywords: Kronecker canonical form
zbMATH Keywords: matrix pencil
zbMATH Keywords: assignment problem
MaRDI profile type: Publication
full work available at URL: s00453-012-9640-8
OpenAlex ID: W2785187072
cites work: Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
cites work: Computational Solutions of Matrix Problems Over an Integral Domain
cites work: On fast multiplication of polynomials over arbitrary algebras
cites work: Accurate Solutions of Ill-Posed Problems in control theory
cites work: Valuated matroids
cites work: Efficient theoretic and practical algorithms for linear matroid intersection problems
cites work: Q3254327
cites work: Algebraic Algorithms for Matching and Matroid Problems
cites work: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
cites work: Combinatorial relaxation algorithm for mixed polynomial matrices
cites work: Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
cites work: On the Kronecker Canonical Form of Mixed Matrix Pencils
cites work: Algorithms – ESA 2004
cites work: Maximum matchings in planar graphs via Gaussian elimination
cites work: Systems analysis by graphs and matroids. Structural solvability and controllability
cites work: Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
cites work: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
cites work: Computing the Degree of Determinants via Combinatorial Relaxation
cites work: Valuated Matroid Intersection I: Optimality Criteria
cites work: Valuated Matroid Intersection II: Algorithms
cites work: On the Degree of Mixed Polynomial Matrices
cites work: Matrices and matroids for systems analysis
cites work: Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—
cites work: Maximum weight bipartite matching in matrix multiplication time
cites work: The singular pencil of a linear dynamical system†
cites work: Rational matrix structure
DOI: 10.1007/S00453-012-9640-8
Recommended article: Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Recommended article: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices
Recommended article: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
Recommended article: Q4252323
Recommended article: Combinatorial relaxation algorithm for mixed polynomial matrices
Recommended article: Q3395748
Recommended article: Computing the Degree of Determinants via Combinatorial Relaxation
Recommended article: Computing Minimal Polynomials of Matrices
Recommended article: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors
Recommended article: On the computation of maximum minors of Hadamard matrices
description: scientific article; zbMATH DE number 6162389