عملیات ماتریسی در خیلی از علوم مثل ریاضی، فیزیک، بیوانفورماتیک، شیمی-فیزیک و … اهمیت دارد. اهمیت این عملیات وقتی بیشتر می‌شود که با داده‌های زیادی سر و کار داشته باشیم و به نوعی دو ماتریس بزرگ قرار باشد در هم ضرب شوند.
در حال حاضر الگوریتمهای مختلفی برای ضرب ماتریسها وجود دارد:
و در ضمن سریعترین الگوریتم ضرب ماتریسی به عنوان یک سوال بدون حل در علوم کامپیوتر مطرح می‌شود:
چرا سریعترین الگوریتم ضرب ماتریسی نامشخص است؟
سریعترین الگوریتم ضرب ماتریسی به لحاظ ریاضی کاملا حل شده است اما از نظر یک دانشمند علوم کامپیوتر نه. سرعت رشد و تنوع در معماری سخت افزارها باعث میشه این مسئله همیشه با اهمیت باشه و هیچ وقت راه حل نهایی براش ارایه نشه. همین مورد رو میشه در مورد خیلی از الگوریتمهای دیگه هم دید. مثلا تبدیل فوریه به لحاظ ریاضی کاملا حل شده است اما از نظر یک دانشمند علوم کامپیوتر که قصد پیاده‌سازی این الگوریتم روی تعداد زیادی پردازشگر رو داره هنوز مسئله حل نشده.
شیوه محاسبه ضرب دو ماتریس در کامپیوتر با آنچه که در ذهن یک ریاضی‌دان وجود داره خیلی فرق میکنه. داده‌ها پیش از رسیدن به واحد پردازش کامپیوتر باید از حافظه‌های مختلفی عبور کنند. این که چه طوری داده‌ها رو برای پردازش آماده کنیم و به واحد پردازش بفرستیم سرعت اجرای ضرب دو ماتریس رو شدیدا تحت تاثیر قرار میده. سخت‌افزارها با گذشت زمان تغییر می‌کنند و در نتیجه شیوه پیاده‌سازی الگوریتمها هم پیوسته تغییر خواهند کرد.
نکته دیگه این که سرعت رشد نرم‌افزار و سخت افزار با هم خیلی تفاوت داره. مثلا سال‌هاست که کامپیوترها و گوشی‌های موبایل چند تا پردازنده دارند اما هنوز خیلی از نرم‌افزارها فقط روی یک پردازنده اجرا میشن در حالی که بقیه پردازنده‌ها بی کار هستند.
سریعترین الگوریتم ضرب ماتریسی از نظر ریاضی هم پیدا نشده
اگر ماتریسهایی که قراره ضرب بشن N*N باشن تعداد عملیاتها برای روش معمولی ضرب کردن ماتریس متناسب با 3N هست (تقریبا یعنی زمان محاسبه با توان ۳ اندازه ماتریس رشد میکنه)
اینجا ولی الگوریتمهایی هست که سریعترن (در واقع نرخ رشد زمانشون کمتره و این باعث میشه که برای ماتریسهایی که از یه اندازه‌ای بزرگترن سریعتر باشن)
الگوریتم strassen که استراتژی divide and conquer داره نیاز به 2.807 N^(log2(7)) = N عملیات داره (در حد N بزرگ)
الگوریتم استراسن با جدا کردن هر ماتریس به چهار ماتریس کار میکنه
الگوریتمهایی هستن که ماتریسها رو در هر مرحله به بخشهای بیشتری تقسیم میکنن و سرعت رشد زمان محاسباتشون کمتره
تو همون لیست الگوریتمهای ضرب ماتریس هم هست که کلا از اون استراتژی استفاده نمیکنن و سرعت رشد زمانشون حتی کمتره
از طرفی تو ریاضیات حد پایینی برای تعداد عملیات لازم برای ضرب ماتریس (بدون در نظر گرفتن هیچ الگوریتمی) در میارن که برای ضرب ماتریس تو اون صفحه N2 log(N) گفته شده بود
چون این دو تا هنوز به هم نرسیدن مساله حل نشده است و برای حل شدن یا حداقل زمان لازم باید در ریاضیات اثبات بشه که بالاتره یا الگوریتمی با این سرعت رشد پیدا بشه.
اما مثلا مساله سریعترین الگوریتم مرتب کردن اعداد (با عملیاتهای مقایسه‌ای) حل شده است.
جایگشتهای یه آرایه مرتب نشده N فاکتوریل هست. نتیجه هر مقایسه دو حالت داره (یا درست هست یا غلط) و با هر بار مقایسه میشه نصفی از جایگشتها رو از بقیه تمیز داد. پس برای این جایگشت آرایه ورودی پیدا بشه حداقل به log2(N!) مقایسه نیاز هست. از تقریب استرلینگ میدونیم در حد N بزرگ، بزرگترین جمله اون N log(N) هست و خیلی از الگوریتمها هستن که تعداد محاسباتشون متناسب با N log(N) هست پس حل شده هست.
پ ن: در حد N به سمت بینهایت log(N) از N به توان هر عدد مثبتی کوچکتر است