Article

Free access

Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions

Author:

Grégoire LecerfAuthors Info & Claims

ISSAC '00: Proceedings of the 2000 international symposium on Symbolic and algebraic computation

Pages 209 - 216

https://doi.org/10.1145/345542.345633

Published: 01 July 2000 Publication History

Abstract

Let ƒ₁, …, ƒ_s be polynomials in n variables over a field of characteristic zero and d be the maximum of their total degree. We propose a new probabilistic algorithm for computing a geometric resolution of each equidimensional part of the variety defined by the system ƒ₁ = ··· = ƒ_s = 0. The returned resolutions are encoded by means of Straight-Line Programs and the complexity of the algorithm is polynomial in a geometric degree of the system. In the worst case this complexity is asymptotically polynomial in sdⁿ.

References

[1]

J. Abdeljaoued. Algorithmes Rapides pour le Calcul d~ Polyn6me Caract~ristique. PhD thesis, Universit~ de Franche Comte, Besancon, France, 1997.

[2]

S. J. Berkowitz. On computing the determinant in small parallel time using a small number of processors Information Processing Letters, 18:147-150, 1984.

Digital Library

[3]

A. L. Chistov. Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic. Journal of Symbolic Computation, 22(1):1-25, July 1996.

Digital Library

[4]

A. L. Chistov. Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic. In A. M. Cohen and M.-F. Roy, editors, Proceedings of MEGA '96, volume 117-118 of Progress in Mathematics, pages 145-175. BirkhSuser, 1997.

[5]

A. L. Chistov and D. Y. Grigoriev. Subexponential time solving systems of algebraic equations. LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad 1983.

[6]

D. Castro, K. HSgele, J. E. Morais and L. M. Pardo. Kronecker and Newton approaches to solving: a first comparison. To appear in Journal of Complexity, 2000

Digital Library

[7]

M. Elkadi and B. Mourrain. A new algorithm for the geometric decomposition of a variety. In S. Dooley, editor, Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation. ACM, 1999.

Digital Library

[8]

N. Fitchas, M. Giusti, and F. Smietanski. Sur la complexit~ du th~or~me des z~ros. In J. Guddat, editor, Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation, volume 8 of Approximation and Optimization, pages 247-329. Peter Lange Verlag, Frankfurt am Main, 1995.

[9]

J. Gathen von zur. Parallel arithmetic computations: a survey. In B. R. J. Gruska and J. Wiedermann, editors, Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, volume 233 of LNCS, pages 93-112, Bratislava, Czechoslovakia, Aug. 1986. Springer.

Digital Library

[10]

M. Giusti, K. HSgele, J. Heintz, J. E. Morais, J. L. Montafia, and L. M. Pardo. Lower bounds for diophantine approximation. In A. M. Cohen and M.-F. Roy, editors, Proceedings of MEGA '96, volume 117-118 of Progress in Mathematics, pages 277-317. BirkhSuser, 1997.

[11]

M. Giusti, K. HSgele, G. Lecerf, J. Marchand, and B. Salvy. The projective Noether Maple package: Computing the dimension of a projective variety. To appear in Journal of Symbolic Computation, 2000.

Digital Library

[12]

M. Giusti and J. Heintz. Algorithmes- disons rapides - pour la d~composition d'une vari~t~ alg~brique en composantes irr~ductibles et ~quidimensionelles. In T. Mora and C. Traverso, editors, Proceedings of MEGA '90, volume 94 of Progress in Mathematics, pages 169-194. BirkhSuser, 1991.

[13]

M. Giusti and J. Heintz. La d~termination des points isol~s et de la dimension d'une vari~t~ alg~brique peut se faire en temps polynomial. In D. Eisenbud and L. Robbiano, editors, Computational Algebraic Geometry and Commutative Algebra, volume XXXIV of Symposia Matematica, pages 216-256. Cambridge University Press, 1993.

[14]

M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern, and L. M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101-146, 1998.

[15]

M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. When polynomial equation systems can be solved fast? In G. Cohen, M. Giusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC-11, Paris), volume 948 of Lecture Notes in Computer Science, pages 205-231. Springer, 1995.

Digital Library

[16]

M. Giusti, J. Heintz, J. E. Morais, and L. M. Pardo. Le r61e des structures de donn~es dans les probl~mes d'~limination. Comptes rendus de l'Acad~mie des sciences, 325:1223-1228, 1997.

[17]

M. Giusti, G. Lecerf, and B. Salvy. A GrSbner free alternative for polynomial system solving. To appear in Journal of Complexity, 2000.

Digital Library

[18]

K. HSgele, J. E. Morais, L. M. Pardo, and M. Sombra. On the intrinsic complexity of the arithmetic Nullstellensatz. Journal of Pure And Applied Algebra, 146(2):103-183, 2000.

[19]

J. Heintz. Definability and fast quantifier elimination in algebraically closed fields. Theoretical Computer Science, 24(3):239-277, 1983.

[20]

J. Heintz. On the computational complexity of polynomials and bilinear mappings. A survey. In Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5, volume 356 of LNCS, pages 269-300. Springer, 1989.

Digital Library

[21]

J. Heintz and C. P. Schnorr. Testing polynomials which are easy to compute. In Logic and Algorithmic, volume 30 of Monographie de l'Enseignement Math~matique, pages 237-254, 1982.

[22]

G. Jeronimo and J. Sabia. Effective equidimensional decomposition of afiqne varieties. Manuscript of Universidad de Buenos Aires, Argentina, 2000.

[23]

S. L. Kleiman. Bertini and his two fundamental theorems. In U. Bottazzini, editor, Rendiconti del circolo matematico di Palmero, Studies in the history of modern mathematics, pages 9-37, 1998.

[24]

T. Krick, L. Pardo, and M. Sombra. Sharp estimates for the arithmetic Nullstellensatz. Manuscript available at http://tera, med icis. polytech n iq ue.fr/tera/pub1999, htm I, December 1999.

[25]

T. Krick and L. M. Pardo. Une approche informatique pour l'approximation diophantienne. Comptes rendus de l'Acad~mie des sciences, 318(1):407-412, 1994.

[26]

(3. Lecerf. Kronecker version 0.1, July 1999. http: / / kro n ec ke r. med icis. polytec h n iq ue. fr/.

[27]

J. E. Morais. Resoluci6n eficaz de sistemas de ecuaciones polinomiales. PhD thesis, Universidad de Cantabria, Santander, Spain, 1997.

[28]

L. M. Pardo. How lower and upper complexity bounds meet in elimination theory. In (3. Cohen, M. (3iusti, and T. Mora, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes (AAECC-11, Paris), volume 948 of Lecture Notes in Computer Science, pages 33-69. Springer, Berlin, 1995.

Digital Library

[29]

P. Samuel. M~thodes d'alg~bre abstraite en g~om~trie alg~brique. Springer-Verlag, 2nd edition, 1967.

[30]

E. Schost. Computing parametric geometric resolutions. GAGE laboratory, manuscript, January 2000. http: / / www. gage. polytec h n iq ue. fr / not es / 2000. ht m l.

[31]

J. T. Schwartz. Probabilistic algorithms for verification of polynomial identities. In W. N. Edward, editor, Symbolic and Algebraic Computation (EUROSAM'79), volume 72 of Lecture Notes in Computer Science. Springer-Verlag, 1979.

Digital Library

[32]

V. Strassen. Berechnung und Programm. I, II. Acta Informatica, 1(4):320-355; ibid. 2(1), 64-79 (1973), 1972.

Digital Library

[33]

V. Strassen. Vermeidung von divisionen. Crelle J. Reine Angew. Math, 264:182-202, 1973.

[34]

N. Vorobjov. Complexity of computing the local dimension of a semialgebraic set. Journal of Symbolic Computation, 27(6):565-579, 1999.

Digital Library

[35]

R. Zippel. Probabilistic algorithms for sparse polynomials. In Proceedings EUROSAM' 79, number 72 in LNCS, pages 216-226. Springer, 1979.

Digital Library

[36]

R. Zippel. Effective Polynomial Computation. Kluwer Academic Publishers, 1993.

Cited By

Helmer MTsigaridas E(2024)Segre-driven radicality testingJournal of Symbolic Computation10.1016/j.jsc.2023.102262122(102262)Online publication date: May-2024
https://doi.org/10.1016/j.jsc.2023.102262
Eder CLairez PMohr RSafey El Din M(2023)A Direttissimo Algorithm for Equidimensional DecompositionProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597069(260-269)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597069
Eder CLairez PMohr RDin M(2022)Towards signature-based gröbner basis algorithms for computing the nondegenerate locus of a polynomial systemACM Communications in Computer Algebra10.1145/3572867.357287256:2(41-45)Online publication date: 23-Nov-2022
https://dl.acm.org/doi/10.1145/3572867.3572872
Show More Cited By

Index Terms

Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions
1. Computing methodologies
  1. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
      1. Algebraic algorithms
2. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis
      1. Computations on polynomials

Recommendations

Isolating the real roots of the piecewise algebraic variety

The piecewise algebraic variety, as a set of the common zeros of multivariate splines, is a kind of generalization of the classical algebraic variety. In this paper, we present an algorithm for isolating the zeros of the zero-dimensional piecewise ...
Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers

We present a new probabilistic method for solving systems of polynomial equations and inequations. Our algorithm computes the equidimensional decomposition of the Zariski closure of the solution set of such systems. Each equidimensional component is ...
Algebraic and Geometric Reasoning using Dixon Resultants

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISSAC '00: Proceedings of the 2000 international symposium on Symbolic and algebraic computation

July 2000

309 pages

ISBN:1581132182

DOI:10.1145/345542

Editor:
Carlo Traverso
Univ. di Pisa

Copyright © 2000 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 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

SIGSAM: ACM Special Interest Group on Symbolic and Algebraic Manipulation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2000

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISSAC00

Sponsor:

SIGSAM

ISSAC00: International Symposium on Symbolic and Algebraic Computation

St. Andrews, Scotland

Acceptance Rates

ISSAC '00 Paper Acceptance Rate 40 of 98 submissions, 41%;

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

22
Total Citations
View Citations
323
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Helmer MTsigaridas E(2024)Segre-driven radicality testingJournal of Symbolic Computation10.1016/j.jsc.2023.102262122(102262)Online publication date: May-2024
https://doi.org/10.1016/j.jsc.2023.102262
Eder CLairez PMohr RSafey El Din M(2023)A Direttissimo Algorithm for Equidimensional DecompositionProceedings of the 2023 International Symposium on Symbolic and Algebraic Computation10.1145/3597066.3597069(260-269)Online publication date: 24-Jul-2023
https://dl.acm.org/doi/10.1145/3597066.3597069
Eder CLairez PMohr RDin M(2022)Towards signature-based gröbner basis algorithms for computing the nondegenerate locus of a polynomial systemACM Communications in Computer Algebra10.1145/3572867.357287256:2(41-45)Online publication date: 23-Nov-2022
https://dl.acm.org/doi/10.1145/3572867.3572872
El Din MYang ZZhi L(2019)Computing real radicals and S-radicals of polynomial systemsJournal of Symbolic Computation10.1016/j.jsc.2019.10.018Online publication date: Nov-2019
https://doi.org/10.1016/j.jsc.2019.10.018
Henrion DNaldi SDin M(2019)Real root finding for low rank linear matricesApplicable Algebra in Engineering, Communication and Computing10.1007/s00200-019-00396-wOnline publication date: 25-Jul-2019
https://doi.org/10.1007/s00200-019-00396-w
Safey El Din MYang ZZhi LKauers MOvchinnikov ASchost É(2018)On the Complexity of Computing Real Radicals of Polynomial SystemsProceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation10.1145/3208976.3209002(351-358)Online publication date: 11-Jul-2018
https://dl.acm.org/doi/10.1145/3208976.3209002
Din MSchost É(2017)A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic SetsJournal of the ACM10.1145/299645063:6(1-37)Online publication date: 20-Jan-2017
https://dl.acm.org/doi/10.1145/2996450
Herrmann CZiegler M(2016)Computational Complexity of Quantum SatisfiabilityJournal of the ACM10.1145/286907363:2(1-31)Online publication date: 4-May-2016
https://dl.acm.org/doi/10.1145/2869073
Herrmann CSokoli JZiegler M(2013)Satisfiability of cross product terms is complete for real nondeterministic polytime Blum-Shub-Smale machinesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.128.16128(85-92)Online publication date: 4-Sep-2013
https://doi.org/10.4204/EPTCS.128.16
Safey El Din MSchost É(2011)A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real HypersurfaceDiscrete & Computational Geometry10.5555/3116270.311648745:1(181-220)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/3116270.3116487
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents