Combinatorial relaxation algorithm for mixed polynomial matrices

The notion of mixed polynomial matrices is a mathematical tool for faithful description of discrete physical/engineering dynamical systems. It distinguishes two kinds of numbers: fixed constant that account for conservation laws and independent parameters that represent physical characteristics. This paper presents an algorithm for computing the maximum degree of subdeterminants of a fixed order in a polynomial matrix that is obtained by substituting specific numerical values to the independent physical parameters of a mixed polynomial matrix. The algorithm first computes the generic solution by a combinatorial method, i.e., by solving a valuated matroid intersection problem associated with the mixed polynomial matrix, and then finds the exact solution for the specified parameter values with a minimum amount of numerical computation. This is intended to be a nontrivial application of mathematical programming techniques to computer algebra and systems analysis.