Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

We consider a family of polynomial systems which arises in the analysis of the stationary solutions of a standard discretization of certain semi-linear second-order parabolic partial differential equations. We prove that this family is well-conditioned from the numeric point of view, and ill-conditioned from the symbolic point of view. We exhibit a polynomial-time numeric algorithm solving any member of this family, which significantly contrasts the exponential behavior of all known symbolic algorithms solving a generic instance of this family of systems. © 2005 Elsevier Inc. All rights reserved.

Registro:

Documento: Artículo
Título:Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
Autor:De Leo, M.; Dratman, E.; Matera, G.
Filiación:Departamento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, 1428 Buenos Aires, Argentina
Instituto de Desarrollo Humano, Universidad Nacional de General Sarmiento, Jose M. Gutiérrez 1150, 1613 Los Polvorines, Buenos Aires, Argentina
CONICET, Buenos Aires, Argentina
Palabras clave:Complexity; Conditioning; Homotopy algorithms; Polynomial system solving; Semi-linear parabolic problems; Stationary solutions; Algorithms; Boundary value problems; Mathematical models; Matrix algebra; Partial differential equations; Polynomials; Set theory; Homotopy algorithms; Polynomial system solving; Semi linear parabolic problems; Stationary solutions; Computational complexity
Año:2005
Volumen:21
Número:4
Página de inicio:502
Página de fin:531
DOI: http://dx.doi.org/10.1016/j.jco.2004.09.008
Título revista:Festschrift for the 70th Birthday of Arnold Schonhage
Título revista abreviado:J. Complexity
ISSN:0885064X
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_0885064X_v21_n4_p502_DeLeo.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0885064X_v21_n4_p502_DeLeo

Referencias:

  • Allgower, E., Georg, K., Numerical continuation methods: An introduction (1990) Springer Series in Computational Mathematics, 13. , Springer, New York
  • Bandle, C., Brunner, H., Blow-up in diffusion equations: A survey (1998) J. Comput. Appl. Math., 97 (1-2), pp. 3-22
  • Bayer, D., Mumford, D., What can be computed in algebraic geometry? (1993) Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica, 34, pp. 1-49. , D. Eisenbud L. Robbiano Cambridge University Press Cambridge
  • Bini, D., Pan, V., Polynomial and matrix computations (1994) Progress in Theoretical Computer Science, , Boston: Birkhäuser
  • Blum, L., Cucker, F., Shub, M., Smale, S., (1998) Complexity and Real Computation, , New York, Berlin, Heidelberg: Springer
  • Bochnack, J., Coste, M., Roy, M.-F., Real Algebraic Geometry (1998) Ergebnisse Der Mathematik Und Ihrer Grenzgebiete, 36. , Folge 3 Springer, Berlin
  • Bompadre, A., Matera, G., Wachenchauzer, R., Waissbein, A., Polynomial equation solving by lifting procedures for ramified fibers (2004) Theoret. Comput. Sci., 315 (2-3), pp. 335-369
  • Bonder, J.F., Rossi, J., Blow-up vs. spurious steady solutions (2001) Proc. Amer. Math. Soc., 129 (1), pp. 139-144
  • Budd, C., Huang, W., Russell, R., Moving mesh methods for problems with blow-up (1996) SIAM J. Sci. Comput., 17 (2), pp. 305-327
  • Bürgisser, P., Clausen, M., Shokrollahi, M., Algebraic Complexity Theory (1997) Grundlehren Der Mathematischen Wissenschaften, 315. , Springer, Berlin
  • Castro, D., Giusti, M., Heintz, J., Matera, G., Pardo, L., The hardness of polynomial equation solving (2003) Found. Comput. Math., 3 (4), pp. 347-420
  • Chipot, M., Fila, M., Quittner, P., Stationary solutions, blow up and convergence to stationary solutions for semilinear parabolic equations with nonlinear boundary conditions (1991) Acta Math. Univ. Comenian., 60 (1), pp. 35-103
  • Chistov, A., Grigoriev, D., Subexponential time solving systems of algebraic equations (1983), I, II, LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad; Cox, D., Little, J., O'Shea, D., Using algebraic geometry (1998) Graduate Texts in Mathematics, 185. , Springer, New York
  • Dratman, E., Matera, G., Deformation techniques for counting the real solutions of specific polynomial equation systems (2002) Proceedings Workshop Argentino De Informática Teórica, WAIT'02, 31, pp. 42-52. , Santa Fe, Argentina, September, Anales JAIIO SADIO, Buenos Aires, 2002
  • Eisenbud, D., Commutative Algebra with a View Toward Algebraic Geometry (1995) Graduate Texts in Mathematics, 150. , Springer, New York
  • Ferreira, R., Groisman, P., Rossi, J., Numerical blow-up for a nonlinear problem with a nonlinear boundary condition (2002) Math. Models Methods Appl. Sci., 12 (4), pp. 461-484
  • Fulton, W., Intersection theory (1984), Berlin, Heidelberg, New York: Springer; von zur Gathen, J., Parallel arithmetic computations: A survey (1986) Proceedings of the 12th International Symposium on Mathematics Foundations in Computer Science, 233, pp. 93-112. , J. Gruska, B. Rovan, J. Wiedermann (Eds.) Bratislava, Czechoslovakia, August 25-29, 1986, Lecture Notes in Computer Science Springer, Berlin
  • von zur Gathen, J., Gerhard, J., (1999) Modern Computer Algebra, , Cambridge: Cambridge University Press
  • 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
  • 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, Symposia Mathematica, 34, pp. 216-256. , D. Eisenbud L. Robbiano Eds. Cambridge University Press
  • 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
  • Giusti, M., Heintz, J., Sabia, J., On the efficiency of effective Nullstellensätze (1993) Comput. Complexity, 3, pp. 56-95
  • Giusti, M., Lecerf, G., Salvy, B., A Gröbner free alternative for polynomial system solving (2001) J. Complexity, 17 (1), pp. 154-211
  • Gomez, J.L., Marquez, V., Wolanski, N., Dynamic behavior of positive solutions to reaction-diffusion problems with nonlinear absorption through the boundary (1993) Rev. Un. Mat. Argentina, 38, pp. 196-209
  • Gonzalez-Vega, L., Rouillier, F., Roy, M.-F., Trujillo, G., Symbolic recipes for real solutions (1999) Some Tapas in Computer Algebra, 4, pp. 121-167. , A. Cohen Ed. Algorithms in Computational Mathematics, Springer Berlin
  • Heintz, J., Definability and fast quantifier elimination in algebraically closed fields (1983) Theoret. Comput. Sci., 24 (3), pp. 239-277
  • Heintz, J., Jerónimo, G., Sabia, J., San Martín, J., Solernó, P., (2002) Intersection Theory and Deformation Algorithms: The Multihomogeneous Case, , Manuscript, University of Buenos Aires
  • 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
  • Heintz, J., Matera, G., Pardo, L., Wachenchauzer, R., The intrinsic complexity of parametric elimination methods (1998) Electron. J. SADIO, 1 (1), pp. 37-51
  • Heintz, J., Matera, G., Waissbein, A., On the time-space complexity of geometric elimination procedures (2001) Appl. Algebra Eng. Comm. Comput., 11 (4), pp. 239-296
  • Heintz, J., Roy, M.-F., Solernó, P., Description des composantes connexes d'un ensemble semialgébrique en temps simplement exponential (1991) C. R. Math. Acad. Sci., 313, pp. 167-170
  • Henry, D., Geometric theory of semilinear parabolic equations (1981) Lecture Notes in Mathematics, 840. , Springer, New York
  • Huber, B., Sturmfels, B., A polyhedral method for solving sparse polynomial systems (1995) Math. Comp., 64 (112), pp. 1541-1555
  • Huber, B., Sturmfels, B., Bernstein's Theorem in affine space (1997) Discrete Comput. Geom., 17, pp. 137-141
  • Levine, H., The role of critical exponents in blow up theorems (1990) SIAM Rev., 32, pp. 262-288
  • Li, T., Numerical solution of multivariate polynomial systems by homotopy continuation methods (1997) Acta Numer., 6, pp. 399-436
  • Li, T., Wang, X., Solving real polynomial systems with real homotopies (1993) Math. Comp., 60 (202), pp. 669-680
  • Lickteig, T., Roy, M.-F., Sylvester-Habicht sequences and fast Cauchy index computation (2001) J. Symbolic Comput., 31 (3), pp. 315-341
  • Matsumura, H., (1986) Commutative Ring Theory, , Cambridge: Cambridge University Press
  • Mignotte, M., (1992) Mathematics for Computer Algebra, , New York: Springer
  • Moré, J., A collection of nonlinear model problems (1990) Computational Solution of Nonlinear Systems of Equations, pp. 723-762. , E. Allgower K. Georg Eds. American Mathematical Society Providence, RI
  • Morgan, A., Solving polynomial systems using continuation for engineering and scientific problems (1987), Englewood Cliffs, NJ: Prentice-Hall; Morgan, A., Sommese, A., Wampler, C., A generic product-decomposition formula for Bézout numbers (1995) SIAM J. Numer. Anal., 32, pp. 1308-1325
  • Mumford, D., (1995) Algebraic Geometry I. Complex Projective Varieties, , 2nd ed., Berlin: Classics in Mathematics, Springer
  • Nabben, R., Two-side bounds on the inverses of diagonally dominant tridiagonal matrices (1998) Linear Algebra Appl., 287 (1-3), pp. 289-305
  • Ortega, J., Rheinboldt, W., (1970) Iterative Solutions of Nonlinear Equations in Several Variables, , New York: Academic Press
  • Pao, C., (1992) Nonlinear Parabolic and Elliptic Equations, , New York: Plenum Press
  • Pardo, L., Universal elimination requires exponential running time (2000) Computer Algebra and Applications, pp. 25-51. , A. Montes (Ed.) Proceedings of EACA-2000, Barcelona, Spain, September
  • Pardo, L., San Martín, J., Deformation techniques to solve generalized Pham systems (2004) Theoret. Comput. Sci., 315 (2-3), pp. 593-625
  • Perko, L., (1996) Differential Equations and Dynamical Systems, 7. , 2nd ed. Texts in Applied Mathematics, Springer, Berlin
  • Rojas, M., Why polyhedra matter in non-linear equation solving (2003) Proceedings Conference on Algebraic Geometry and Geometric Modelling, 334, pp. 293-320. , (Vilnius, Lithuania, July 29-August 2, 2002) Contemporary Mathematics American Mathematical Society, Providence, RI
  • Samarskii, A., Galaktionov, V., Kurdyumov, S., Mikhailov, A., Blow-up in quasilinear parabolic equations (1995) De Gruyter Experimental Mathematics, 19. , de Gruyter, Berlin
  • Savage, J., (1998) Models of Computation. Exploring the Power of Computing, , Reading, MA: Addison-Wesley
  • Schost, E., Computing parametric geometric resolutions (2003) Appl. Algebra Eng. Comm. Comput., 13, pp. 349-393
  • Shafarevich, I., (1994) Basic Algebraic Geometry:Varieties in Projective Space, , Berlin, Heidelberg, New York: Springer
  • Sommese, A., Verschelde, J., Wampler, C., Numerical decomposition of the solution sets of polynomial systems into irreducible components (2001) SIAM J. Numer. Anal., 38 (6), pp. 2022-2046
  • Verschelde, J., Gatermann, K., Cools, R., Mixed volume computation by dynamic lifting applied to polynomial system solving (1996) Discrete Comput. Geom., 16 (1), pp. 69-112
  • Verschelde, J., Verlinden, P., Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems (1994) SIAM J. Numer. Anal., 31 (3), pp. 915-930
  • Zippel, R., (1993) Effective Polynomial Computation, , Kluwer International Series in Engineering and Computer Science, Dordrecht: Kluwer Academic Publishers

Citas:

---------- APA ----------
De Leo, M., Dratman, E. & Matera, G. (2005) . Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study. Festschrift for the 70th Birthday of Arnold Schonhage, 21(4), 502-531.
http://dx.doi.org/10.1016/j.jco.2004.09.008
---------- CHICAGO ----------
De Leo, M., Dratman, E., Matera, G. "Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study" . Festschrift for the 70th Birthday of Arnold Schonhage 21, no. 4 (2005) : 502-531.
http://dx.doi.org/10.1016/j.jco.2004.09.008
---------- MLA ----------
De Leo, M., Dratman, E., Matera, G. "Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study" . Festschrift for the 70th Birthday of Arnold Schonhage, vol. 21, no. 4, 2005, pp. 502-531.
http://dx.doi.org/10.1016/j.jco.2004.09.008
---------- VANCOUVER ----------
De Leo, M., Dratman, E., Matera, G. Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study. J. Complexity. 2005;21(4):502-531.
http://dx.doi.org/10.1016/j.jco.2004.09.008