پیشرفت جدید ضرب ماتریس را به ایده آل نزدیک می کند | مجله کوانتا

دانشمندان کامپیوتر گروهی خواستار هستند. برای آنها، دریافت پاسخ صحیح برای یک مشکل کافی نیست - هدف، تقریباً همیشه، دریافت پاسخ تا حد امکان کارآمد است.

عمل ضرب ماتریس ها یا آرایه های اعداد را در نظر بگیرید. در سال 1812، ژاک فیلیپ ماری بینه، ریاضیدان فرانسوی، مجموعه ای از قوانین اساسی را ارائه کرد که هنوز به دانش آموزان آموزش می دهیم. این کاملاً خوب کار می کند، اما دیگر ریاضیدانان راه هایی برای ساده سازی و سرعت بخشیدن به این فرآیند پیدا کرده اند. در حال حاضر وظیفه از تسریع در روند ضرب ماتریس در تقاطع ریاضیات و علوم کامپیوتر قرار دارد، جایی که محققان تا به امروز به بهبود این فرآیند ادامه می‌دهند - اگرچه در دهه‌های اخیر دستاوردها نسبتاً کم بوده است. از سال 1987، بهبودهای عددی در ضرب ماتریس "کوچک و ... بسیار دشوار به دست آمده است." فرانسوا لو گال، دانشمند کامپیوتر در دانشگاه ناگویا.

اکنون، سه محقق - ران دوان و رنفی ژو از دانشگاه تسینگ‌هوا و هونگ‌سون وو از دانشگاه کالیفرنیا، برکلی - گام بزرگی در حمله به این مشکل همیشگی برداشته‌اند. آنها نتایج جدیدلو گال گفت، که در نوامبر گذشته در کنفرانس مبانی علوم کامپیوتر ارائه شد، از یک تکنیک جدید غیرمنتظره سرچشمه می گیرد. اگرچه خود بهبود نسبتاً کوچک بود، لی گال آن را "از لحاظ مفهومی بزرگتر از سایر موارد قبلی" نامید.

این تکنیک منبعی از پیشرفت‌های بالقوه ناشناخته را که قبلاً ناشناخته و در نتیجه دست‌نخورده بود را نشان می‌دهد و قبلاً به ثمر نشسته است: کاغذ دوم، که در ژانویه منتشر شد، بر اساس اولین مورد است که نشان می دهد چگونه ضرب ماتریس را می توان حتی بیشتر تقویت کرد.

گفت: "این یک پیشرفت فنی بزرگ است." ویلیام کوزمول، دانشمند نظری کامپیوتر در دانشگاه هاروارد. "این بزرگترین پیشرفت در ضرب ماتریس است که در بیش از یک دهه دیده ایم."

ماتریس را وارد کنید

ممکن است مشکلی مبهم به نظر برسد، اما ضرب ماتریس یک عملیات محاسباتی اساسی است. این الگوریتم در بخش بزرگی از الگوریتم‌هایی گنجانده شده است که مردم هر روز برای کارهای مختلف از نمایش گرافیک‌های کامپیوتری واضح‌تر گرفته تا حل مشکلات لجستیکی در تئوری شبکه استفاده می‌کنند. و مانند سایر حوزه های محاسباتی، سرعت در اولویت قرار دارد. حتی پیشرفت های جزئی در نهایت می تواند منجر به صرفه جویی قابل توجهی در زمان، قدرت محاسباتی و پول شود. اما در حال حاضر، نظریه پردازان عمدتاً علاقه مند هستند که بفهمند این روند تا چه حد می تواند سریع باشد.

روش سنتی ضرب دو n-توسط-n ماتریس - با ضرب اعداد از هر ردیف در ماتریس اول در اعداد در ستون های ماتریس دوم - نیاز دارد n³ ضرب جدا برای ماتریس های 2 در 2، این به معنای 2 است³ یا 8 ضرب.

در سال 1969، ریاضیدان فولکر استراسن روش پیچیده تری را نشان داد که می توانست ماتریس های 2 در 2 را تنها در هفت مرحله ضربی و 18 جمع ضرب کند. دو سال بعد، دانشمند کامپیوتر Shmuel Winograd نشان داد که هفت در واقع حداقل مطلق برای ماتریس های 2 در 2 است.

استراسن از همین ایده استفاده کرد تا نشان دهد که همه بزرگتر هستند n-توسط-n ماتریس ها را نیز می توان در کمتر از ضرب کرد n³ مراحل یک عنصر کلیدی در این استراتژی شامل رویه‌ای به نام تجزیه است - شکستن یک ماتریس بزرگ به زیرماتریس‌های متوالی کوچک‌تر، که ممکن است در نهایت به کوچکی 2 در 2 یا حتی 1 در 1 شوند (اینها فقط اعداد منفرد هستند).

منطق تقسیم یک آرایه غول پیکر به قطعات کوچک بسیار ساده است ویرجینیا واسیلوسکا ویلیامز، دانشمند کامپیوتر در موسسه فناوری ماساچوست و یکی از نویسندگان یکی از مقالات جدید. واسیلوسکا ویلیامز گفت: «برای یک انسان سخت است که به یک ماتریس بزرگ (مثلاً در مرتبه 100 در 100) نگاه کند و به بهترین الگوریتم ممکن فکر کند. حتی ماتریس های 3 در 3 هنوز به طور کامل حل نشده اند. با این وجود، می‌توان از الگوریتم سریعی که قبلاً برای ماتریس‌های کوچک ایجاد کرده است استفاده کرد تا یک الگوریتم سریع برای ماتریس‌های بزرگتر نیز به دست آورد.»

محققین تعیین کرده‌اند که کلید سرعت این است که تعداد گام‌های ضرب را کاهش داده و این توان را از آن کاهش دهیم n³ (برای روش استاندارد) تا آنجا که می توانند. کمترین مقدار ممکن، n²، اساساً به اندازه ای است که فقط نوشتن پاسخ طول می کشد. دانشمندان کامپیوتر از آن توان به عنوان امگا، ω، با نام می برند n^ω این کمترین گام ممکن برای ضرب موفقیت آمیز دو است n-توسط-n ماتریس به عنوان n بسیار بزرگ می شود ژو که یکی از نویسندگان مقاله ژانویه 2024 است، گفت: «نکته این کار این است که ببینید چقدر می‌توانید به 2 نزدیک شوید و آیا می‌توان به صورت تئوری به آن دست یافت.»

فوکوس لیزری

در سال 1986، استراسن یک پیشرفت بزرگ دیگر داشت معرفی چیزی که روش لیزری برای ضرب ماتریس نامیده می شود. استراسن از آن برای تعیین مقدار بالای امگا 2.48 استفاده کرد. در حالی که این روش تنها یک مرحله در ضرب‌های ماتریس بزرگ است، اما یکی از مهم‌ترین آنهاست زیرا محققان به بهبود آن ادامه داده‌اند.

یک سال بعد، Winograd و Don Coppersmith الگوریتم جدیدی را معرفی کردند که به زیبایی روش لیزر را تکمیل می کرد. این ترکیب از ابزارها تقریباً در تمام تلاش‌های بعدی برای سرعت بخشیدن به ضرب ماتریس برجسته شده است.

در اینجا یک روش ساده برای تفکر در مورد اینکه چگونه این عناصر مختلف با هم تطبیق می یابند وجود دارد. بیایید با دو ماتریس بزرگ A و B شروع کنیم که می خواهید با هم ضرب کنید. ابتدا، شما آنها را به زیرماتریس‌ها یا بلوک‌های کوچک‌تر، همانطور که گاهی اوقات نامیده می‌شود، تجزیه می‌کنید. در مرحله بعد، می‌توانید از الگوریتم Coppersmith و Winograd استفاده کنید تا به‌عنوان نوعی راهنمای دستورالعمل برای جابجایی، و در نهایت مونتاژ بلوک‌ها عمل کند. واسیلوسکا ویلیامز گفت: «این به من می‌گوید چه چیزی را ضرب کنم و چه چیزی را اضافه کنم و چه ورودی‌هایی کجا می‌روند» در ماتریس محصول C. "این فقط یک دستور العمل برای ایجاد C از A و B است."

با این حال یک نکته وجود دارد: شما گاهی اوقات با بلوک هایی مواجه می شوید که ورودی های مشترک دارند. گذاشتن این موارد در محصول شبیه به شمارش دوبار آن ورودی‌ها خواهد بود، بنابراین در برخی مواقع باید از شر اصطلاحات تکراری خلاص شوید که همپوشانی نامیده می‌شوند. محققان این کار را با "کشتن" بلوک هایی که در آن قرار دارند انجام می دهند - اجزای آنها را برابر با صفر قرار می دهند تا آنها را از محاسبات حذف کنند.

در اینجاست که روش لیزری Strassen بالاخره وارد عمل می شود. لو گال گفت: «روش لیزری معمولاً بسیار خوب عمل می‌کند و به طور کلی راه خوبی برای از بین بردن زیرمجموعه‌ای از بلوک‌ها برای حذف همپوشانی پیدا می‌کند. بعد از اینکه لیزر تمام همپوشانی ها را از بین برد، یا «سوخت»، می توانید ماتریس محصول نهایی، C را بسازید.

کنار هم قرار دادن این تکنیک‌های مختلف منجر به الگوریتمی برای ضرب دو ماتریس با تعداد ضرب‌های عمداً خسیسی می‌شود - حداقل در تئوری. روش لیزری عملی نیست. این فقط راهی برای فکر کردن در مورد راه ایده آل برای ضرب ماتریس است. ژو گفت: «ما هرگز این روش را [روی رایانه] اجرا نمی کنیم. "ما آن را تجزیه و تحلیل می کنیم."

و این تجزیه و تحلیل همان چیزی است که منجر به بزرگترین بهبود امگا در بیش از یک دهه گذشته شده است.

ضرر پیدا شد

مقاله تابستان گذشته، توسط دوان، ژو و وو، نشان داد که روند استراسن هنوز هم می تواند به طور قابل توجهی تسریع شود. ژو گفت، همه اینها به دلیل مفهومی بود که آنها آن را فقدان پنهان می نامیدند، که در اعماق تجزیه و تحلیل های قبلی مدفون شده بود - "نتیجه کشتن ناخواسته تعداد زیادی بلوک".

روش لیزری با برچسب زدن بلوک‌های دارای همپوشانی به‌عنوان زباله‌ای که برای دفع قفسه‌بندی شده‌اند، کار می‌کند. بلوک های دیگر شایسته تلقی می شوند و ذخیره خواهند شد. روند انتخاب، با این حال، تا حدودی تصادفی است. بلوکی که به عنوان زباله رتبه بندی می شود، در واقع ممکن است مفید واقع شود. این کاملاً غافلگیرکننده نبود، اما با بررسی بسیاری از این انتخاب‌های تصادفی، تیم Duan به این نتیجه رسیدند که روش لیزری به طور سیستماتیک بلوک‌ها را کم‌ارزش می‌کند: بلوک‌های بیشتری باید ذخیره شوند و تعداد کمتری بیرون ریخته شود. و همانطور که معمولاً اتفاق می‌افتد، ضایعات کمتر منجر به کارایی بیشتر می‌شود.

لو گال گفت: «بتوانیم بلوک‌های بیشتری را بدون همپوشانی نگه داریم، بنابراین منجر به ... الگوریتم ضرب ماتریس سریع‌تر می‌شود».

پس از اثبات وجود این از دست دادن، تیم Duan روشی را که روش لیزری بر روی بلوک‌ها برچسب‌گذاری می‌کرد، تغییر داد و ضایعات را به میزان قابل توجهی کاهش داد. در نتیجه، آنها یک کران بالای جدید برای امگا در حدود 2.371866 تعیین کردند - که نسبت به کران بالای قبلی 2.3728596 بهبود یافته است. در سال 2020 تنظیم شده است توسط جاش المان و واسیلوسکا ویلیامز. این ممکن است یک تغییر کوچک به نظر برسد و حدود 0.001 کران را کاهش دهد. اما این تنها بزرگترین پیشرفتی است که دانشمندان از سال 2010 مشاهده کرده اند. نتایج Vassilevska Williams و Alman در سال 2020، در مقایسه، نسبت به سلف خود تنها 0.00001 بهبود یافته است.

اما چیزی که برای محققان هیجان انگیزتر است فقط خود رکورد جدید نیست - که مدت زیادی دوام نیاورد. همچنین این واقعیت است که این روزنامه مسیر جدیدی را برای بهبود نشان می‌دهد که تا آن زمان کاملاً مورد توجه قرار نمی‌گرفت. لو گال گفت که برای نزدیک به چهار دهه، همه به روش لیزری مشابهی تکیه کرده اند. "سپس آنها دریافتند که خوب، ما می توانیم بهتر عمل کنیم."

مقاله ژانویه 2024 این رویکرد جدید را اصلاح کرد و به واسیلوسکا ویلیامز، ژو و نویسندگان همکار آنها این امکان را داد تا ضرر پنهان را بیشتر کاهش دهند. این منجر به بهبود بیشتر کران بالایی امگا شد و آن را به 2.371552 کاهش داد. نویسندگان همچنین همان تکنیک را برای بهبود فرآیند ضرب برای مستطیل (n-توسط-m) ماتریس - رویه ای که در نظریه گراف، یادگیری ماشین و سایر زمینه ها کاربرد دارد.

برخی پیشرفت‌های بیشتر در این مسیر کاملاً قطعی است، اما محدودیت‌هایی وجود دارد. در سال 2015، لو گال و دو همکار ثابت که رویکرد فعلی - روش لیزر همراه با دستور مسمیت-وینوگراد - نمی تواند امگا کمتر از 2.3078 به دست آورد. لو گال گفت: برای انجام هر گونه پیشرفت بیشتر، «شما باید رویکرد اصلی Coppersmith و Winograd را که واقعاً از سال 1987 تغییر نکرده است، بهبود بخشید." اما تاکنون هیچ کس راه بهتری برای این کار پیدا نکرده است. حتی ممکن است یکی نباشد.

ژو گفت: «بهبود امگا در واقع بخشی از درک این مشکل است. اگر بتوانیم مشکل را به خوبی درک کنیم، می توانیم الگوریتم های بهتری برای آن طراحی کنیم. [و] مردم هنوز در مراحل اولیه درک این مشکل قدیمی هستند."