Skip to main content
SUPERVISOR
Azam Etemad dehkordy,Amir Hashemi
اعظم اعتماددهکردی (استاد مشاور) امیر هاشمی (استاد راهنما)
 
STUDENT
Fateme Ahmadi
فاطمه احمدی

FACULTY - DEPARTMENT

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

TITLE

Solving Symmetric Polynomial Systems
One of the dir=rtl align=right Solving polynomial systems is also an important tool in computer algebra. It is possible to solve polynomial equation systems using Gr?bner bases. For this purpose, we can compute the Gr?bner basis w.r.t. lexicographical ordering and from this basis, we can compute simpler the solutions of the initial system. On the other hand, some of the polynomial equation systems that are important in application have symmetries. In this thesis, we study an efficient method to solve polynomial systems whose equations are left invariant by the action of a finite group G. For this purpose, we shall consider first an invariant olynomial ring, i.e. the ring of polynomials which are invariant under the action of the given group. Such a polynomial ring can be represented by the primary and secondary invariants. For solving symmetric polynomial system we use the truncated form of SAGBI- Gr?bner bases (a generalization of Gr?bner bases to ideals of sub algebras of polynomial ring) and a Gr?bner bases in the invariant ring where is the i-th elementary symmetric polynomial. In fact, to solve an invariant system, we provide to main algorithms: first, from an algorithm like Buchberger's algorithm we compute truncated SAGBI- Gr?bner bases of an ideal in invariant rings. The second algorithm is iired by FGLM algorithm: from a truncated SAGBI- Gr?bner basis of a zero dimensional ideal we can compute efficiently a Gr?bner basis in some invariant rings , from this notation, we mean a ring of polynomials which are stable under the action of the group G. Finally, we will show how two algorithm can be combined to find all the complex roots of such an invariant polynomial system. In [6], Colin suggested to use invariants (primary and secondary invariants) to reformulate a given polynomial system. In fact, he expressed each polynomial equation of the system with symmetries as polynomial in term of the primary and secondary invariants and added generators of the ideal of syzygies between secondary invariants to this expressions. This new system (depending only on the invariants) has the same variety as the original one. By using this method, the systems can be solved without breaking the symmetries. But, this method is not always optimal in practice because the resulting systems are often more difficult to solve than the original one. Finally, we shall note that invariant theory may be considered as both a type="#_x0000_t75" finitely generated as a K-algebra?". Due to some results of Hilbert, Nagata, Haboush and Popov, it is known that this question has an affirmative answer iff G is reductive. The algorithmic side of this problem is to find the generators of when it is finitely generated, and it has been also studied in this thesis.
یکی از مهم‌ترین چالش‌ها در جبر کامپیوتری، حل دستگاه‌های معادلات چند‌جمله‌ای است. از طرفی برخی از معادلاتی که از صنعت معرفی می‌شوند دارای تقارن هستند. ما در این پایان‌نامه به حل دستگاه معادلات چند‌جمله‌ای می‌پردازیم که تحت عمل یک گروه ماتریسی متناهی پایا بماند. برای مطالعه‌ی جبری این دستگاه‌ها و در نظر گرفتن تقارن آن‌ها، حلقه‌ی چند‌جمله‌ای‌های پایا را معرفی می‌کنیم. با توجه به ساختار این حلقه‌ها، می‌توان هر حلقه‌ی پایا را بر حسب پایا‌های اولیه و ثانویه نمایش داد. در بخش اول این پایان‌نامه، روش محاسبه‌ی این پایا‌ها را بیان خواهیم کرد. هم‌چنین برای حل دستگاه معادلات چند‌جمله‌ای پایا، از مفاهیم پایه‌ی ساگبی- گربنر کوتاه شده و پایه‌ی گربنر در حلقه‌ی پایا استفاده می‌کنیم. برای محاسبه‌ی پایه‌ی ساگبی- گربنر از الگوریتمی شبیه الگوریتم بوخبرگر استفاده می‌کنیم. سپس نسخه‌ی پایای الگوریتم FGLM با نام FGLM-Invariant را بیان و سپس با استفاده از الگوریتم FGLM به پایه‌ی گربنر ایده‌آلی دسترسی پیدا می‌کنیم که حل آن بسیار ساده ‌تر از دستگاه متقارن داده شده است. در انتها نشان می‌دهیم که چگونه با استفاده از جواب‌های این دستگاه و گروه ماتریسی داده شده، می‌توانیم ریشه‌های مختلط دستگاه معادلات چند‌جمله‌ای پایا را به ‌دست آوریم.

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