ماتریس ها را وارد کنید | news.myScience / news / news 2024

چه توسط انسان یا رایانه انجام شود، ضرب ماتریس یک کار خسته کننده است. محققان در تلاشند تا زمان و تعداد مراحل مورد نیاز برای حل چنین عملیاتی را کاهش دهند.

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

ماتریس ها را می توان به عنوان جداول مقادیر در نظر گرفت. از جمله، آنها توصیف یک سیستم معادلات خطی را به صورت فشرده امکان پذیر می کنند. بیشتر پدیده های فیزیکی، شیمیایی و بیولوژیکی را می توان در قالب ماتریس نشان داد. دومی همچنین می تواند برای مشخص کردن یک شی – مانند یک تصویر، توصیف شده توسط جدولی که مقدار (رنگ، ​​موقعیت و غیره) هر یک از پیکسل های آن را نشان می دهد – و همچنین در یادگیری ماشین، که در آن توضیح داده شده است، استفاده شود. “بیشتر محاسبات در شبکه های عصبی بر روی ماتریس هایی انجام می شود که وضعیت هر یک از آن نورون ها را نشان می دهد.”گابریل پیره، محقق دپارتمان ریاضیات و کاربردها در École Normale Supérieure 1 تاکید می کند.

از جداول تا ماتریس

جد ماتریکس در حدود قرن اول قبل از میلاد ایجاد شد. در سال 200 قبل از میلاد یا پس از میلاد در چین متولد شد. «در کار ناشناس نه فصل در مورد هنر ریاضی، آیا چیزی وجود دارد که شبیه ماتریس باشد؟ فرآیند حل یک سیستم خطی در واقع با توصیف آرایش داده ها در یک جدول آغاز شد. کارینه چملا، محقق تاریخ ریاضیات در آزمایشگاه SPHERE 2 توضیح می‌دهد. نکته جالب در مورد این ترتیب مشابه شماره‌گذاری موقعیتی ما است که جمع را با قرار دادن یک‌ها، ده‌ها، صدها و غیره تسهیل می‌کند. ایده این است که الگوریتم برای حل مسئله بر اساس ترتیب داده ها در یک جدول است.

با این حال، این جداول را نمی توان ماتریس در نظر گرفت زیرا نمی توان از آنها برای انجام عملیات استفاده کرد. این جهش بزرگ در اواسط قرن نوزدهم با کار آرتور کیلی انجام شد. با انجام این کار با این ماتریس ها، او توانست مسائل هندسه را حل کند زیرا آنها می توانند تبدیل هندسی یک جسم، مانند چرخش آن را ثبت کنند. دنباله تبدیل های چندگانه به سادگی ضرب ماتریس هایی است که هر یک نشان دهنده یک تبدیل هندسی است که جسم مورد نظر متحمل می شود. این تکنیک اغلب در گرافیک سه بعدی استفاده می شود.

در دنیای دیجیتالی فزاینده، ضرب ماتریس نقش اصلی را ایفا می کند و نه فقط در ریاضیات. “تقریبا همه الگوریتم ها از ضرب ماتریس برای حل عددی استفاده می کنند.” فرانسوا لو گال، محقق دانشکده ریاضیات دانشگاه ناگویا (ژاپن) را به یاد می آورد. مزیت این است که روش پیش پا افتاده (یا استاندارد) انجام این عملیات تا زمانی که ماتریس از اندازه معقولی باشد به راحتی با دست یا با رایانه قابل انجام است. اشکال این است که تعداد مراحل محاسبه مورد نیاز برای این الگوریتم به صورت تصاعدی با اندازه ماتریس افزایش می یابد. ما می‌توانیم جمع‌ها و ضرب‌های لازم برای ضرب دو ماتریس را با استفاده از الگوریتم بی‌اهمیت بشماریم. برای ماتریسی با n ردیف و n ستون، این سربار که «پیچیدگی الگوریتم» نامیده می شود، n است.³” کلمنت پرنت، دانشمند آزمایشگاه ژان کونتزمن 3 توضیح می دهد. برای مثال، اگر دو ماتریس هر کدام دارای 1000 سطر و 1000 ستون باشند، کامپیوتر (یا انسان) باید 1 میلیارد عملیات (یا 1000) انجام دهد.³) آنها را با موفقیت تکثیر کنید. در واقع، ماتریس‌هایی با این اندازه در برنامه‌های کاربردی، به‌ویژه در یادگیری ماشینی رایج هستند.» لو گال تاکید می کند.

جستجو برای بهترین الگوریتم

در دهه 1960، ریاضیدانان و دانشمندان کامپیوتر به این فکر می کردند که آیا ماتریس ها را می توان با استفاده از عملیات کمتر ضرب کرد. ولکر استراسن متقاعد شده بود که این امکان پذیر نیست. با این وجود، این او بود که الگوریتمی را کشف کرد که می تواند یک محصول ماتریس را در کمتر از n حل کند.³ قدم ها” پرنت با لبخندی کنایه آمیز می گوید. این کشف جرقه جستجویی برای الگوریتم بهینه برای محصولات ماتریسی شد! انگیزه اصلی انجام محاسبات سریع است. Le Gall اضافه می کند. در واقع، ضرب دو ماتریس زمان می برد: 30 ثانیه برای دو ماتریس با 10000 سطر و 10000 ستون، اما 4 دقیقه برای دو برابر تعداد سطرها و ستون ها. یافتن الگوریتمی که تعداد مراحل محاسبه را کاهش دهد، زمان کلی محاسبه را کاهش می دهد. هر چه ماتریس بزرگتر باشد، این کوتاه شدن آشکارتر است.

بیایید الگوریتم بی اهمیت را با یک الگوریتم ضرب فرضی با پیچیدگی n² مقایسه کنیم. هنگام ضرب دو ماتریس با اندازه 3×3، مزیت روش دوم نسبت به الگوریتم بی اهمیت زیاد نیست. با این حال، اگر اندازه ماتریس یک میلیون ردیف و یک میلیون خط باشد، الگوریتم دوم به یک میلیون محاسبه کمتر یا یک میلیون برابر زمان و انرژی کمتر نیاز دارد. انگیزه نظری ما نیز این است که بفهمیم تا چه حد می توانیم مقدار توان n را کاهش دهیم. Le Gall اضافه می کند. آنچه می دانیم این است که حتی با بهینه سازی، الگوریتم نمی تواند زیر پیچیدگی n قرار گیرد²این تعداد سلول ها در ماتریس نتیجه است، یعنی حداقل n² برای نوشتن نتیجه مراحل لازم است. برای کاهش پیچیدگی، محققان بر کاهش تعداد ضرب های مورد نیاز برای حل یک محصول ماتریس تمرکز می کنند. ما می دانیم تعداد جمع هایی که باید انجام شود و نسبت به تعداد ضرب ها کم است. بنابراین، در درجه اول این دومی است که توان n را تعیین می کند.”

پیچیدگی به سختی کمتر

اولین پیشرفت، الگوریتم Volker Strassen، پیچیدگی n را کاهش داد³ تن²⁸⁰⁷. او از روش تقسیم و غلبه استفاده کرد، که شامل تجزیه مسئله (در اینجا ماتریس) به چندین مشکل فرعی (قسمت های ماتریس) و اینها به نوبه خود به مسائل فرعی دیگر تا زمانی که فرد منحصراً ماتریس هایی با اندازه 2 x بدست آورد، استفاده کرد. 2. تنها چیزی که باقی می ماند این است که این نتایج را ضرب کنیم تا به راه حل نهایی برسیم. به این ترتیب، ضرب دو ماتریس با اندازه 2×2 نیاز به یک ضرب کمتر از روش بی اهمیت دارد و ضرب ماتریس هایی با اندازه 10000×10000 صرفه جویی در زمان تقریباً 28 درصد را فراهم می کند. “به گفته فولکر استراسن، ده سال پیشرفتی حاصل نشد. سپس، بین سال های 1978 و اواخر دهه 1980، رقابت شدیدی وجود داشت! تعدادی از پیشرفت‌های کوچک‌تر، ابتدا به لطف تحقیقات مداوم استراسن و بعداً به لطف ریاضی‌دانان Shmuel Winograd و Don Coppersmith، که از روش متفاوتی برای تجزیه ماتریس‌ها برای کاهش پیچیدگی به n استفاده کردند، کشف شد.^2,376.

از سال 2010، پیشرفت های پی در پی در بهبود این روش با دقت بالا صورت گرفته است. ژو رنفی و همکارانش در موسسه علوم اطلاعات میان رشته‌ای (IIIS) در دانشگاه تسینگ‌هوا (چین) با کاهش توان از 2.372860 به 2.371866 به آخرین بهینه‌سازی تا به امروز در پایان سال 2023 دست یافتند. این نتیجه ممکن است زیاد به نظر نرسد، اما از نظر ریاضی بسیار مهم است. «آنها دریافتند که چیزی غیربهینه در مورد روش مسمیت و وینوگراد وجود دارد. چیزی که ما نادیده گرفته بودیم.” به لو گال تبریک می گوید.

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