الگوریتم کوپراسمیت–وینوگارد

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در رشته ی جبر خطی ریاضیات، الگوریتم Coppersmith–Winograd که بر اساس نام Don Coppersmith و Shmuel Winograd نام گذاری شده، سریعترین الگوریتم شناخته شده از لحاظ مجانبی برای ضرب ماتریس های مربعی از سال 2008 به بعد است. این الگوریتم می تواند دو ماتریس n \times n را در زمان O(n^{2.3727}) (نماد O بزرگ را ببینید) در هم ضرب کند. این زمان به نسبت الگوریتم کم اهمیتی با زمان O(n^3) و الگوریتم استراسن با زمان O(n^{2.807}) یک پیشرفت محسوب می شود. شاید بهبود این توان ممکن باشد ولی حداقل می تواند ۲ باشد (زیرا یک ماتریس n \times n، n^2 مقدار دارد و تمام این مقادیر برای محاسبه ی جواب دقیق می بایست حداقل یکبار خوانده شوند). پیچیدگی این الگوریتم از O(n^{2.3755}) محاسبه شد.[۱]

در سال 2010، [۲]Stothers و [۳]Williams هر کدام به طور مستقل این الگوریتم را به O(n^{2.3737}) ارتقا دادند. این پیشرفت ها بر اساس استفاده از حاصل ضرب های تانسوری پیچیده تر بود.

الگوریتم Coppersmith–Winograd اغلب به عنوان یک بلاک سازنده برای تئوری اثبات حد زمانی در بقیه الگوریتم ها استفاده می شود. با این وجود بر خلاف الگوریتم استراسن در عمل استفاده نمی‌شود زیرا تنها مزیتی برای ماتریس های بسیار بزرگ فراهم می کند که نمی‌توانند توسط سخت افزارهای کنونی پردازش شوند.[۴]

Henry Cohn، Robert Kleinberg، Balázs Szegedy و Christopher Umans با استفاده از ساختار نظریه گروه ها الگوریتم Coppersmith–Winograd را مجدداً طراحی کردند. آن ها همچنین نشان دادند که هر یک از دو حدس این مفهوم را می رساند که بهینه ترین توان ضرب ماتریس ها، همان طور که از قبل انتظار می رفت، ۲ می باشد. [۵]

زمان اجرا[ویرایش]

ابتدایی ترین الگوریتم ضرب دو ماتریس مربعی n × n به (O(n۳ ضرب نیاز دارد. استراسن در سال ۱۹۸۷ الگوریتمی ارائه داد که ضرب دو ماتریس را در مرتبه زمانی O(n۲/۸۰۷ انجام می دهد.الگوریتم کاپرایمیت - وینوگراد که توسط Don Coppersmith و Shmuel Winograd در سال ۱۹۸۷ ارائه شده است، بهینه ترین الگوریتم برای ضرب دو ماتریس است که تاکنون شناخته شده که از مرتبه زمانی O(n۲/۳۷٦ است. می توان توان n را کمتر کرد، ولی حداقل توان باید ۲ باشد. زیرا ماتریس n × n دارای n۲ مقدار است که برای ضرب دو ماتریس هر کدام باید حداقل یکبار خوانده شود.

جدول زیر کاهش مرتبه زمانی را نشان می دهد:

سال
١٩٦٩> ٣ مثال
١٩٦٩ ٢.٨١ Strassen
١٩٧٨ ٢.٧٩ Pan
١٩٧٩ ٢.٧٨ Bini et al
١٩٨١ ٢.٥٥ Schonhage
١٩٨٢ ٢.٥٠ Pan; Romani; CW
١٩٨٧ ٢.٤٨ Strassen
١٩٨٧ ٢.٣٨ CW

از الگوریتم کاپراسمیت-وینوگراد نمی توان در عمل استفاده کرد، زیرا ضریب ثابت آن بسیار بزرگ است و فقط برای ضرب ماتریس های خیلی بزرگ می توان از آن استفاده کرد که سخت افزارهای امروزی قابلیت پردازش آن ها را ندارند.

پانویس[ویرایش]

  1. In the Coppersmith and Winograd's original paper
  2. Stothers, Andrew (2010), On the Complexity of Matrix Multiplication .
  3. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier .
  4. Robinson, Sara (2005), Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38 (9) 
  5. Cohn, H.; Kleinberg, R.; Szegedy, B.; Umans, C. (2005). "Group-theoretic Algorithms for Matrix Multiplication". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). pp. 379. doi:10.1109/SFCS.2005.39. ISBN 0-7695-2468-0

منابع[ویرایش]