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

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

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

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

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

زمان اجرا

ابتدایی‌ترین الگوریتم ضرب دو ماتریس مربعی 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 (PDF), archived from the original (PDF) on 15 December 2011, retrieved 7 December 2011.
3. Williams, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF), archived from the original (PDF) on 20 January 2013, retrieved 7 December 2011.
4. Robinson, Sara (2005), "Toward an Optimal Algorithm for Matrix Multiplication" (PDF), SIAM News, 38 (9), archived from the original (PDF) on 31 March 2010, retrieved 7 December 2011
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. شابک ‎۰−۷۶۹۵−۲۴۶۸−۰

منابع

• Coppersmith, Don; Winograd, Shmuel (1990), "Matrix multiplication via arithmetic progressions" (PDF), Journal of Symbolic Computation, 9 (3): 251–280, doi:10.1016/S0747-7171(08)80013-2, archived from the original (PDF) on 9 June 2011, retrieved 7 December 2011.
• William, Virginia (2011), Breaking the Coppersmith-Winograd barrier (PDF), archived from the original (PDF) on 20 January 2013, retrieved 7 December 2011.
• http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm