Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study

En:

J. Complexity 2005;21(4):502-531

Fecha:

2005

Formato:

application/pdf

Tipo de documento:

info:eu-repo/semantics/article
info:ar-repo/semantics/artículo
info:eu-repo/semantics/publishedVersion

Descriptores:

Complexity -  Conditioning -  Homotopy algorithms -  Polynomial system solving -  Semi-linear parabolic problems -  Stationary solutions -  Algorithms -  Boundary value problems -  Mathematical models

Descripción:

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.
Fil:De Leo, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Dratman, E. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
Fil:Matera, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.

Identificador(es):

http://hdl.handle.net/20.500.12110/paper_0885064X_v21_n4_p502_DeLeo

Derechos:

info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by/2.5/ar