A fast method for finding the basis of non-negative solutions to a linear diophantine equation

دسته بندی: نظریه شماره
ویرایش:  
نویسندگان: Filgueiras M.,  Tomas A.P.  
سری:  
 
ناشر:  
سال نشر:  
تعداد صفحات: 20 
زبان: English 
فرمت فایل : DJVU (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 422 کیلوبایت 

قیمت کتاب (تومان) : 47,000

مجله محاسبات نمادین. — 1995. — №19 — С. 507-526 ما یک توصیف کامل از مجموعه راه حل های حداقل یک معادله دیوفانتین خطی در سه مجهول بر روی اعداد طبیعی ارائه می دهیم. این مشخصه که برای آن یک تفسیر هندسی می‌دهیم، بر اساس ویژگی‌های شناخته شده همخوانی‌ها است و از آن به عنوان پایه الگوریتم‌های مستقیم برای حل این نوع خاص از معادله استفاده می‌کنیم. سپس این الگوریتم‌های مستقیم و یک روش شمارش با هم ترکیب می‌شوند تا الگوریتمی برای حل حالت کلی یک معادله دیوفانتین بر روی طبیعی‌ها بسازند. ما همچنین یک روش آماری برای مقایسه الگوریتم‌های حل معادلات دیوفانتین ارائه کردیم که نسبت به مقایسه‌ها بر اساس زمان‌های مشاهده شده برای مجموعه‌های کوچکی از معادلات صحیح‌تر است. از مقایسه گسترده با الگوریتم‌هایی که توسط نویسندگان دیگر توصیف شده‌اند، مشخص می‌شود که الگوریتم ما سریع‌ترین الگوریتم شناخته شده تا به امروز برای یک کلاس از معادلات است. معمولاً معادلات این کلاس دارای تعداد کمی مجهول در یک طرف هستند که حداکثر مقدار ضرایب آنها بیشتر از 3 است.

Journal of Symbolic Computation. — 1995. — №19 — С. 507-526 We present a complete characterization of the set of minimal solutions of a single linear Diophantine equation in three unknowns over the natural numbers. This characterization, for which we give a geometric interpretation, is based on well-known properties of congruences and we use it as the foundation of direct algorithms for solving this particular kind of equation. These direct algorithms and an enumeration procedure are then pur together to build an algorithm for solving the general case of a Diophantine equation over the naturals. We also put forth a statistical method for comparing algorithms for solving Diophantine equations which is more sound than comparisons based on times observed for small sets of equations. From an extensive comparison with algorithms described by other authors it becomes clear that our algorithm is the fastest known to date for a class of equations. Typically the equations in this class have a small number of unknowns in one side, the maximum value for their coefficients being greater than 3