×

Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study. (English) Zbl 1098.65052

A family of systems of polynomial equations is considered, which arises in the analysis of the stationary solutions of certain discretized semi-linear parabolic differential equations. Only the positive solutions are of interest. A numerical homotopy algorithm for finding all positive solutions is presented with polynomial complexity in the number of unknown. It is shown that any universal symbolic method is likely to have a complexity which is exponential in the number of unknowns.

MSC:

65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
65H10 Numerical computation of solutions to systems of equations
12Y05 Computational aspects of field theory and polynomials (MSC2010)
26C10 Real polynomials: location of zeros
65Y20 Complexity and performance of numerical algorithms

Software:

Kronecker
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Allgower, K. Georg, Numerical continuation methods: an introduction, Springer Series in Computational Mathematics, vol. 13, Springer, New York, 1990.; E. Allgower, K. Georg, Numerical continuation methods: an introduction, Springer Series in Computational Mathematics, vol. 13, Springer, New York, 1990. · Zbl 0717.65030
[2] Bandle, C.; Brunner, H., Blow-up in diffusion equationsa survey, J. Comput. Appl. Math., 97, 1-2, 3-22 (1998)
[3] Bayer, D.; Mumford, D., What can be computed in algebraic geometry?, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica, vol. 34 (1993), Cambridge University Press: Cambridge University Press Cambridge), 1-49 · Zbl 0846.13017
[4] Bini, D.; Pan, V., Polynomial and matrix computations, Progress in Theoretical Computer Science (1994), Birkhäuser: Birkhäuser Boston
[5] Blum, L.; Cucker, F.; Shub, M.; Smale, S., Complexity and Real Computation (1998), Springer: Springer New York, Berlin, Heidelberg
[6] J. Bochnack, M. Coste, M.-F. Roy, Real Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete, Folge 3, vol. 36, Springer, Berlin, 1998.; J. Bochnack, M. Coste, M.-F. Roy, Real Algebraic Geometry, Ergebnisse der Mathematik und ihrer Grenzgebiete, Folge 3, vol. 36, Springer, Berlin, 1998.
[7] Bompadre, A.; Matera, G.; Wachenchauzer, R.; Waissbein, A., Polynomial equation solving by lifting procedures for ramified fibers, Theoret. Comput. Sci., 315, 2-3, 335-369 (2004) · Zbl 1060.65054
[8] Bonder, J. F.; Rossi, J., Blow-up vs. spurious steady solutions, Proc. Amer. Math. Soc., 129, 1, 139-144 (2001) · Zbl 0970.35003
[9] Budd, C.; Huang, W.; Russell, R., Moving mesh methods for problems with blow-up, SIAM J. Sci. Comput., 17, 2, 305-327 (1996) · Zbl 0860.35050
[10] P. Bürgisser, M. Clausen, M. Shokrollahi, Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften. vol. 315, Springer, Berlin, 1997.; P. Bürgisser, M. Clausen, M. Shokrollahi, Algebraic Complexity Theory, Grundlehren der mathematischen Wissenschaften. vol. 315, Springer, Berlin, 1997.
[11] Castro, D.; Giusti, M.; Heintz, J.; Matera, G.; Pardo, L., The hardness of polynomial equation solving, Found. Comput. Math., 3, 4, 347-420 (2003) · Zbl 1049.68070
[12] Chipot, M.; Fila, M.; Quittner, P., Stationary solutions, blow up and convergence to stationary solutions for semilinear parabolic equations with nonlinear boundary conditions, Acta Math. Univ. Comenian., 60, 1, 35-103 (1991) · Zbl 0743.35038
[13] A. Chistov, D. Grigoriev, Subexponential time solving systems of algebraic equations. I, II, LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad, 1983.; A. Chistov, D. Grigoriev, Subexponential time solving systems of algebraic equations. I, II, LOMI preprints E-9-83, E-10-83, Steklov Institute, Leningrad, 1983.
[14] D. Cox, J. Little, D. O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer, New York, 1998.; D. Cox, J. Little, D. O’Shea, Using algebraic geometry, Graduate Texts in Mathematics, vol. 185, Springer, New York, 1998.
[15] E. Dratman, G. Matera, Deformation techniques for counting the real solutions of specific polynomial equation systems, in: Proceedings Workshop Argentino de Informática Teórica, WAIT’02, Santa Fe, Argentina, September 2002, Anales JAIIO, vol. 31, SADIO, Buenos Aires, 2002, pp. 42-52.; E. Dratman, G. Matera, Deformation techniques for counting the real solutions of specific polynomial equation systems, in: Proceedings Workshop Argentino de Informática Teórica, WAIT’02, Santa Fe, Argentina, September 2002, Anales JAIIO, vol. 31, SADIO, Buenos Aires, 2002, pp. 42-52.
[16] D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150, Springer, New York, 1995.; D. Eisenbud, Commutative Algebra with a View Toward Algebraic Geometry, Graduate Texts in Mathematics, vol. 150, Springer, New York, 1995. · Zbl 0819.13001
[17] Ferreira, R.; Groisman, P.; Rossi, J., Numerical blow-up for a nonlinear problem with a nonlinear boundary condition, Math. Models Methods Appl. Sci., 12, 4, 461-484 (2002) · Zbl 1028.35082
[18] Fulton, W., Intersection theory (1984), Springer: Springer Berlin, Heidelberg, New York · Zbl 0541.14005
[19] J. von zur Gathen, Parallel arithmetic computations: a survey, in: J. Gruska, B. Rovan, J. Wiedermann (Eds.), Proceedings of the 12th International Symposium on Mathematics Foundations in Computer Science, Bratislava, Czechoslovakia, August 25-29, 1986, Lecture Notes in Computer Science, vol. 233, Springer, Berlin, 1986, pp. 93-112.; J. von zur Gathen, Parallel arithmetic computations: a survey, in: J. Gruska, B. Rovan, J. Wiedermann (Eds.), Proceedings of the 12th International Symposium on Mathematics Foundations in Computer Science, Bratislava, Czechoslovakia, August 25-29, 1986, Lecture Notes in Computer Science, vol. 233, Springer, Berlin, 1986, pp. 93-112. · Zbl 0616.68037
[20] von zur Gathen, J.; Gerhard, J., Modern Computer Algebra (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0936.11069
[21] Giusti, M.; Hägele, K.; Heintz, J.; Morais, J. E.; Montaña, J. L.; Pardo, L. M., Lower bounds for Diophantine approximation, J. Pure Appl. Algebra, 117,118, 277-317 (1997) · Zbl 0871.68101
[22] 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, (Eisenbud, D.; Robbiano, L., Computational Algebraic Geometry and Commutative Algebra, Symposia Mathematica, vol. 34 (1993), Cambridge University Press), 216-256 · Zbl 0829.14029
[23] Giusti, M.; Heintz, J.; Morais, J. E.; Morgenstern, J.; Pardo, L. M., Straight-line programs in geometric elimination theory, J. Pure Appl. Algebra, 124, 101-146 (1998) · Zbl 0944.12004
[24] Giusti, M.; Heintz, J.; Sabia, J., On the efficiency of effective Nullstellensätze, Comput. Complexity, 3, 56-95 (1993) · Zbl 0824.68051
[25] Giusti, M.; Lecerf, G.; Salvy, B., A Gröbner free alternative for polynomial system solving, J. Complexity, 17, 1, 154-211 (2001) · Zbl 1003.12005
[26] Gomez, J. L.; Marquez, V.; Wolanski, N., Dynamic behavior of positive solutions to reaction-diffusion problems with nonlinear absorption through the boundary, Rev. Un. Mat. Argentina, 38, 196-209 (1993) · Zbl 0808.35062
[27] Gonzalez-Vega, L.; Rouillier, F.; Roy, M.-F.; Trujillo, G., Symbolic recipes for real solutions, (Cohen, A.; etal., Some tapas in computer algebra, Algorithms in Computational Mathematics, vol. 4 (1999), Springer: Springer Berlin), 121-167 · Zbl 0994.12003
[28] Heintz, J., Definability and fast quantifier elimination in algebraically closed fields, Theoret. Comput. Sci., 24, 3, 239-277 (1983) · Zbl 0546.03017
[29] Heintz, J.; Jerónimo, G.; Sabia, J.; San Martín, J.; Solernó, P., Intersection Theory and Deformation AlgorithmsThe Multihomogeneous Case, Manuscript (2002), University of Buenos Aires
[30] Heintz, J.; Krick, T.; Puddu, S.; Sabia, J.; Waissbein, A., Deformation techniques for efficient polynomial equation solving, J. Complexity, 16, 1, 70-109 (2000) · Zbl 1041.65044
[31] Heintz, J.; Matera, G.; Pardo, L.; Wachenchauzer, R., The intrinsic complexity of parametric elimination methods, Electron. J. SADIO, 1, 1, 37-51 (1998) · Zbl 0915.68073
[32] Heintz, J.; Matera, G.; Waissbein, A., On the time-space complexity of geometric elimination procedures, Appl. Algebra Eng. Comm. Comput., 11, 4, 239-296 (2001) · Zbl 0977.68101
[33] Heintz, J.; Roy, M.-F.; Solernó, P., Description des composantes connexes d’un ensemble semialgébrique en temps simplement exponential, C. R. Math. Acad. Sci., 313, 167-170 (1991) · Zbl 0764.14024
[34] D. Henry, Geometric theory of semilinear parabolic equations, Lecture Notes in Mathematics, vol. 840, Springer, New York, 1981.; D. Henry, Geometric theory of semilinear parabolic equations, Lecture Notes in Mathematics, vol. 840, Springer, New York, 1981. · Zbl 0456.35001
[35] Huber, B.; Sturmfels, B., A polyhedral method for solving sparse polynomial systems, Math. Comp., 64, 112, 1541-1555 (1995) · Zbl 0849.65030
[36] Huber, B.; Sturmfels, B., Bernstein’s Theorem in affine space, Discrete Comput. Geom., 17, 137-141 (1997) · Zbl 0891.65055
[37] Levine, H., The role of critical exponents in blow up theorems, SIAM Rev., 32, 262-288 (1990) · Zbl 0706.35008
[38] Li, T., Numerical solution of multivariate polynomial systems by homotopy continuation methods, Acta Numer., 6, 399-436 (1997) · Zbl 0886.65054
[39] Li, T.; Wang, X., Solving real polynomial systems with real homotopies, Math. Comp., 60, 202, 669-680 (1993) · Zbl 0779.65033
[40] Lickteig, T.; Roy, M.-F., Sylvester-Habicht sequences and fast Cauchy index computation, J. Symbolic Comput., 31, 3, 315-341 (2001) · Zbl 0976.65043
[41] Matsumura, H., Commutative Ring Theory (1986), Cambridge University Press: Cambridge University Press Cambridge
[42] Mignotte, M., Mathematics for Computer Algebra (1992), Springer: Springer New York
[43] Moré, J., A collection of nonlinear model problems, (Allgower, E.; Georg, K., Computational solution of nonlinear systems of equations (1990), American Mathematical Society: American Mathematical Society Providence, RI), 723-762
[44] Morgan, A., Solving polynomial systems using continuation for engineering and scientific problems (1987), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0733.65031
[45] Morgan, A.; Sommese, A.; Wampler, C., A generic product-decomposition formula for Bézout numbers, SIAM J. Numer. Anal., 32, 1308-1325 (1995) · Zbl 0854.65038
[46] Mumford, D., Algebraic Geometry I. Complex Projective Varieties (1995), Classics in Mathematics, Springer: Classics in Mathematics, Springer Berlin · Zbl 0821.14001
[47] Nabben, R., Two-side bounds on the inverses of diagonally dominant tridiagonal matrices, Linear Algebra Appl., 287, 1-3, 289-305 (1998) · Zbl 0951.15005
[48] Ortega, J.; Rheinboldt, W., Iterative solutions of nonlinear equations in several variables (1970), Academic Press: Academic Press New York · Zbl 0241.65046
[49] Pao, C., Nonlinear Parabolic and Elliptic Equations (1992), Plenum Press: Plenum Press New York
[50] L. Pardo, Universal elimination requires exponential running time, in: A. Montes (Ed.), Computer Algebra and Applications, Proceedings of EACA-2000, Barcelona, Spain, September 2000, pp. 25-51.; L. Pardo, Universal elimination requires exponential running time, in: A. Montes (Ed.), Computer Algebra and Applications, Proceedings of EACA-2000, Barcelona, Spain, September 2000, pp. 25-51.
[51] Pardo, L.; San Martín, J., Deformation techniques to solve generalized Pham systems, Theoret. Comput. Sci., 315, 2-3, 593-625 (2004) · Zbl 1053.65038
[52] L. Perko, Differential equations and dynamical systems, 2nd ed., Texts in Applied Mathematics, vol. 7, Springer, Berlin, 1996.; L. Perko, Differential equations and dynamical systems, 2nd ed., Texts in Applied Mathematics, vol. 7, Springer, Berlin, 1996. · Zbl 0854.34001
[53] M. Rojas, Why polyhedra matter in non-linear equation solving, in: Proceedings Conference on Algebraic Geometry and Geometric Modelling, (Vilnius, Lithuania, July 29-August 2, 2002), Contemporary Mathematics, vol. 334, American Mathematical Society, Providence, RI, 2003, pp. 293-320.; M. Rojas, Why polyhedra matter in non-linear equation solving, in: Proceedings Conference on Algebraic Geometry and Geometric Modelling, (Vilnius, Lithuania, July 29-August 2, 2002), Contemporary Mathematics, vol. 334, American Mathematical Society, Providence, RI, 2003, pp. 293-320. · Zbl 1073.12007
[54] A. Samarskii, V. Galaktionov, S. Kurdyumov, A. Mikhailov, Blow-up in quasilinear parabolic equations, de Gruyter Experimental Mathematics, vol. 19, de Gruyter, Berlin, 1995.; A. Samarskii, V. Galaktionov, S. Kurdyumov, A. Mikhailov, Blow-up in quasilinear parabolic equations, de Gruyter Experimental Mathematics, vol. 19, de Gruyter, Berlin, 1995. · Zbl 1020.35001
[55] Savage, J., Models of Computation. Exploring the Power of Computing (1998), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0890.68059
[56] Schost, E., Computing parametric geometric resolutions, Appl. Algebra Eng. Comm. Comput., 13, 349-393 (2003) · Zbl 1058.68123
[57] Shafarevich, I., Basic Algebraic GeometryVarieties in Projective Space (1994), Springer: Springer Berlin, Heidelberg, New York
[58] Sommese, A.; Verschelde, J.; Wampler, C., Numerical decomposition of the solution sets of polynomial systems into irreducible components, SIAM J. Numer. Anal., 38, 6, 2022-2046 (2001) · Zbl 1002.65060
[59] Verschelde, J.; Gatermann, K.; Cools, R., Mixed volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom., 16, 1, 69-112 (1996) · Zbl 0854.68111
[60] Verschelde, J.; Verlinden, P.; Cools, R., Homotopies exploiting Newton polytopes for solving sparse polynomial systems, SIAM J. Numer. Anal., 31, 3, 915-930 (1994) · Zbl 0809.65048
[61] Zippel, R., Effective Polynomial Computation, Kluwer International Series in Engineering and Computer Science (1993), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.