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
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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v21_n4_p502_DeLeo_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-paper_0885064X_v21_n4_p502_DeLeo_oai
record_format	dspace
spelling	I28-R145-paper_0885064X_v21_n4_p502_DeLeo_oai2024-08-16 De Leo, M. Dratman, E. Matera, G. 2005 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. application/pdf http://hdl.handle.net/20.500.12110/paper_0885064X_v21_n4_p502_DeLeo info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar J. Complexity 2005;21(4):502-531 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 Numeric vs. symbolic homotopy algorithms in polynomial system solving: A case study info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v21_n4_p502_DeLeo_oai
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-145
collection	Repositorio Digital de la Universidad de Buenos Aires (UBA)
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 https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_0885064X_v21_n4_p502_DeLeo_oai
work_keys_str_mv	AT deleom numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy AT dratmane numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy AT materag numericvssymbolichomotopyalgorithmsinpolynomialsystemsolvingacasestudy
_version_	1809357009136386048

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

Ejemplares similares