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

A combinatorial relaxation algorithm is proposed to compute the highest degree of a minor, of a specified order \(k\), of a matrix whose entries are polynomials, or rational functions, of a single variable. It uses an algorithm which finds a maximum weight matching of size \(k\) in a bipartite graph. The resulting ``generic'' answer is then modified if ``accidental numerical cancellations occur''.