Skip to main content
SUPERVISOR
Reza Mokhtari,Amir Hashemi
رضا مختاری (استاد مشاور) امیر هاشمی (استاد راهنما)
 
STUDENT
Asieh Pourhaghani
آسیه پورحقانی

FACULTY - DEPARTMENT

دانشکده ریاضی
DEGREE
Master of Science (MSc)
YEAR
1387

TITLE

Solving Parametric Polynomial Systems
Many problems in science and engineering such as biology, chemistry, computer vision, robotics, and so on, can be reduced to solve a parametric polynomial system. Such a system has two different unknowns: variables and parameters. Solving parametric polynomial system, which is the main purpose of this thesis, means finding the values of variables w.r.t. the different values of parameters. In the other words, the main obstacle in solving such a system is to describe the structure of the solution set in dependence of the parameters. In this thesis, we reduce the space of computations to the space of parameters. Then by cylindrical algebraic decomposition (CAD) method, which had been discovered by Collins, we decompose whole the space of parameters into the cells on which the initial polynomial system has constant sign. But this method requires too much computation time and its complexity is doubly exponential. Lazard and Rouillier, by introducing the concept of minimal discriminant variety, have reduced the space of computations to the parameter space and then they have used CAD to decompose the space of parameters into the cells. In this thesis, as a new result, we modify Lazard-Rouillier algorithm to compute minimal discriminant variety, and we show that with our improvements the output of our algorithm is (despite of Lazard-Rouillier algorithm) always minimal and it does not need to compute the radical of ideals.
کاربرد فراوان دستگاه های چندجمله ای پارامتری در علوم، به خصوص در مدلسازی سیستم ها، در رشته هایی چون بیولوژی، علوم کامپیوتر، رباتیک، شیمی و ... محققان بسیاری را وادار به یافتن الگوریتمی مناسب برای حل چنین دستگاه هایی کرده است. بسیاری از مسائل پیچیده صنعتی را می توان با مدل سازی توسط دستگاه معادلات و نامعادلات چندجمله ای پارامتری حل کرد. در چنین مسائلی دو دسته مجهول داریم، متغیرها و پارامترها. حل دستگاه چندجمله ای پارامتری یعنی یافتن جواب برای متغیرها برحسب مقادیر مختلف پارامترها. در این پایان نامه به کمک تعمیم مفهوم مبین سنتی به چندگونای مبین، فضای محاسبات را به فضای پارامترها تقلیل می دهیم و سپس با استفاده از روشی موسوم به «تجزیه جبری استوانه ای» کل فضای پارامترها را به سلول هایی افراز می کنیم که در هر یک از آنها رفتار دستگاه ثابت باشد. با استفاده از نتایج جدید به دست آمده در این پایان نامه، نشان می دهیم همیشه چندگونای مبین کمینه را بدون نیاز به انجام محاسبات پرهزینه ای مانند محاسبه رادیکال ایده آل می توان محاسبه کرد. مطالب و الگوریتم های ارائه شده در این پایان نامه به گونه ای است که با استفاده از یک یارانه شخصی معمولی بتوان دستگاه معادلات و نامعادلات چندجمله ای پارامتری را به طور کامل حل کرد. کلمات کلیدی: دستگاه چندجمله ای پارامتری، مجموعه جبری، مجموعه نیمه جبری، مجموعه ساخت پذیر، چندگونای مبین، تجزیه جبری استوانه ای، پایه گروبنر.

ارتقاء امنیت وب با وف بومی