skip to main content
10.1145/1005285.1005301acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Support hull: relating the cayley-dixon resultant constructions to the support of a polynomial system

Published: 04 July 2004 Publication History

Abstract

A geometric concept of the support hull of the support of a polynomial was used earlier by the authors for developing a tight upper bound on the size of the Cayley-Dixon resultant matrix for an unmixed polynomial system. The relationship between the support hull and the Cayley-Dixon resultant construction is analyzed in this paper. The support hull is shown to play an important role in the construction and analysis of resultant matrices based on the Cayley-Dixon formulation, similar to the role played by the associated convex hull (Newton polytope) for analyzing resultant matrices over the toric variety. For an unmixed polynomial system, the sizes of the resultant matrices (both dialytic as well as nondialytic) constructed using the Cayley-Dixon formulation are determined by the support hull of its support. Consequently, degree of the projection operator (which is in general, a nontrivial multiple of the resultant) computed from such a resultant matrix is determined by the support hull.The support hull of a given support is similar to its convex hull except that instead of the Euclidean distance, the support hull is defined using rectilinear distance. The concept of a support-hull interior point is introduced. It is proved that for an unmixed polynomial system, the size of the resultant matrix (both dialytic and nondialytic) based on the Cayley-Dixon formulation remains the same even if a term whose exponent is support-hull interior with respect to the support is generically added to the polynomial system. This key insight turned out to be instrumental in generalizing the concept of an unmixed polynomial system with a corner-cut support from 2 dimensions to arbitrary dimension as well as identifying an unmixed polynomial system with almost corner-cut support in arbitrary dimension.An algorithm for computing the size (and the lattice points) of the support hull of a given support is presented. It is proved that determining whether a given lattice point is not in the support hull, is NP-complete. A heuristic for computing a good variable ordering for constructing Dixon matrices for mixed as well as unmixed polynomial systems is proposed using the support hull and its projections. This is one of the first results on developing heuristics for variable orderings for constructing resultant matrices. A construction for a Sylvester-type resultant matrix based on the support hull of a polynomial system is also given.

References

[1]
D. Avis, D. Bremner, and R. Seidel. How good are convex hull algorithms. Computational Geometry: Theory and Applications, 7:265--302, 1997.
[2]
J. Canny and I. Emiris. A subdivision based algorithm for the sparse resultant. J. ACM, 2000.
[3]
E.-W. Chionh. Rectangular corner cutting and dixon A-resultants. Journal of Symbolic Computation, 31:651--663, 2001.
[4]
A. D. Chtcherba. A new Sylvester-type Resultant Method based on the Dixon- Bézout Formulation. PhD thesis, Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA, Jul 2003.
[5]
A. D. Chtcherba and D. Kapur. Conditions for Exact Resultants using the Dixon formulation. ISSAC00, pages 62--70, 2000.
[6]
A. D. Chtcherba and D. Kapur. Constructing Sylvester-type Resultant Matrices using the Dixon Formulation. Accepted for publication Journal of Symbolic Computation, 2003.
[7]
A. D. Chtcherba and D. Kapur. Exact resultants for corner-cut unmixed multivariate polynomial systems using the Dixon formulation. Journal of Symbolic Computation, 36(3--4):289--315, 2003.
[8]
A. D. Chtcherba and D. Kapur. Resultants for Unmixed Bivariate Polynomial Systems using the Dixon formulation. Accepted for publication in JSC, Dec. 2003.
[9]
A. D. Chtcherba and D. Kapur. On Relationship between the Dixon-based Resultant Construction and the Supports of Polynomial Systems. Technical Report Forthcomming, Computer Science Dept., Univ. of New Mexico, Albuquerque, New Mexico, USA, 2004.
[10]
A. Dixon. The eliminant of three quantics in two independent variables. Proc. London Mathematical Society, 6:468--478, 1908.
[11]
I. Emiris and J. Canny. Efficient incremental algorithms for the sparse resultant and the mixed volume. J. Symbolic Computation, 20(2):117--149, August 1995.
[12]
D. Kapur and T. Saxena. Comparison of various multivariate resultants. In ACM ISSAC 95, Montreal, Canada, July 1995.
[13]
D. Kapur and T. Saxena. Sparsity considerations in the Dixon resultant formulation. In Proc. ACM Symposium on Theory of Computing, Philadelphia, May 1996.
[14]
D. Kapur, T. Saxena, and L. Yang. Algebraic and geometric reasoning using the Dixon resultants. In ACM ISSAC 94, pages 99--107, Oxford, England, July 1994.
[15]
I. Shafarevich. Basic Algebraic Geometry. Spring-Verlag, New-York, second edition, 1994.
[16]
M. Zhang and R. Goldman. Rectangular Corner Cutting and Sylvester A-Resultants. In C. Traverso, editor, Proc. of the ISSAC, pages 301--308, St. Andrews, Scotland, Aug. 2000. ACM Press.

Index Terms

  1. Support hull: relating the cayley-dixon resultant constructions to the support of a polynomial system

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation
    July 2004
    334 pages
    ISBN:158113827X
    DOI:10.1145/1005285
    • General Chair:
    • Josef Schicho
    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 ACM 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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 04 July 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. dialytic method
    2. dixon resultant formulation
    3. resultant
    4. support
    5. support hull
    6. support-hull interior point
    7. sylvester-type matrices
    8. variable ordering

    Qualifiers

    • Article

    Conference

    ISSAC04
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 395 of 838 submissions, 47%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 210
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 15 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media