Name
Abstract | ||
|---|---|---|
Suppose the polynomials f and g in K[x1,...,xr] over the field K are determinants of non-singular m x m and n x n matrices, respectively, whose entries are in K ∪ x1,...,xr. Furthermore, suppose h = f/g is a polynomial in K[x1,..., xr]. We construct an s x s matrix C whose entries are in K ∪ x1,...,xr, such that h = det(C) and s = γ (m+n)6, where γ = O(1) if K is an infinite field or if for the finite field K = F{q} with q elements we have m = O(q), and where γ = (logq m)1+o(1) if q = o(m). Our construction utilizes the notion of skew circuits by Toda and WSK circuits by Malod and Portier. Our problem was motivated by resultant formulas derived from Chow forms. Additionally, we show that divisions can be removed from formulas that compute polynomials in the input variables over a sufficiently large field within polynomial formula size growth. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1145/1390768.1390790 | ISSAC |
Keywords | Field | DocType |
large field,polynomial formula size growth,q element,finite field k,field k,chow form,infinite field,wsk circuit,non-singular m,logq m | S-matrix,Discrete mathematics,Combinatorics,Finite field,Polynomial,Matrix (mathematics),Mathematics | Conference |
Citations | PageRank | References |
16 | 0.92 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erich Kaltofen | 1 | 2332 | 261.40 |
| Pascal Koiran | 2 | 919 | 113.85 |