On the time-space complexity of geometric elimination procedures
In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new ge...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2001
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 16486caa a22013337a 4500 | ||
|---|---|---|---|
| 001 | PAPER-2031 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203122.0 | ||
| 008 | 190411s2001 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-0035060036 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a AAECE | ||
| 100 | 1 | |a Heintz, J. | |
| 245 | 1 | 3 | |a On the time-space complexity of geometric elimination procedures |
| 260 | |c 2001 | ||
| 270 | 1 | 0 | |m Matera, G.; Departamento de Computación, Universidad Favaloro, Belgrano 1723 (1093) Buenos Aires, Argentina; email: gmater@favaloro.edu.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Abdeljaoued, J., Algorithmes rapides pour le Calcul du Polynôme Caractéristique (1997), PhD thesis, Université de Franche Compte, Besançon, France; Alonso, M.E., Becker, E., Roy, M.-F., Wörmann, T., Zeroes, multiplicities and idempotents for zerodimensional systems (1996) Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA'94, 142, pp. 1-15. , of Progress in Mathematics; Basel: Birkhäuser | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties, real equation solving and data structures: The hypersurface case (1997) J. Complexity, 13 (1), pp. 5-27 | ||
| 504 | |a Bank, B., Giusti, M., Heintz, J., Mbakop, G.M., Polar varieties and efficient real elimination (2001) Math. Zeitschrift | ||
| 504 | |a Bini, D., Pan, V., Polynomial and matrix computations (1994) Progress in Theoretical Computer Science, , Boston-Basel-Berlin: Birkhäuser | ||
| 504 | |a Borodin, A., On relating time and space to size and depth (1977) SIAM J. Comput., 6, pp. 733-744 | ||
| 504 | |a Borodin, A., Time space tradeoffs (getting closer to the barrier?) (1993) Algorithms and Computation, Proceedings 4th ISAAC, Vol. 762 of Lecture Notes in Computer Science, pp. 209-220. , Berlin Heidelberg New York: Springer | ||
| 504 | |a Borodin, A., Munro, J., The computational complexity of algebraic and numeric problems (1972), Amsterdam: Elsevier; Brownawell, D.W., Bounds for the degree in the Nullstellensatz (1987) Ann. Math., 126, pp. 577-591 | ||
| 504 | |a Buchberger, B., Gröbner bases: An algoritmic method in polynomial ideal theory (1985) Multidimensional System Theory, pp. 374-383. , In: Bose, N. K., et al. (eds.); Dordrecht: Reidel | ||
| 504 | |a Bürgisser, P., Clausen, M., Amin Shokrollahi, M., (1997) Algebraic Complexity Theory, Vol. 315 of Grundlehren der Mathematischen Wissenschaften, , Berlin Heidelberg New York: Springer | ||
| 504 | |a Caniglia, L., How to compute the Chow Form of an unmixed Polynomial Ideal in Single Exponential Time (1990) AAECC, 1 (1), pp. 25-41 | ||
| 504 | |a Caniglia, L., Galligo, A., Heintz, J., Some new effectivity bounds in computational geometry (1989) Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings of AAECC-6, Vol. 357 of LNCS, pp. 131-152. , In: Mora, T., et al. (eds.); Berlin Heidelberg New York: Springer | ||
| 504 | |a Canny, J., Some algebraic and geometric problems in PSPACE (1988) Proceedings 20th ACM STOC, pp. 460-467 | ||
| 504 | |a Chistov, A.L., Grigoriev, D.Y., Subexponential time solving systems of algebraic equations (1983), LOMI preprint E-9-83, E-10-83, Steklov Institute, Leningrad; Collins, G.E., Subresultants and reduced polynomial sequences (1967) J. ACM, 14, pp. 128-142 | ||
| 504 | |a Dickenstein, A., Fitchas, N., Giusti, M., Sessa, C., The membership problem for unmixed polynomial ideals is solvable in single exponential time (1991) Discrete Appl. Math., 33, pp. 73-94 | ||
| 504 | |a Faddeev, D.K., Faddeeva, V.N., Computational methods of linear algebra (1963), San Francisco: Freeman; Fitchas, N., Galligo, A., Nullstellensatz effectif et Conjecture de Serre (Théorème de Quillen-Suslin) pour le calcul formel (1990) Math. Nachr., 149, pp. 231-253 | ||
| 504 | |a Fitchas, N., Giusti, M., Smietanski, F., Sur la complexité du théorème des zéros (1995) Approximation and Optimization in the Caribbean II, Proceedings 2nd Int. Conf. on Non-Linear Optimization and Approximation, Volume 8 of Approximation and Optimization, pp. 247-329. , In: Guddat, J., et al. (eds.); Frankfurt am Main: Peter Lange Verlag | ||
| 504 | |a Fulton, W., (1984) Intersection Theory, Vol. 3 of Ergebnisse der Mathematik, , Berlin Heidelberg New York: Springer | ||
| 504 | |a Giusti, M., Hägele, K., Heintz, J., Morais, J.E., Montaña, J.L., Pardo, L.M., Lower bounds for diophantine approximation (1997) J. Pure. Appl. Algebra, 117-118, pp. 277-317 | ||
| 504 | |a Giusti, M., Hägele, K., Lecerf, G., Marchand, J., Salvy, B., The Projective Noether Maple Package: Computing the dimension of a projective variety (2000) J. Sym. Comput., 30 (3), pp. 291-307 | ||
| 504 | |a Giusti, M., Heintz, J., La détermination des points isolés et de la dimension d'une variété algébrique peut se faire en temps polynomial (1993) Computational Algebraic Geometry and Commutative Algebra, Volume XXXIV of Symposia Matematica, pp. 216-256. , In: Eisenbud, D., Robbiano, L. (eds.); Cambridge University Press | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Morgenstern, J., Pardo, L.M., Straight-line programs in geometric elimination theory (1998) J. Pure. Appl. Algebra, 124, pp. 101-146 | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., When polynomial equation systems can be solved fast? (1995) Applied Algebra, Algebraic Algorithms and Error Correcting Codes, Proceedings AAECC-11, Vol. 948 of LNCS, pp. 205-231. , In: Cohen, G., Giusti, H., Mora, T. (eds.); Berlin Heidelberg New York: Springer | ||
| 504 | |a Giusti, M., Heintz, J., Morais, J.E., Pardo, L.M., Le rôle des structures de données dans les problèmes d'élimination (1997) Comptes Rendus de l'Académie de Sciences de Paris, 325, pp. 1223-1228 | ||
| 504 | |a Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective Nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95 | ||
| 504 | |a Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity | ||
| 504 | |a Gianni, P., Mora, T., Algebraic solution of systems of polynomial equations using Gröbner Bases (1989) Proceedings AAECC-5, Vol. 356 of LNCS, pp. 247-257. , Berlin Heidelberg New York: Springer | ||
| 504 | |a Gonzalez-Vega, L., Rouillier, F., Roy, M.-F., Symbolic recipes for polynomial system solving (1997) Some Tapas of Computer Algebra, pp. 34-65. , Berlin Heidelberg New York: Springer | ||
| 504 | |a Hägele, K., Intrinsic height estimates for the Nullstellensatz (1998), PhD thesis, Universidad de Cantabria, Santander, Spain; Hägele, K., Morais, J.E., Pardo, L.M., Sombra, M., On the intrinsic complexity of the arithmetic Nullstellensatz (2000) J. Pure Appl. Algebra, 146, pp. 103-183 | ||
| 504 | |a Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theor. Comput. Sci., 24 (3), pp. 239-277 | ||
| 504 | |a Heintz, J., On the computational complexity of polynomials and bilinear mappings. A survey (1989) Proceedings AAECC-5, Vol. 356 of Lecture Notes in Computer Science, pp. 269-300. , Berlin Heidelberg New York: Springer | ||
| 504 | |a Heintz, J., Krick, T., Puddu, S., Sabia, J., Waissbein, A., Deformation techniques for efficient polynomial equation solving (2000) J. Complexity, 16 (1), pp. 70-109 | ||
| 504 | |a Heintz, J., Matera, G., Pardo, L.M., Wachenchauzer, R., The intrinsic complexity of parametric elimination methods (1998) Electronic Journal of SADIO, 1 (1), pp. 37-51 | ||
| 504 | |a Ja'Ja', J., Time-space tradeoffs for some algebraic problems (1983) J. ACM, 30 (3), pp. 657-667 | ||
| 504 | |a Kaltofen, E., Asymptotically fast solution of Toeplitz-like singular linear systems (1994) Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation, ISSAC'94 (Oxford, July 20-22 1994), pp. 297-304. , In: Von zur Gathen, J., Giesbrecht, M. (eds.); New York: ACM Press | ||
| 504 | |a Kobayashi, H., Fujise, T., Furukawa, A., Solving systems of algebraic equations by general elimination method (1988) J. Symb. Comput., 5, pp. 303-320 | ||
| 504 | |a Krick, T., Pardo, L.M., Une approche informatique pour l' approximation diophantienne (1994) C. R. Acad. Sci. Paris, 318 (1), pp. 407-412 | ||
| 504 | |a Krick, T., Pardo, L.M., A computational method for diophantine approximation (1996) Algorithms in Algebraic Geometry and Applications. Proceedings of MEGA'94, Vol. 143 of Progress in Mathematics, pp. 193-254. , In: González-Vega, L., Recio, T. (eds.); Basel: Birkhäuser | ||
| 504 | |a Kronecker, L., Grundzüge einer Arithmetischen Theorie de Algebraischen Grössen (1882) J. Reine Angew. Math., 92, pp. 1-122 | ||
| 504 | |a Kühnle, K., Space optimal computation of normal forms of polynomials (1998), PhD thesis, Technischen Universität München, München, Germany; Kühnle, K., Mayr, E., Exponential space computation of Gröbner bases (1996) Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC'96 (Zürich, 24-26 July 1996) Vol. 358 of ACM Press, 358, pp. 63-71. , New York: ACM | ||
| 504 | |a Macaulay, F.S., The algebraic theory of modular systems (1916), Cambridge University Press; Matera, G., Sobre la complejidad en espacio y tiempo de la eliminación geométrica (1997), PhD thesis, Universidad de Buenos Aires, Argentina; Matera, G., Probabilistic algorithms for geometric elimination (1999) AAECC, 9 (6), pp. 476-521 | ||
| 504 | |a Matera, G., Turull Torres, J.M., The space complexity of elimination: Upper bounds (1997) Proceedings Foundations of Computational Mathematics (FOCM'97), pp. 267-276. , In: Cucker, F., Shub, M. (eds.); Berlin Heidelberg New York: Springer 1977 | ||
| 504 | |a Mayr, E., Membership in polynomial ideals over Q is exponential space complete (1989) Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS'89), Paderborn (FRG) 1989, Vol. 349 in Lecture Notes in Computer Science, pp. 400-406. , In: Monien, B., et al. (eds.); Berlin Heidelberg New York: Springer | ||
| 504 | |a Mayr, E., Meyer, A., The complexity of the word problem for commutative semigroups (1982) Adv. Math., 46, pp. 305-329 | ||
| 504 | |a Morais, J.E., Resolución eficaz de sistemas de ecuaciones polinomiales (1997), PhD thesis, Universidad de Cantabria, Santander, Spain; Pardo, L.M., How lower and upper complexity bounds meet in elimination theory (1995) Applied Algebra, Algebraic Algorithms and Error Correcting Codes. Proceedings of AAECC-11, Vol. 948 of Lecture Notes in Computer Science, , In: Cohen, G., Giusti, H., Mora, T. (eds.); Berlin Heidelberg New York: Springer | ||
| 504 | |a Rouillier, F., Solving zero-dimensional systems throught rational univariate representation (1997) AAECC, 9 (5), pp. 433-461 | ||
| 504 | |a Sabia, J., Solernó, P., Bounds for traces in complete intersections and degrees in the Nullstellensatz (1996) AAECC, 6 (6), pp. 353-376 | ||
| 504 | |a Schönhage, A., Grotefeld, F.W., Vetter, E., Fast algorithms: A multitape turing machine implementation (1994), Manntein: B.I. Wissenschaftsverlag; Schwartz, J.T., Fast probabilistic algorithms for verification of polynomial identities (1980) J. ACM, 27 (4), pp. 701-717 | ||
| 504 | |a Sendra, J.R., Algoritmos simbólicos de Hankel en álgebra computacional (1990), PhD thesis, Universidad de Alcalá de Henares, Madrid, Spain; Sendra, R., Llovet, J., An extended polynomial gcd algorithm using Hankel matrices (1992) J. Symbol. Comput., 13, pp. 25-39 | ||
| 504 | |a Shafarevich, I.R., Basic algebraic geometry (1974), Berlin Heidelberg: Springer; Sieveking, M., An algorithm for division of power series (1972) Computing, 10, pp. 153-156 | ||
| 504 | |a Sombra, M., Estimaciones para el Teorema de Ceros de Hilbert (1998), PhD thesis, Universidad de Buenos Aires, Argentina; Stoß, H.-J., Lower bounds for the complexity of polynomials (1989) Theor. Comput. Sci., 64, pp. 15-23 | ||
| 504 | |a Strassen, V., Vermeidung von Divisionen (1973) Crelle J. Reine Angew. Math., 264, pp. 182-202 | ||
| 504 | |a Strassen, V., Algebraic complexity theory (1990) Handbook of Theoretical Computer Science, Chapter 11, pp. 634-671. , Amsterdam: Elsevier | ||
| 504 | |a Van Der Waerden, B.L., (1931) Moderne Algebra II, , Berlin: Springer | ||
| 504 | |a Von Zur Gathen, J., Parallel arithmetic computations: A survey (1986) Proceedings of the 12th Symposium on Mathematical Foundations of Computer Science, Vol. 233 of LNCS, pp. 93-112. , In: Rovan, B., Gruska, J., Wiedermann, J. (eds.); Bratislava, Czechoslovakia, August. Berlin Heidelberg New York: Springer | ||
| 504 | |a Von Zur Gathen, J., Parallel linear algebra (1993) Synthesis of Parallel Algorithms, , In: Reif, J. H. (ed.); Los Altas, CA: Morgan Kaufmann | ||
| 504 | |a Wadler, P., Deforestation: Transforming programs to eliminate trees (1990) Theor. Comput. Sci., 73, pp. 231-248. , (Special issue of selected papers from 2nd ESOP) | ||
| 504 | |a Zariski, O., Algebraic surfaces. Classics in mathematics (1995), Berlin Heidelberg New York: Springer; Zippel, R., Probabilistic algorithms for sparse polynomials (1979) Proceedings EUROSAM'79, Vol. 72 of LNCS, pp. 216-226 | ||
| 504 | |a Zippel, R., Effective polynomial computation (1993), ECS 241. Dordrecht: Kluwer Academic Publishers | ||
| 520 | 3 | |a In [25] and [22] a new algorithmic concept was introduced for the symbolic solution of a zero dimensional complete intersection polynomial equation system satisfying a certain generic smoothness condition. The main innovative point of this algorithmic concept consists in the introduction of a new geometric invariant, called the degree of the input system, and the proof that the most common elimination problems have time complexity which is polynomial in this degree and the length of the input. In this paper we apply this algorithmic concept in order to exhibit an elimination procedure whose space complexity is only quadratic and its time complexity is only cubic in the degree of the input system. |l eng | |
| 593 | |a Departamento de Matemáticas, Estadística y Computación, Facultad de Ciencias, Universidad de Cantabria, Avda. de Los Castros s/n, E-39071 Santander, Spain | ||
| 593 | |a Departamento de Matemáticas, Facultad de Ciencias Exactas y Naturales, Ciudad Universitaria, Pabellón I, (1428) Buenos Aires, Argentina | ||
| 593 | |a CONICET (Consejo Nacional de Investigaciones Cientí Ficas y Técnicas), Argentina, Argentina | ||
| 593 | |a Departamento de Computación, Universidad Favaloro, Belgrano 1723, (1093) Buenos Aires, Argentina | ||
| 593 | |a Instituto de Desarrollo Humano, Universidad Nacional de General Sarmiento, Roca 850, (1663) San Miguel, Argentina | ||
| 690 | 1 | 0 | |a ALGEBRAIC COMPLEXITY THEORY |
| 690 | 1 | 0 | |a ALGORITHMIC ELIMINATION THEORY |
| 690 | 1 | 0 | |a COMPUTATION TREE |
| 690 | 1 | 0 | |a POLYNOMIAL EQUATION SOLVING |
| 690 | 1 | 0 | |a STRAIGHT-LINE PROGRAM |
| 690 | 1 | 0 | |a SYMBOLIC COMPUTATION |
| 690 | 1 | 0 | |a TIME-SPACE COMPLEXITY |
| 690 | 1 | 0 | |a ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a MATHEMATICAL MODELS |
| 690 | 1 | 0 | |a MATHEMATICAL PROGRAMMING |
| 690 | 1 | 0 | |a MATRIX ALGEBRA |
| 690 | 1 | 0 | |a POLYNOMIALS |
| 690 | 1 | 0 | |a THEOREM PROVING |
| 690 | 1 | 0 | |a TREES (MATHEMATICS) |
| 690 | 1 | 0 | |a ALGEBRAIC COMPLEXITY THEORY |
| 690 | 1 | 0 | |a ALGORITHMIC ELIMINATION THEORY |
| 690 | 1 | 0 | |a COMPUTATION TREE |
| 690 | 1 | 0 | |a GEOMETRIC ELIMINATION PROCEDURES |
| 690 | 1 | 0 | |a STRAIGHT LINE PROGRAM |
| 690 | 1 | 0 | |a SYMBOLIC COMPUTATION |
| 690 | 1 | 0 | |a TIME SPACE COMPLEXITY |
| 690 | 1 | 0 | |a GEOMETRY |
| 700 | 1 | |a Matera, G. | |
| 700 | 1 | |a Waissbein, A. | |
| 773 | 0 | |d 2001 |g v. 11 |h pp. 239-296 |k n. 4 |p Appl Algebra Eng Commun Comput |x 09381279 |t Applicable Algebra in Engineering, Communications and Computing | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-0035060036&doi=10.1007%2fs002000000046&partnerID=40&md5=8835a4b0f6e0aeebf4de5ea35bf89569 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s002000000046 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_09381279_v11_n4_p239_Heintz |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_09381279_v11_n4_p239_Heintz |y Registro en la Biblioteca Digital |
| 961 | |a paper_09381279_v11_n4_p239_Heintz |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 62984 | ||