Root counting in product homotopy method

Product Homotopy method is used to solve dense multivariate polynomial systems for finding all isolated solutions (real or complex). There are two stages in the computation of Homotopy method which are root counting and root finding. This study focuses on root counting which involves the computation...

Full description

Saved in:

Bibliographic Details
Main Author:	Tajudin, Hazrina
Format:	Thesis
Language:	English
Published:	2013
Subjects:	Q Science (General) QD Chemistry
Online Access:	http://eprints.utm.my/id/eprint/47924/25/HazrinaTajudinMFS2013.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.47924
record_format	uketd_dc
spelling	my-utm-ep.479242017-07-06T04:26:20Z Root counting in product homotopy method 2013-07 Tajudin, Hazrina Q Science (General) QD Chemistry Product Homotopy method is used to solve dense multivariate polynomial systems for finding all isolated solutions (real or complex). There are two stages in the computation of Homotopy method which are root counting and root finding. This study focuses on root counting which involves the computation of multi-homogeneous Bézout number (MHBN). This value determines the number of solution path in the second stage. Homogenization of partition each gives its own MHBN. Therefore, it is crucial to have minimum MHBN. The computation of minimum MHBN using local search method, fission and assembly method and genetic algorithm had become intractable when the system size gets larger. Hence, this study applied recent heuristic method, Tabu Search. Other than that, the computation of estimating MHBN is of exponential time. For large size system, the usage of row expansion with memory becomes impossible, hence, this study focus on implementing General Random Path algorithm (GRPA). This study implements Tabu search method and GRPA into several systems of different sizes. Tabu search is effective since the global minimum is obtained instead of the local minimum. Other than that, the number of visited partition is much smaller compared with the previous method. Although GRPA gives estimated value, it helps for large size system. We implement two accuracy level in the computation and in the result, the N=1000 gives more accurate result. Hence, GRPA is important when it comes to solve estimated MHBN for large size system. 2013-07 Thesis http://eprints.utm.my/id/eprint/47924/ http://eprints.utm.my/id/eprint/47924/25/HazrinaTajudinMFS2013.pdf application/pdf en public masters Universiti Teknologi Malaysia, Faculty of Science Faculty of Science
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	Q Science (General) QD Chemistry
spellingShingle	Q Science (General) QD Chemistry Tajudin, Hazrina Root counting in product homotopy method
description	Product Homotopy method is used to solve dense multivariate polynomial systems for finding all isolated solutions (real or complex). There are two stages in the computation of Homotopy method which are root counting and root finding. This study focuses on root counting which involves the computation of multi-homogeneous Bézout number (MHBN). This value determines the number of solution path in the second stage. Homogenization of partition each gives its own MHBN. Therefore, it is crucial to have minimum MHBN. The computation of minimum MHBN using local search method, fission and assembly method and genetic algorithm had become intractable when the system size gets larger. Hence, this study applied recent heuristic method, Tabu Search. Other than that, the computation of estimating MHBN is of exponential time. For large size system, the usage of row expansion with memory becomes impossible, hence, this study focus on implementing General Random Path algorithm (GRPA). This study implements Tabu search method and GRPA into several systems of different sizes. Tabu search is effective since the global minimum is obtained instead of the local minimum. Other than that, the number of visited partition is much smaller compared with the previous method. Although GRPA gives estimated value, it helps for large size system. We implement two accuracy level in the computation and in the result, the N=1000 gives more accurate result. Hence, GRPA is important when it comes to solve estimated MHBN for large size system.
format	Thesis
qualification_level	Master's degree
author	Tajudin, Hazrina
author_facet	Tajudin, Hazrina
author_sort	Tajudin, Hazrina
title	Root counting in product homotopy method
title_short	Root counting in product homotopy method
title_full	Root counting in product homotopy method
title_fullStr	Root counting in product homotopy method
title_full_unstemmed	Root counting in product homotopy method
title_sort	root counting in product homotopy method
granting_institution	Universiti Teknologi Malaysia, Faculty of Science
granting_department	Faculty of Science
publishDate	2013
url	http://eprints.utm.my/id/eprint/47924/25/HazrinaTajudinMFS2013.pdf
_version_	1747817264768352256

Root counting in product homotopy method

Similar Items