research-article

Resultants and Discriminants for Bivariate Tensor-Product Polynomials

Authors:

Angelos Mantzaflaris,

Elias TsigaridasAuthors Info & Claims

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

Pages 309 - 316

https://doi.org/10.1145/3087604.3087646

Published: 23 July 2017 Publication History

Abstract

Optimal resultant formulas have been systematically constructed mostly for unmixed polynomial systems, that is, systems of polynomials which all have the same support. However, such a condition is restrictive, since mixed systems of equations arise frequently in practical problems.

We present a square, Koszul-type matrix expressing the resultant of arbitrary (mixed) bivariate tensor-product systems. The formula generalizes the classical Sylvester matrix of two univariate polynomials, since it expresses a map of degree one, that is, the entries of the matrix are simply coefficients of the input polynomials.

Interestingly, the matrix expresses a primal-dual multiplication map, that is, the tensor product of a univariate multiplication map with a map expressing derivation in a dual space. Moreover, for tensor-product systems with more than two (affine) variables, we prove an impossibility result: no universal degree-one formulas are possible, unless the system is unmixed.

We present applications of the new construction in the computation of discriminants and mixed discriminants as well as in solving systems of bivariate polynomials with tensor-product structure.

References

[1]

M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Algorithms in algebraic geometry and applications. chapter Zeros, Multiplicities, and Idempotents for Zero-dimensional Systems, pp. 1--15. 1996.

Digital Library

[2]

A. Bostan, B. Salvy, and É. Schost. Fast algorithms for zero-dimensional polynomial systems using duality. Applicable Algebra in Engineering, Communication and Computing, 14 (4): 239--272, 2003.

[3]

R. Bott. Homogeneous vector bundles. Annals of Mathematics, 66 (2): 203--248, 1957.

[4]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Rational univariate representations of bivariate systems and applications. In Proc. 38th Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 109--116, 2013. ISBN 978--1--4503--2059--7.

Digital Library

[5]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Separating linear forms for bivariate systems. In Proc. of the 38th Int'l Symposium on Symbolic and Algebraic Computation, ISSAC '13, pp. 117--124, New York, NY, USA, 2013. ISBN 978--1--4503--2059--7.

Digital Library

[6]

Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, and F. Rouillier. Improved algorithm for computing separating linear forms for bivariate systems. In Proc. 39th Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 75--82, 2014.

Digital Library

[7]

Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff. Improved algorithms for solving bivariate systems via Rational Univariate Representations. Tech. report, Inria, June 2015.

[8]

Y. Bouzidi, S. Lazard, M. Pouget, and F. Rouillier. Separating linear forms and rational univariate representations of bivariate systems. Journal of Symbolic Computation, 68, Part 1: 84 -- 119, 2015.

Digital Library

[9]

L. Busé. Resultants of determinantal varieties. Journal of Pure and Applied Algebra, 193 (1--3): 71 -- 97, 2004.

[10]

L. Busé, M. Elkadi, and B. Mourrain. Using projection operators in computer aided geometric design. Comtemporary Mathematics, 334: 321--342, 2003.

[11]

J. Canny. Some algebraic and geometric computations in PSPACE. In Proc. ACM STOC, pp. 460--467, 1988.

Digital Library

[12]

J. F. Canny, E. Kaltofen, and L. Yagati. Solving systems of nonlinear polynomial equations faster. In Proc. ACM ISSAC, pp. 121--128, 1989.

Digital Library

[13]

E. Cattani and A. Dickenstein. Solving Polynomial Equations: Foundations, Algorithms, and Applications, chapter Introduction to residues and resultants, pp. 1--61. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. ISBN 978--3--540--27357--8.

[14]

E. Cattani, M. A. Cueto, A. Dickenstein, S. Di Rocco, and B. Sturmfels. Mixed discriminants. Mathematische Zeitschrift, 274 (3): 761--778, 2013.

[15]

A. Chtcherba and D. Kapur. Resultants for unmixed bivariate polynomial systems produced using the Dixon formulation. Journal of Symbolic Computation, 38 (2): 915 -- 958, 2004.ISSN 0747--7171.

[16]

A. D. Chtcherba and D. Kapur. Conditions for exact resultants using the dixon formulation. In Proc. Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 62--70, 2000.

Digital Library

[17]

D. Cox and E. Materov. Tate resolutions for Segre embeddings. Algebra & Number Theory, 2 (5): 523--550, 2008.

[18]

C. D'Andrea. Macaulay style formulas for sparse resultants. Transactions of the American Mathematical Society, 354 (7): 2595--2629, 2002.

[19]

C. D'Andrea and A. Dickenstein. Explicit formulas for the multivariate resultant. J. Pure and Applied Algebra, 164 (1--2): 59--86, 2001.

[20]

C. D'Andrea and I. Z. Emiris. Hybrid sparse resultant matrices for bivariate systems. In Proc. of the 2001 Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 24--31, 2001.

Digital Library

[21]

A. Dickenstein and I. Z. Emiris. Multihomogeneous resultant formulae by means of complexes. Journal of Symbolic Computation, 36 (3): 317--342, 2003.

Digital Library

[22]

A. Dickenstein, I. Z. Emiris, and A. Karasoulou. phSAGA -- Advances in ShApes, Geometry, and Algebra Results from the Marie Curie Initial Training Network, chapter Plane Mixed Discriminants and Toric Jacobians, pp. 105--121. Springer Int'l Publishing, 2014. ISBN 978--3--319-08635--4.

[23]

M. Elkadi and A. Galligo. Systems of three polynomials with two separated variables. In Proc. Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 159--166, 2007.

Digital Library

[24]

I. Emiris and R. Vidunas. Root counts of semi-mixed systems, and an application to counting Nash equilibria. In Proc. ACM ISSAC, pp. 154--161, Kobe, Japan, 2014.

Digital Library

[25]

I. Z. Emiris and A. Karasoulou. Future Vision and Trends on Shapes, Geometry and Algebra, chapter Sparse Discriminants and Applications, pp. 55--71. Springer, London, 2014. ISBN 978--1--4471--6461--6.

[26]

I. Z. Emiris and A. Mantzaflaris. Multihomogeneous resultant formulae for systems with scaled support. Journal of Symbolic Computation, 47 (7): 820--842, 2012.

Digital Library

[27]

I. Z. Emiris and B. Mourrain. Matrices in elimination theory. Journal of Symbolic Computation, 28 (1): 3--44, 1999.

Digital Library

[28]

I. Z. Emiris and V. Y. Pan. Symbolic and numeric methods for exploiting structure in constructing resultant matrices. Journal of Symbolic Computation, 33 (4): 393--413, Apr. 2002.

Digital Library

[29]

I. Z. Emiris and V. Y. Pan. Improved algorithms for computing determinants and resultants. Journal of Complexity, 21 (1): 43--71, Feb. 2005.

Digital Library

[30]

I. Z. Emiris, A. Mantzaflaris, and E. Tsigaridas. On the bit complexity of solving bilinear polynomial systems. In Proc. Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 215--222, 2016.

Digital Library

[31]

A. Esterov. The discriminant of a system of equations. Advances in Mathematics, 245: 534 -- 572, 2013.

[32]

I. Gelfand, M. Kapranov, and A. Zelevinsky. Discriminants, Resultants and Multidimensional Determinants. Birkhauser, Boston, 1994.

[33]

R. Hartshorne. Algebraic Geometry. Springer, New York, 1977.

[34]

A. Khetan. The resultant of an unmixed bivariate system. Journal of Symbolic Computation, 36 (3--4): 425--442, 2003.

Digital Library

[35]

A. Khetan, N. Song, and R. Goldman. Sylvester A-resultants for bivariate polynomials with planar Newton polygons. In Proc. Int'l Symposium on Symbolic and Algebraic Computation, ISSAC, pp. 205--212, 2004.

Digital Library

[36]

F. S. Macaulay. Some formulæ in elimination. Proceedings of the London Mathematical Society, s1--35 (1): 3--27, 1902.

[37]

A. Mantzaflaris and B. Mourrain. Deflation and certified isolation of singular zeros of polynomial systems. In Proc. ACM ISSAC, pp. 249--256, 2011.

Digital Library

[38]

A. Mantzaflaris and B. Mourrain. Singular zeros of polynomial systems. In T. Dokken and G. Muntingh, editors, Advances in Shapes, Geometry, and Algebra, volume 10 of Geometry and Computing, pp. 77--103. Springer, 2014.

[39]

N. McCoy. On the resultant of a system of forms homogeneous in each of several sets of variables. Trans. AMS, 35 (1): 215--233, 1933.

[40]

A. McLennan. The maximum number of real roots of a multihomogeneous system of polynomial equations. Contributions to Algebra and Geometry, 40 (2): 343--350, 1999.

[41]

E. Miller and B. Sturmfels. Combinatorial commutative algebra, volume 227. Springer, 2004.

[42]

T. Muir. The resultant of a set of lineo-linear equations. Proc. Royal Soc. of South Africa, 2 (1): 373--380, 1910.

[43]

F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. Applicable Algebra in Engineering, Communication and Computing, 9 (5): 433--461, 1999.

[44]

H. Schenck, D. Cox, and A. Dickenstein. A case study in bigraded commutative algebra. Syzygies & Hilbert Functions, 254: 67--112, 2007.

[45]

B. Sturmfels and A. Zelevinsky. Multigraded resultants of Sylvester type. Journal of Algebra, 163 (1): 115--127, 1994.

[46]

J. Sylvester. On the degree and weight of the resultant of a multipartite system of equations. Proc. Royal Soc. of London, 12: 674--676, 1862.

[47]

J. Weyman. Calculating discriminants by higher direct images. Transactions of AMS, 343 (1): 367--389, 1994.

[48]

J. Weyman. Cohomology of Vector Bundles and Syzygies. Cambridge University Press, 2003. {Cambridge Tracts in Mathematics 149}.

[49]

J. Weyman and A. Zelevinsky. Determinantal formulas for multigraded resultants. Journal of Algebraic Geometry, 3 (4): 569--597, 1994.

[50]

M. Zhang and R. Goldman. Rectangular corner cutting and Sylvester A-resultants. In Proc. ACM ISSAC,%phProc. Int'l Symposium on Symbolic and Algebraic Computation, pp. 301--308, 2000.

Digital Library

Cited By

Yao SFeng YJia XShen L(2019)ISSAC 2019 software presentations communicated by Yue RenACM Communications in Computer Algebra10.1145/3371991.337199253:2(33-36)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371991.3371992
Bender MFaugère JMantzaflaris ATsigaridas EKauers MOvchinnikov ASchost É(2018)Bilinear Systems with Two SupportsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209011(63-70)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209011

Index Terms

Resultants and Discriminants for Bivariate Tensor-Product Polynomials
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms

Recommendations

Matrix formulæ for resultants and discriminants of bivariate tensor-product polynomials
Abstract
The construction of optimal resultant formulæ for polynomial systems is one of the main areas of research in computational algebraic geometry. However, most of the constructions are restricted to formulæ for unmixed polynomial systems, ...
A root isolation algorithm for sparse univariate polynomials
ISSAC '12: Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation

We consider a univariate polynomial f with real coefficients having a high degree N but a rather small number d + 1 of monomials, with d ≪ N. Such a sparse polynomial has a number of real root smaller or equal to d. Our target is to find for each real ...
On the Bit Complexity of Solving Bilinear Polynomial Systems
ISSAC '16: Proceedings of the 2016 ACM International Symposium on Symbolic and Algebraic Computation

We bound the Boolean complexity of computing isolating hyperboxes for all complex roots of systems of bilinear polynomials. The resultant of such systems admits a family of determinantal Sylvester-type formulas, which we make explicit by means of ...

Comments

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISSAC '17: Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation

July 2017

466 pages

ISBN:9781450350648

DOI:10.1145/3087604

Editor:
Michael Burr
Clemson University, USA
,
General Chair:
Chee K. Yap
New York University, USA
,
Program Chair:
Mohab Safey El Din
University Pierre et Marie Curie, France

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2017

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

ANR HPAC

Conference

ISSAC '17

ISSAC '17: International Symposium on Symbolic and Algebraic Computation

July 23 - 28, 2017

Kaiserslautern, Germany

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
49
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yao SFeng YJia XShen L(2019)ISSAC 2019 software presentations communicated by Yue RenACM Communications in Computer Algebra10.1145/3371991.337199253:2(33-36)Online publication date: 8-Nov-2019
https://dl.acm.org/doi/10.1145/3371991.3371992
Bender MFaugère JMantzaflaris ATsigaridas EKauers MOvchinnikov ASchost É(2018)Bilinear Systems with Two SupportsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209011(63-70)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209011

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten