{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T09:16:38Z","timestamp":1776849398041,"version":"3.51.2"},"reference-count":61,"publisher":"Elsevier BV","issue":"4","license":[{"start":{"date-parts":[[2003,8,1]],"date-time":"2003-08-01T00:00:00Z","timestamp":1059696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3674,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Complexity"],"published-print":{"date-parts":[[2003,8]]},"DOI":"10.1016\/s0885-064x(03)00031-1","type":"journal-article","created":{"date-parts":[[2003,5,19]],"date-time":"2003-05-19T18:04:16Z","timestamp":1053367456000},"page":"564-596","source":"Crossref","is-referenced-by-count":68,"title":["Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers"],"prefix":"10.1016","volume":"19","author":[{"given":"Gr\u00e9goire","family":"Lecerf","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0885-064X(03)00031-1_BIBAHU74","series-title":"The Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBBP94","series-title":"Polynomial and Matrix Computations, Progress in Theoretical Computer Science","author":"Bini","year":"1994"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBBC95","series-title":"Handbook of Magma Functions, School of Mathematics and Statistics","author":"Bosma","year":"1995"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBBCM94","series-title":"Proceedings of ISSAC\u201994","article-title":"Programming with algebraic structures: design of the Magma language","author":"Bosma","year":"1994"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBBCP97","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system I","volume":"24","author":"Bosma","year":"1997","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBBCS97","series-title":"Algebraic Complexity Theory","author":"B\u00fcrgisser","year":"1997"},{"issue":"1","key":"10.1016\/S0885-064X(03)00031-1_BIBCP96","first-page":"113","article-title":"Magma","volume":"2","author":"Cannon","year":"1996","journal-title":"Euromath Bull."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBCAS01","unstructured":"D. Castro, Sobre la complejidad de la representaci\u00f3n de variedades algebraicas, Ph.D. Thesis, Universidad de Cantabria, Departemento de Matem\u00e1ticas, Estad\u0131\u0301stica y Computaci\u00f3n, Santander, Spain, July 2001."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBCGH02","doi-asserted-by":"crossref","unstructured":"D. Castro, M. Giusti, J. Heintz, G. Matera, L.M. Pardo, The hardness of polynomial equation solving, Found. Comput. Math. doi: 10.1007\/S10208-002-0065-7.","DOI":"10.1007\/s10208-002-0065-7"},{"issue":"1","key":"10.1016\/S0885-064X(03)00031-1_BIBCHMP01","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1006\/jcom.2000.0572","article-title":"Kronecker's and Newton's approaches to solving","volume":"17","author":"Castro","year":"2001","journal-title":"J. Complexity"},{"issue":"1","key":"10.1016\/S0885-064X(03)00031-1_BIBCHI96","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jsco.1996.0039","article-title":"Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic","volume":"22","author":"Chistov","year":"1996","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBCHI97","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0022-4049(97)00009-1","article-title":"Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic","volume":"117\u2013118","author":"Chistov","year":"1997","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBCG83","unstructured":"A.L. Chistov, D.Y. Grigoriev, Subexponential time solving systems of algebraic equations, LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad, 1983."},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBCW90","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","year":"1990","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBDST87","series-title":"Calcul formel. Syst\u00e8mes, algorithmes de manipulations alg\u00e9briques","author":"Davenport","year":"1987"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBEM99","doi-asserted-by":"crossref","unstructured":"M. Elkadi, B. Mourrain, A new algorithm for the geometric decomposition of a variety, in: Proceedings of ISSAC\u201999, ACM, New York, 1999.","DOI":"10.1145\/309831.309843"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBFUL84","doi-asserted-by":"crossref","unstructured":"W. Fulton, Intersection Theory, 2nd Edition, Ergebnisse der Mathematik, No. 3, Springer, Berlin, 1984.","DOI":"10.1007\/978-3-662-02421-8"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGG99","series-title":"Modern Computer Algebra","author":"von zur Gathen","year":"1999"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGH91","series-title":"Proceedings of MEGA\u201990","first-page":"169","article-title":"Algorithmes - disons rapides - pour la d\u00e9composition d'une vari\u00e9t\u00e9 alg\u00e9brique en composantes irr\u00e9ductibles et \u00e9quidimensionelles","volume":"Vol. 94","author":"Giusti","year":"1991"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGH93","series-title":"Computational Algebraic Geometry and Commutative Algebra","first-page":"216","article-title":"La d\u00e9termination des points isol\u00e9s, de la dimension d'une vari\u00e9t\u00e9 alg\u00e9brique peut se faire en temps polynomial","volume":"Vol. XXXIV","author":"Giusti","year":"1993"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGH01","doi-asserted-by":"crossref","unstructured":"M. Giusti, J. Heintz, Kronecker's smart, little black-boxes, in: A. Iserles, R. DeVore (Eds.), Proceedings of Foundations of Computational Mathematics, London Mathematical Society Lecture Notes Series, Vol. 284, pp. 69\u2013104, Oxford 1999, Cambridge University Press, 2001.","DOI":"10.1017\/CBO9781107360198.005"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGHH97","doi-asserted-by":"crossref","unstructured":"M. Giusti, K. H\u00e4gele, J. Heintz, J.E. Morais, J.L. Monta\u00f1a, L.M. Pardo, Lower bounds for Diophantine approximation, in: Proceedings of MEGA\u201996, J. Pure Appl. Algebra 117, 118 (1997) 277\u2013317.","DOI":"10.1016\/S0022-4049(97)00015-7"},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBGHL00","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1006\/jsco.2000.0369","article-title":"Computing the dimension of a projective variety","volume":"30","author":"Giusti","year":"2000","journal-title":"J. Symbolic Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGHM98","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/S0022-4049(96)00099-0","article-title":"Straight-line programs in geometric elimination theory","volume":"124","author":"Giusti","year":"1998","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGHMP95","series-title":"Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11","first-page":"205","article-title":"When polynomial equation systems can be solved fast?","volume":"Vol. 948","author":"Giusti","year":"1995"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGHMP97","doi-asserted-by":"crossref","first-page":"1223","DOI":"10.1016\/S0764-4442(97)83558-6","article-title":"Le r\u00f4le des structures de donn\u00e9es dans les probl\u00e8mes d\u2019\u00e9limination","volume":"325","author":"Giusti","year":"1997","journal-title":"C. R. Acad. Sci. Paris"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBGKZ94","series-title":"Discriminants, Resultants and Multidimensional Determinants","author":"Gel'fand","year":"1994"},{"issue":"1","key":"10.1016\/S0885-064X(03)00031-1_BIBGLS01","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1006\/jcom.2000.0571","article-title":"A Gr\u00f6bner free alternative for polynomial system solving","volume":"17","author":"Giusti","year":"2001","journal-title":"J. Complexity"},{"issue":"2","key":"10.1016\/S0885-064X(03)00031-1_BIBHMPS00","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0022-4049(98)00148-0","article-title":"On the intrinsic complexity of the arithmetic Nullstellensatz","volume":"146","author":"H\u00e4gele","year":"2000","journal-title":"J. Pure Appl. Algebra"},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBHEI83","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0304-3975(83)90002-6","article-title":"Definability and fast quantifier elimination in algebraically closed fields","volume":"24","author":"Heintz","year":"1983","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/S0885-064X(03)00031-1_BIBHMW01","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s002000000046","article-title":"On the time-space complexity of geometric elimination procedures","volume":"11","author":"Heintz","year":"2001","journal-title":"Appl. Algebra Eng. Comm. Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBJKSS02","unstructured":"G. Jeronimo, T. Krick, J. Sabia, M. Sombra, The computational complexity of the Chow form, Manuscript, March 2002."},{"issue":"1","key":"10.1016\/S0885-064X(03)00031-1_BIBJPS01","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1006\/jagm.2001.1177","article-title":"Computing Chow forms and some applications","volume":"41","author":"Jeronimo","year":"2001","journal-title":"J. Algorithms"},{"issue":"6","key":"10.1016\/S0885-064X(03)00031-1_BIBJS00","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/S0764-4442(00)01659-1","article-title":"Probabilistic equidimensional decomposition","volume":"331","author":"Jeronimo","year":"2000","journal-title":"C. R. Acad. Sci. Paris"},{"issue":"2\u20133","key":"10.1016\/S0885-064X(03)00031-1_BIBJS02","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0022-4049(01)00083-4","article-title":"Effective equidimensional decomposition of affine varieties","volume":"169","author":"Jeronimo","year":"2002","journal-title":"J. Pure Appl. Algebra"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBKOI97","doi-asserted-by":"crossref","unstructured":"P. Koiran, Randomized and deterministic algorithms for the dimension of algebraic varieties. in: Proceedings of the 38th Annual IEEE Computer Society Conference on Foundations of Computer Science (FOCS), ACM, New York, 1997.","DOI":"10.1109\/SFCS.1997.646091"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBKP96","series-title":"Algorithms in Algebraic Geometry and Applications, Proceedings of MEGA\u201994","first-page":"193","article-title":"A computational method for Diophantine approximation","volume":"Vol. 143","author":"Krick","year":"1996"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBLEC99","unstructured":"G. Lecerf, Kronecker, a Magma package for polynomial system solving, from 1999, http:\/\/kronecker.medicis.polytechnique.fr."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBLEC00","doi-asserted-by":"crossref","unstructured":"G. Lecerf, Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions, in: Proceedings of ISSAC\u20192000, ACM, New York, 2000, pp. 209\u2013216.","DOI":"10.1145\/345542.345633"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBLEC01","unstructured":"G. Lecerf, Une alternative aux m\u00e9thodes de r\u00e9\u00e9criture pour la r\u00e9solution des syst\u00e8mes alg\u00e9briques, Ph.D. Thesis, \u00c9cole polytechnique, Palaiseau, France, 2001."},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBLEC02","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/s102080010026","article-title":"Quadratic Newton iteration for systems with multiplicity","volume":"2","author":"Lecerf","year":"2002","journal-title":"Found. Comput. Math."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBLS01","unstructured":"G. Lecerf, \u00c9. Schost, Fast multivariate power series multiplication in characteristic zero, SADIO Electron. J. Informatics Oper. Res., to appear. Manuscript available at http:\/\/www.math.uvsq.fr\/~lecerf."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBMAG","unstructured":"Magma, http:\/\/magma.maths.usyd.edu.au."},{"issue":"6","key":"10.1016\/S0885-064X(03)00031-1_BIBMAT99","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/s002000050115","article-title":"Probabilistic algorithms for geometric elimination","volume":"9","author":"Matera","year":"1999","journal-title":"Appl. Algebra Eng. Comm. Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBMAT86","series-title":"Commutative ring theory","author":"Matsumura","year":"1986"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBMOR97","unstructured":"J.E. Morais, Resoluci\u00f3n eficaz de sistemas de ecuaciones polinomiales, Ph.D. Thesis, Universidad de Cantabria, Santander, Spain, 1997."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBMUM95","series-title":"Algebraic Geometry I\u2014Complex Projective Varieties","author":"Mumford","year":"1995"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBPAR95","series-title":"Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-5","first-page":"33","article-title":"How lower and upper complexity bounds meet in elimination theory","volume":"Vol. 948","author":"Pardo","year":"1995"},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBPS78","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/0020-0190(78)90079-0","article-title":"An improved parallel processor bound in fast matrix inversion","volume":"7","author":"Preparata","year":"1978","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBROJ00","unstructured":"M. Rojas, Computing complex dimension faster and deterministically, Manuscript of City University of Hong Kong, 2000."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSAM67","series-title":"M\u00e9thodes d'alg\u00e8bre abstraite en g\u00e9om\u00e9trie alg\u00e9brique","author":"Samuel","year":"1967"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSCH00","unstructured":"\u00c9. Schost, Sur la r\u00e9solution des syst\u00e8mes polynomiaux \u00e0 param\u00e8tres, Ph.D. Thesis, \u00c9cole polytechnique, Palaiseau, France, 2000."},{"issue":"5","key":"10.1016\/S0885-064X(03)00031-1_BIBSCH01","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/s00200-002-0109-x","article-title":"Computing parametric geometric resolutions","volume":"13","author":"Schost","year":"2003","journal-title":"Appl. Algebra Eng. Comm. Comput."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSCH02","series-title":"Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation","first-page":"235","article-title":"Degree bounds and lifting techniques for triangular sets","author":"Schost","year":"2002"},{"issue":"3","key":"10.1016\/S0885-064X(03)00031-1_BIBSV00","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1006\/jcom.2000.0554","article-title":"Numerical homotopies to compute generic points on positive dimensional algebraic sets","volume":"16","author":"Sommese","year":"2000","journal-title":"J. Complexity"},{"issue":"6","key":"10.1016\/S0885-064X(03)00031-1_BIBSVW01A","doi-asserted-by":"crossref","first-page":"2022","DOI":"10.1137\/S0036142900372549","article-title":"Numerical decomposition of the solution sets of polynomial systems into irreducible components","volume":"38","author":"Sommese","year":"2001","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSVW01B","series-title":"Symbolic Computation: Solving Equations in Algebra, Geometry, and Engineering","article-title":"Numerical irreducible decomposition using projection from points on the components","volume":"Vol. 286","author":"Sommese","year":"2001"},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSVW01C","series-title":"Application of Algebraic Geometry to Coding Theory, Physics, and Computation, Proceedings of NATO Conference 2001","article-title":"Using monodromy to decompose solution sets of polynomial systems into irreducible components","author":"Sommese","year":"2001"},{"issue":"6","key":"10.1016\/S0885-064X(03)00031-1_BIBSVW02","doi-asserted-by":"crossref","first-page":"2026","DOI":"10.1137\/S0036142901397101","article-title":"Symmetric functions applied to decomposing solution sets of polynomial systems","volume":"40","author":"Sommese","year":"2002","journal-title":"SIAM J. Numer. Anal."},{"key":"10.1016\/S0885-064X(03)00031-1_BIBSTU94","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1023\/A:1022497624378","article-title":"On the Newton polytope of the resultant","volume":"3","author":"Sturmfels","year":"1994","journal-title":"J. Algebraic Combin."},{"issue":"6","key":"10.1016\/S0885-064X(03)00031-1_BIBVOR99","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1006\/jsco.1999.0282","article-title":"Complexity of computing the local dimension of semialgebraic set","volume":"27","author":"Vorobjov","year":"1999","journal-title":"J. Symbol. Comput."}],"container-title":["Journal of Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X03000311?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0885064X03000311?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,21]],"date-time":"2019-03-21T10:50:20Z","timestamp":1553165420000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0885064X03000311"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,8]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2003,8]]}},"alternative-id":["S0885064X03000311"],"URL":"https:\/\/doi.org\/10.1016\/s0885-064x(03)00031-1","relation":{},"ISSN":["0885-064X"],"issn-type":[{"value":"0885-064X","type":"print"}],"subject":[],"published":{"date-parts":[[2003,8]]}}}