کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439461 690773 2014 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Solving multivariate polynomial systems using hyperplane arithmetic and linear programming
ترجمه فارسی عنوان
حل دستگاه‌های چندجمله‌ای با استفاده از حساب ابرصفحه‌ای و برنامه‌ریزی خطی
کلمات کلیدی
حلال زیربخش - حلال چند متغیره - محدودیت های هندسی -
فهرست مطالب مقاله
چکیده
کلید واژه ها
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 بهره می‌برند در سال‌‌های اخیر توانسته‌اند در حل چنین دستگاه‌هایقیدهای چندجمله‌ای موفقیت‌آمیز ظاهر شوند. یک ضعف عمده‌ در استفاده از حل‌کننده‌های زیربخشی فقدان مقیاس‌پذیری آن‌هاست. هنگامی که قید داده‌شده به شکل ضرب تانسوری از متغیرهایش نمایش داده شود، اندازه‌اش به‌صورت تابعی از تعداد متغیرهایش به‌طور نمایی رشد می‌کند. در این مقاله ما روشی جدید برای حل دستگاه‌های قید‌های چندجمله‌ای ارائه می‌کنیم که به‌خوبی برای سیستم‌ها با تعداد زیاد متغیر و درجه‌ی نسبتاً کم مقیاس می‌شود. چنین سیستم‌هایی در حوزه‌های کاربری بسیاری ظاهر می‌شوند. این روش مبتنی بر مفهوم حساب ابرصفحه‌ای کراندار است که می‌توان آن را تعمیمی از حساب بازه‌ای دانست. ما ابرصفحات کراندار را می‌سازیم و سپس به حل‌کننده‌ی برنامه‌ریزی خطی می‌دهیم تا از دامنه‌ی ریشه کاسته شود. ما روش خود را پیاده‌سازی کرده و نتایج عملی را ارائه می‌دهیم. این روش با روش‌های پیشین مقایسه و مزایای آن بحث می‌شوند.
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر گرافیک کامپیوتری و طراحی به کمک کامپیوتر
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer-Aided Design - Volume 46, January 2014, Pages 101–109
نویسندگان
,