معرفی
دانشمندان کامپیوتر گروهی خواستار هستند. برای آنها، دریافت پاسخ صحیح برای یک مشکل کافی نیست - هدف، تقریباً همیشه، دریافت پاسخ تا حد امکان کارآمد است.
عمل ضرب ماتریس ها یا آرایه های اعداد را در نظر بگیرید. در سال 1812، ژاک فیلیپ ماری بینه، ریاضیدان فرانسوی، مجموعه ای از قوانین اساسی را ارائه کرد که هنوز به دانش آموزان آموزش می دهیم. این کاملاً خوب کار می کند، اما دیگر ریاضیدانان راه هایی برای ساده سازی و سرعت بخشیدن به این فرآیند پیدا کرده اند. در حال حاضر وظیفه از تسریع در روند ضرب ماتریس در تقاطع ریاضیات و علوم کامپیوتر قرار دارد، جایی که محققان تا به امروز به بهبود این فرآیند ادامه میدهند - اگرچه در دهههای اخیر دستاوردها نسبتاً کم بوده است. از سال 1987، بهبودهای عددی در ضرب ماتریس "کوچک و ... بسیار دشوار به دست آمده است." فرانسوا لو گال، دانشمند کامپیوتر در دانشگاه ناگویا.
اکنون، سه محقق - ران دوان و رنفی ژو از دانشگاه تسینگهوا و هونگسون وو از دانشگاه کالیفرنیا، برکلی - گام بزرگی در حمله به این مشکل همیشگی برداشتهاند. آنها نتایج جدیدلو گال گفت، که در نوامبر گذشته در کنفرانس مبانی علوم کامپیوتر ارائه شد، از یک تکنیک جدید غیرمنتظره سرچشمه می گیرد. اگرچه خود بهبود نسبتاً کوچک بود، لی گال آن را "از لحاظ مفهومی بزرگتر از سایر موارد قبلی" نامید.
این تکنیک منبعی از پیشرفتهای بالقوه ناشناخته را که قبلاً ناشناخته و در نتیجه دستنخورده بود را نشان میدهد و قبلاً به ثمر نشسته است: کاغذ دوم، که در ژانویه منتشر شد، بر اساس اولین مورد است که نشان می دهد چگونه ضرب ماتریس را می توان حتی بیشتر تقویت کرد.
معرفی
گفت: "این یک پیشرفت فنی بزرگ است." ویلیام کوزمول، دانشمند نظری کامپیوتر در دانشگاه هاروارد. "این بزرگترین پیشرفت در ضرب ماتریس است که در بیش از یک دهه دیده ایم."
ماتریس را وارد کنید
ممکن است مشکلی مبهم به نظر برسد، اما ضرب ماتریس یک عملیات محاسباتی اساسی است. این الگوریتم در بخش بزرگی از الگوریتمهایی گنجانده شده است که مردم هر روز برای کارهای مختلف از نمایش گرافیکهای کامپیوتری واضحتر گرفته تا حل مشکلات لجستیکی در تئوری شبکه استفاده میکنند. و مانند سایر حوزه های محاسباتی، سرعت در اولویت قرار دارد. حتی پیشرفت های جزئی در نهایت می تواند منجر به صرفه جویی قابل توجهی در زمان، قدرت محاسباتی و پول شود. اما در حال حاضر، نظریه پردازان عمدتاً علاقه مند هستند که بفهمند این روند تا چه حد می تواند سریع باشد.
روش سنتی ضرب دو n-توسط-n ماتریس - با ضرب اعداد از هر ردیف در ماتریس اول در اعداد در ستون های ماتریس دوم - نیاز دارد n3 ضرب جدا برای ماتریس های 2 در 2، این به معنای 2 است3 یا 8 ضرب.
در سال 1969، ریاضیدان فولکر استراسن روش پیچیده تری را نشان داد که می توانست ماتریس های 2 در 2 را تنها در هفت مرحله ضربی و 18 جمع ضرب کند. دو سال بعد، دانشمند کامپیوتر Shmuel Winograd نشان داد که هفت در واقع حداقل مطلق برای ماتریس های 2 در 2 است.
استراسن از همین ایده استفاده کرد تا نشان دهد که همه بزرگتر هستند n-توسط-n ماتریس ها را نیز می توان در کمتر از ضرب کرد n3 مراحل یک عنصر کلیدی در این استراتژی شامل رویهای به نام تجزیه است - شکستن یک ماتریس بزرگ به زیرماتریسهای متوالی کوچکتر، که ممکن است در نهایت به کوچکی 2 در 2 یا حتی 1 در 1 شوند (اینها فقط اعداد منفرد هستند).
منطق تقسیم یک آرایه غول پیکر به قطعات کوچک بسیار ساده است ویرجینیا واسیلوسکا ویلیامز، دانشمند کامپیوتر در موسسه فناوری ماساچوست و یکی از نویسندگان یکی از مقالات جدید. واسیلوسکا ویلیامز گفت: «برای یک انسان سخت است که به یک ماتریس بزرگ (مثلاً در مرتبه 100 در 100) نگاه کند و به بهترین الگوریتم ممکن فکر کند. حتی ماتریس های 3 در 3 هنوز به طور کامل حل نشده اند. با این وجود، میتوان از الگوریتم سریعی که قبلاً برای ماتریسهای کوچک ایجاد کرده است استفاده کرد تا یک الگوریتم سریع برای ماتریسهای بزرگتر نیز به دست آورد.»
محققین تعیین کردهاند که کلید سرعت این است که تعداد گامهای ضرب را کاهش داده و این توان را از آن کاهش دهیم n3 (برای روش استاندارد) تا آنجا که می توانند. کمترین مقدار ممکن، n2، اساساً به اندازه ای است که فقط نوشتن پاسخ طول می کشد. دانشمندان کامپیوتر از آن توان به عنوان امگا، ω، با نام می برند 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 تغییر نکرده است، بهبود بخشید." اما تاکنون هیچ کس راه بهتری برای این کار پیدا نکرده است. حتی ممکن است یکی نباشد.
ژو گفت: «بهبود امگا در واقع بخشی از درک این مشکل است. اگر بتوانیم مشکل را به خوبی درک کنیم، می توانیم الگوریتم های بهتری برای آن طراحی کنیم. [و] مردم هنوز در مراحل اولیه درک این مشکل قدیمی هستند."
- محتوای مبتنی بر SEO و توزیع روابط عمومی. امروز تقویت شوید.
- PlatoData.Network Vertical Generative Ai. به خودت قدرت بده دسترسی به اینجا.
- PlatoAiStream. هوش وب 3 دانش تقویت شده دسترسی به اینجا.
- PlatoESG. کربن ، CleanTech، انرژی، محیط، خورشیدی، مدیریت پسماند دسترسی به اینجا.
- PlatoHealth. هوش بیوتکنولوژی و آزمایشات بالینی. دسترسی به اینجا.
- منبع: https://www.quantamagazine.org/new-breakthrough-brings-matrix-multiplication-closer-to-ideal-20240307/
- : دارد
- :است
- :نه
- :جایی که
- ][پ
- $UP
- 001
- 2015
- 2020
- 2024
- 8
- a
- قادر
- درباره ما
- مطلق
- مطابق
- دست
- ACM
- عمل
- واقعا
- اضافه کردن
- اضافی
- اضافات
- پس از
- قدیمی
- وابسته
- الگوریتم
- الگوریتم
- معرفی
- تقریبا
- در امتداد
- قبلا
- همچنین
- هر چند
- همیشه
- an
- تجزیه و تحلیل
- تحلیل
- تحلیل
- و
- دیگر
- پاسخ
- هر
- برنامه های کاربردی
- روش
- هستند
- مناطق
- دور و بر
- صف
- AS
- At
- هجوم بردن
- نویسندگان
- خیابان
- دور
- اساسی
- اساسا
- BE
- زیبایی
- زیرا
- بوده
- بودن
- در زیر
- برکلی
- بهترین
- بهتر
- بزرگ
- بزرگترین
- مسدود کردن
- بلاک ها
- تقویت شده
- کران
- شکستن
- دستیابی به موفقیت
- به ارمغان می آورد
- ساختن
- می سازد
- دسته
- اما
- by
- محاسبه
- کالیفرنیا
- نام
- آمد
- CAN
- نمی توان
- مورد
- کشتی
- معین
- تغییر دادن
- تغییر
- انتخاب
- نزدیک
- نزدیک
- نویسنده مشترک
- مشارکت کنندگان
- ستون ها
- ترکیب
- بیا
- می آید
- مشترک
- مقایسه
- تکمیل شده
- بغرنج
- اجزاء
- محاسبه
- محاسباتی
- قدرت محاسباتی
- کامپیوتر
- علم کامپیوتر
- مفهوم
- کنفرانس
- ساختن
- ادامه دادن
- ادامه داد:
- میتوانست
- با احتساب
- همراه
- جاری
- روز
- دهه
- دهه
- تلقی می شود
- عمیق
- خواستار
- نشان
- طرح
- مشخص
- توسعه
- مختلف
- مشکل
- نمایش
- دسترس
- do
- دان
- پایین
- هر
- در اوایل
- بهره وری
- موثر
- تلاش
- عنصر
- عناصر
- حذف شد
- را قادر می سازد
- پایان
- کافی
- برابر
- ایجاد
- حتی
- در نهایت
- تا کنون
- هر
- هر روز
- هر کس
- در حال بررسی
- مهیج
- وجود
- سوء استفاده قرار گیرد
- خیلی
- واقعیت
- منصفانه
- بسیار
- FAST
- سریعتر
- ویژه
- کمتر
- نهایی
- سرانجام
- پیدا می کند
- نام خانوادگی
- مناسب
- برای
- به جلو
- یافت
- مبانی
- چهار
- فرانسوی
- از جانب
- کاملا
- اساسی
- بیشتر
- عایدات
- تعمیم یافته
- عموما
- دریافت کنید
- غول
- Go
- هدف
- رفته
- خوب
- گوگل
- گراف
- گرافیک
- بیشتر
- رشد می کند
- بود
- اداره
- سخت
- دانشگاه هاروارد
- دانشگاه هاروارد
- آیا
- he
- از این رو
- پنهان
- چگونه
- اما
- HTTP
- HTTPS
- انسان
- اندیشه
- دلخواه
- IEEE
- مهم
- بهبود
- بهبود یافته
- بهبود
- ارتقاء
- in
- در دیگر
- ادغام شده
- در واقع
- موسسه
- مورد نظر
- علاقه مند
- تقاطع
- به
- معرفی
- شامل
- IT
- ITS
- خود
- ژانویه
- تنها
- نگاه داشتن
- کلید
- کشتن
- کشتن
- نوع
- برچسب
- بزرگ
- بزرگتر
- لیزر
- نام
- بعد
- رهبری
- منجر می شود
- یادگیری
- کمترین
- ترک
- رهبری
- کمتر
- نهفته است
- پسندیدن
- محدودیت
- خطوط
- طولانی
- نگاه کنيد
- خاموش
- پایین آوردن
- پایین ترین
- دستگاه
- فراگیری ماشین
- مجله
- عمدتا
- عمده
- ساخت
- کتابچه راهنمای
- بسیاری
- ماساچوست
- موسسه تکنولوژی ماساچوست
- ریاضیات
- ماتریس
- ممکن است..
- me
- به معنی
- روش
- قدرت
- حد اقل
- MIT
- فروتن
- اصلاح شده
- پول
- بیش
- اکثر
- بسیار
- ضرب
- ضرب
- ضرب شدن
- تقریبا
- نیاز
- ضروری
- شبکه
- هرگز
- جدید
- بعد
- نوامبر
- اکنون
- عدد
- تعداد
- گرفتن
- of
- on
- ONE
- آنهایی که
- فقط
- عمل
- or
- سفارش
- اصلی
- دیگر
- خارج
- روی
- به طور کلی
- همپوشانی
- مقاله
- اوراق
- برترین
- بخش
- مردم
- کاملا
- فیلیپ
- قطعات
- افلاطون
- هوش داده افلاطون
- PlatoData
- بازی
- نقطه
- ممکن
- پتانسیل
- قدرت
- عملی
- سلف، اسبق، جد
- ارائه شده
- زیبا
- خیلی ساده
- قبلی
- قبلا
- مشکل
- مشکلات
- روش
- روند
- محصول
- پیشرفت
- نسبت
- اثبات كردن
- منتشر شده
- مجله کوانتاما
- تصادفی
- تصادفی
- دارای رتبه
- منطق
- واقعا
- اخیر
- دستور العمل
- رکورد
- كاهش دادن
- کاهش
- مراجعه
- پالوده
- نسبتا
- تکیه بر
- برداشتن
- نیاز
- محققان
- نتیجه
- نتایج
- نشان داد
- فاش می کند
- خلاص شدن از شر
- راست
- ROW
- قوانین
- دویدن
- سعید
- همان
- نگهداری می شود
- پس انداز
- گفتن
- علم
- دانشمند
- دانشمندان
- دوم
- دیدن
- به نظر می رسد
- مشاهده گردید
- انتخاب
- جداگانه
- خدمت
- تنظیم
- محیط
- هفت
- باید
- نشان
- نشان داد
- سیام
- قابل توجه
- به طور قابل توجهی
- ساده
- ساده شده
- ساده کردن
- پس از
- تنها
- کوچک
- کوچکتر
- So
- تا حالا
- حل کردن
- برخی از
- گاهی
- تاحدی
- منبع
- سرعت
- مراحل
- استاندارد
- شروع
- ساقه
- گام
- مراحل
- هنوز
- استراتژی
- دانشجویان
- متعاقب
- قابل ملاحظه ای
- موفقیت
- تعجب
- صورت گرفته
- طول می کشد
- کار
- وظایف
- تیم
- فنی
- تکنیک
- تکنیک
- پیشرفته
- می گوید
- قوانین و مقررات
- نسبت به
- که
- La
- شان
- آنها
- سپس
- نظری
- نظریه
- آنجا.
- اینها
- آنها
- فکر می کنم
- تفکر
- این
- کسانی که
- اگر چه؟
- سه
- بدین ترتیب
- زمان
- به
- با هم
- هم
- ابزار
- جمع
- کاملا
- سنتی
- Tsinghua دانشگاه
- دور زدن
- دو برابر
- دو
- به طور معمول
- در نهایت
- فهمیدن
- درک
- غیر منتظره
- دانشگاه
- دانشگاه کالیفرنیا
- ناشناخته
- استفاده نشده
- تا
- بر
- استفاده کنید
- استفاده
- مفید
- معمولا
- ارزش
- تنوع
- مختلف
- بسیار
- عملا
- می خواهم
- بود
- ضایعات
- مسیر..
- راه
- we
- وب سایت
- خوب
- چی
- چه زمانی
- چه
- که
- در حین
- WHO
- اراده
- ویلیامز
- با
- در داخل
- بدون
- مهاجرت کاری
- با این نسخهها کار
- شایسته
- خواهد بود
- نوشتن
- wu
- سال
- سال
- هنوز
- بازده
- شما
- زفیرنت
- صفر