دانلود مقاله ISI انگلیسی شماره 25449 + ترجمه فارسی
عنوان فارسی مقاله

حل دستگاه‌های چندجمله‌ای با استفاده از حساب ابرصفحه‌ای و برنامه‌ریزی خطی

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی
25449 2014 9 صفحه PDF 29 صفحه WORD
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Solving multivariate polynomial systems using hyperplane arithmetic and linear programming
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Computer-Aided Design, Volume 46, January 2014, Pages 101–109

فهرست مطالب ترجمه فارسی
چکیده
کلید واژه ها
1.مقدمه
1.1روش‌های زیربخشی
1.2روش‌های بیزیر یا منحنی‌های B
1.3محدودیت‌های روش‌های زیربخشی منحنی B یا بیزیر
2.الگوریتم
2.1کران‌دار‌سازی یک چندجمله‌ای با ابرصفحات
2.2الگوریتم برنامه‌ریزی خطی ساده
2.3حساب ابرصفحه‌ای
2.4مرور کلی الگوریتم
3.نتایج تجربی
3.1قطع دادن ابراستوانه‌ها
3.2تعمیم به درجه‌ی 3
3.3دستگاه سه‌قطری برویدن 
3.4مثالی از یک دستگاه فشرده
4.بحث و کارهای آتی
زیرنویس شکل‌ها
کلمات کلیدی
حلال زیربخش - حلال چند متغیره - محدودیت های هندسی -
ترجمه چکیده
حل دستگاه‌های معادلات چندجمله‌ای در بسیاری زمینه‌ها از جمله طراحی به کمک کامپیوتر، تولید و رباتیک مسئله‌ای مهم است. حل‌کننده ‌های مبتنی بر زیربخشی که عموماً از خصوصیات شکل نمایش بیزیر یا منحنی‌های B بهره می‌برند در سال‌‌های اخیر توانسته‌اند در حل چنین دستگاه‌هایقیدهای چندجمله‌ای موفقیت‌آمیز ظاهر شوند. یک ضعف عمده‌ در استفاده از حل‌کننده‌های زیربخشی فقدان مقیاس‌پذیری آن‌هاست. هنگامی که قید داده‌شده به شکل ضرب تانسوری از متغیرهایش نمایش داده شود، اندازه‌اش به‌صورت تابعی از تعداد متغیرهایش به‌طور نمایی رشد می‌کند. در این مقاله ما روشی جدید برای حل دستگاه‌های قید‌های چندجمله‌ای ارائه می‌کنیم که به‌خوبی برای سیستم‌ها با تعداد زیاد متغیر و درجه‌ی نسبتاً کم مقیاس می‌شود. چنین سیستم‌هایی در حوزه‌های کاربری بسیاری ظاهر می‌شوند. این روش مبتنی بر مفهوم حساب ابرصفحه‌ای کراندار است که می‌توان آن را تعمیمی از حساب بازه‌ای دانست. ما ابرصفحات کراندار را می‌سازیم و سپس به حل‌کننده‌ی برنامه‌ریزی خطی می‌دهیم تا از دامنه‌ی ریشه کاسته شود. ما روش خود را پیاده‌سازی کرده و نتایج عملی را ارائه می‌دهیم. این روش با روش‌های پیشین مقایسه و مزایای آن بحث می‌شوند.
ترجمه مقدمه
در بسیاری زمینه‌ها مثل رباتیک [1]، طراحی و تولید به کمک کامپیوتر [2، 3] و بسیاری دیگر [4] حل دستگاه‌های معادلات چندجمله‌ای مسئله‌ای حیاتی است. این مسئله، که به یافتن ریشه‌‌های مجموعه‌ای از معادلات چندجمله‌ای چندمتغیره شناخته می‌شوند، مسئله‌ی دشواری بوده و رویکردهای متعددی برای آن پیشنهاد شده است. رویکردهای نمادین مثل پایه‌های گروبنر و تکنیک‌های مبتنی بر حذفِ مشابه [5] سیستم دستگاه اصلی را به دستگاهی ساده‌تر نگاشت می‌کند به‌طوری که مجموعه‌جواب حفظ شود. روش‌های استمرار چندجمله‌ای (که تحت عنوان روش‌های هموتوپی نیز شناخته می‌شوند) از ریشه‌های یک دستگاه ساده‌تر شروع می‌کند و با ردگیری تبدیل پیوسته‌ی ریشه‌ها به جواب مطلوب می‌رسد. این روش‌ها با دستگاه به صورت کاملاً جبری رفتار می‌کنند و تمام ریشه‌های حقیقی و مختلط را یافته و اطلاعاتی کلی پیرامون مجموعه‌جواب می‌دهند. اگر تنها به ریشه‌های حقیقی نیاز باشد چنین روش‌هایی عموماً چندان مناسب نیستند.
پیش نمایش مقاله
پیش نمایش مقاله حل دستگاه‌های چندجمله‌ای با استفاده از حساب ابرصفحه‌ای و برنامه‌ریزی خطی

چکیده انگلیسی

Solving polynomial systems of equations is an important problem in many fields such as computer-aided design, manufacturing and robotics. In recent years, subdivision-based solvers, which typically make use of the properties of the Bézier/BB-spline representation, have proven successful in solving such systems of polynomial constraints. A major drawback in using subdivision solvers is their lack of scalability. When the given constraint is represented as a tensor product of its variables, it grows exponentially in size as a function of the number of variables. In this paper, we present a new method for solving systems of polynomial constraints, which scales nicely for systems with a large number of variables and relatively low degree. Such systems appear in many application domains. The method is based on the concept of bounding hyperplane arithmetic, which can be viewed as a generalization of interval arithmetic. We construct bounding hyperplanes, which are then passed to a linear programming solver in order to reduce the root domain. We have implemented our method and present experimental results. The method is compared to previous methods and its advantages are discussed.

مقدمه انگلیسی

Solving polynomial systems of equations is a crucial problem in many fields such as robotics [1], computer aided design and manufacturing [2] and [3], and many others [4]. This problem, namely finding the roots of a set of multivariate polynomial equations, is a difficult one and various approaches have been proposed for it. Symbolical approaches, such as Gröbner bases and similar elimination-based techniques [5], map the original system to a simpler one, which preserves the solution set. Polynomial continuation methods (also known as homotopy methods [4]) start at roots of a simpler system and trace a continuous transformation of the roots to the desired solution. These methods handle the system in a purely algebraic manner, find all complex and real roots, and give general information about the solution set. Such methods are typically not well-suited if only real roots are required.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.