ISSN:
1432-0622
Keywords:
combinatorial matrix theory
;
computer algebra
;
determinant
;
Kronecker form of matrix pencil
;
matching
;
polyhedral combinatorics
;
Smith-McMillan form of rational matrix
;
05C50
;
15A15
;
68Q40
;
68Q25
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
,
Technology
Notes:
Abstract LetA(x)=(A ij (x)) be a matrix withA ij (x) being a polynomial or rational function inx. This paper proposes a “combinatorial relaxation” type algorithm for computing the highest degreeδ k (A) of a minor ofA(x) of a specified orderk. Such an algorithm can be used to compute the Smith-McMillan form of a rational function matrix at infinity, as well as the structure of the Kronecker form of a matrix pencil. The algorithm is based on a combinatorial upper bound $$\hat \delta _k (A)$$ onδ k (A), which is defined as the maximum weight of a matching of sizek in a bipartite graph associated withA. The algorithm is efficient, making full use of the fast algorithms for weighted matchings. It is combinatorial in almost all cases (or generically) and invokes algebraic elimination routines only when accidental numerical cancellations occur. The validity relies on the integrality of bipartite matching polytopes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01235719
Permalink
