Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
assignment problemcombinatorial relaxation algorithmKronecker canonical formmatching problemmatrix pencilmaximum degree of minorspolynomial matrix
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Canonical forms, reductions, classification (15A21) Matrix pencils (15A22) Matrices over function rings in one or more variables (15A54) Discrete location and assignment (90B80) Combinatorial optimization (90C27) Matching models (91B68)
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.
- Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
- Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices
- Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
- scientific article; zbMATH DE number 1305439
- Combinatorial relaxation algorithm for mixed polynomial matrices
- On the computation of the minimal polynomial of a polynomial matrix
- Computing the Degree of Determinants via Combinatorial Relaxation
- Computing minimal polynomials of matrices
- Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors
- On the computation of maximum minors of Hadamard matrices
- Accurate Solutions of Ill-Posed Problems in control theory
- Algebraic algorithms for matching and matroid problems
- Algorithms – ESA 2004
- Combinatorial relaxation algorithm for mixed polynomial matrices
- Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
- Computational Solutions of Matrix Problems Over an Integral Domain
- Computing Puiseux-Series Solutions to Determinantal Equations via Combinatorial Relaxation
- Computing the Degree of Determinants via Combinatorial Relaxation
- Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
- Efficient theoretic and practical algorithms for linear matroid intersection problems
- scientific article; zbMATH DE number 3138903 (Why is no real title available?)
- Matrices and matroids for systems analysis
- Maximum matchings in planar graphs via Gaussian elimination
- Maximum weight bipartite matching in matrix multiplication time
- On fast multiplication of polynomials over arbitrary algebras
- On the Degree of Mixed Polynomial Matrices
- On the Kronecker canonical form of mixed matrix pencils
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
- Rational matrix structure
- Structural solvability of systems of equations —A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems—
- Sylvester's Identity and Multistep Integer-Preserving Gaussian Elimination
- Systems analysis by graphs and matroids. Structural solvability and controllability
- The singular pencil of a linear dynamical system†
- Valuated Matroid Intersection I: Optimality Criteria
- Valuated Matroid Intersection II: Algorithms
- Valuated matroids
- Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
- Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form
- Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
- Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices
- Computing the degrees of all cofactors in mixed polynomial matrices
- On the Degree of Mixed Polynomial Matrices
- scientific article; zbMATH DE number 1305439 (Why is no real title available?)
- Computing the Degree of Determinants via Combinatorial Relaxation
- Computing the combinatorial canonical form of a layered mixed matrix
- Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- On the Kronecker Canonical Form of Singular Mixed Matrix Pencils
- Combinatorial relaxation algorithm for mixed polynomial matrices
- A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2 2 submatrices
This page was built for publication: Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1950387)
