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

در رشتهٔ جبر خطی ریاضیات، الگوریتم Coppersmith–Winograd که بر اساس نام Don Coppersmith  و Shmuel Winograd نام گذاری شده، سریعترین الگوریتم شناخته شده از لحاظ مجانبی برای ضرب ماتریس‌های مربعی از سال 2008 به بعد است. این الگوریتم می‌تواند دو ماتریس  را در زمان  (نماد O بزرگ را ببینید) در هم ضرب کند. این زمان به نسبت الگوریتم کم اهمیتی با زمان  و الگوریتم استراسن با زمان  یک پیشرفت محسوب می‌شود. شاید بهبود این توان ممکن باشد ولی حداقل می‌تواند ۲ باشد (زیرا یک ماتریس ،  مقدار دارد و تمام این مقادیر برای محاسبهٔ جواب دقیق می بایست حداقل یکبار خوانده شوند). پیچیدگی این الگوریتم از  محاسبه شد.

در سال 2010، Stothers و Williams هر کدام به‌طور مستقل این الگوریتم را به  ارتقا دادند. این پیشرفت‌ها بر اساس استفاده از حاصل ضرب‌های تانسوری پیچیده تر بود.

الگوریتم 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۲ مقدار است که برای ضرب دو ماتریس هر کدام باید حداقل یکبار خوانده شود.

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

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

پانویس

منابع 

 .
 .
 http://en.wikipedia.org/wiki/Coppersmith-Winograd_algorithm

الگوریتم‌ها
الگوریتم‌های ضرب ماتریس
جبر خطی عددی
ماتریس‌ها