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

Mostrar todas las versiones(3)

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-conditi...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: De Leo, M., Dratman, E., Matera, G.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: 2005
Materias:
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
Semi linear parabolic problems
Computational complexity
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_0885064X_v21_n4_p502_DeLeo
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paperaa:paper_0885064X_v21_n4_p502_DeLeo
record_format dspace
spelling paperaa:paper_0885064X_v21_n4_p502_DeLeo2023-06-12T16:48:18Z Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study J. Complexity 2005;21(4):502-531 De Leo, M. Dratman, E. Matera, G. 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 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. 2005 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion application/pdf eng info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_0885064X_v21_n4_p502_DeLeo
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv eng
topic 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
spellingShingle 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
De Leo, M.
Dratman, E.
Matera, G.
Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
topic_facet 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
description 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.
format Artículo
Artículo
publishedVersion
author De Leo, M.
Dratman, E.
Matera, G.
author_facet De Leo, M.
Dratman, E.
Matera, G.
author_sort De Leo, M.
title Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
title_short Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
title_full Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
title_fullStr Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
title_full_unstemmed Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study
title_sort numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study
publishDate 2005
url http://hdl.handle.net/20.500.12110/paper_0885064X_v21_n4_p502_DeLeo
work_keys_str_mv AT deleom numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy
AT dratmane numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy
AT materag numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy
_version_ 1769810236443459584

Ejemplares similares