Cover Image

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
http://eprints.utm.my/id/eprint/47924/
Tags: Add Tag
No Tags, Be the first to tag this record!
id my.utm.47924
record_format eprints
spelling my.utm.479242017-07-06T04:26:20Z http://eprints.utm.my/id/eprint/47924/ Root counting in product homotopy method 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 NonPeerReviewed application/pdf en http://eprints.utm.my/id/eprint/47924/25/HazrinaTajudinMFS2013.pdf Tajudin, Hazrina (2013) Root counting in product homotopy method. Masters thesis, Universiti Teknologi Malaysia, Faculty of Science.
institution Universiti Teknologi Malaysia
building UTM Library
collection Institutional Repository
continent Asia
country Malaysia
content_provider Universiti Teknologi Malaysia
content_source UTM Institutional Repository
url_provider http://eprints.utm.my/
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
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
publishDate 2013
url http://eprints.utm.my/id/eprint/47924/25/HazrinaTajudinMFS2013.pdf
http://eprints.utm.my/id/eprint/47924/
_version_ 1643652406960979968
score 13.211869

Similar Items