الگوریتم جدید، محدودیت سرعت را برای حل معادلات خطی درهم می‌شکند

منتشر‌شده در: quantamagazine به تاریخ ۸ مارس ۲۰۲۱
لینک منبع: New Algorithm Breaks Speed Limit for Solving Linear Equations

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

مارک گیسبرشت از دانشگاه واترلو گفت: «این یکی از اساسی‌ترین مشکلات در محاسبات است.» «اکنون ما مدرکی داریم که نشان می‌دهد می‌توانیم سریع‌تر حرکت کنیم.» این روش جدید، توسط ریچارد پنگ و سانتش واپالا از موسسه فن‌آوری جورجیا، در ماه جولای به صورت آنلاین منتشر شد و در ماه ژانویه در سمپوزیوم ACM-SIAM سالانه بر روی الگوریتم‌های گسسته ارائه شد که جایزه بهترین مقاله را برد.

سیستم‌های خطی شامل دو یا چند معادله با متغیرهایی هستند که روش‌های مختلف ارتباط اشیا با یکدیگر را مشخص می‌کنند. آن‌ها «خطی» هستند زیرا تنها توان مجاز دقیقا ۱ است و نمودارهای جواب معادلات صفحات را تشکیل می‌دهند.

یک مثال معمول از یک سیستم خطی-که احتمالا برای دانش‌آموزان ریاضی نیز آشنا است - شامل یک محوطه پر از مرغ و خوک است. اگر بدانید که ۱۰سر و ۳۰ پا وجود دارد، چند جوجه و چند خوک وجود دارد؟ همانطور که دانشجویان جبر یاد می‌گیرند، یک روند مشخص برای فهمیدن آن وجود دارد: دو معادله جبری بنویسید و آن‌ها را با هم حل کنید.

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

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

پنگ گفت: «شما می‌توانید راه خود را برای یافتن راه‌حل حدس بزنید.» و هیچ معلمی به خاطر آن از دست شما عصبانی نمی شود.

ممکن است به مطالعه مقاله ۳ نکته که بر کیفیت اطلاعات شما در تحقیقات عددی تاثیر می‌گذارند. علاقمند باشید.

قسمت ریاضی

برای اینکه به سیستم‌های خطی و نحوه حل آن‌ها پی ببرید، به حیاط برگردید، اما تصور کنید که حالا بیشتر یک باغ وحش است: مرغ، ۱-کرگدن شاخ‌دار و ۲-بره‌ شاخ‌دار. شما یک شمارش سریع انجام می‌دهید و مشخص می‌کنید که ۱۲ سر، ۳۸ پا و ۱۰شاخ وجود دارد. آیا می‌توانید تعداد هر حیوان را بیابید؟

برای ادامه، یک متغیر را به هر حیوان اختصاص دهید (c برای مرغ‌ها، r برای کرگدن‌ها، g برای بزها) و برای هر صفت یک معادله بنویسید. اعداد یا ضرایب در مقابل هر متغیر نشان‌دهنده مقدار آن ویژگی است که هر حیوان در اختیار دارد.

c + r + g = ۱۲ سر

۲c + ۴r + ۴g = ۳۸ پا

۰c + ۱r + ۲g = ۱۰ شیپور

حالا شما سه معادله و سه مجهول دارید.

یک راه برای حل آن‌ها دستکاری یک معادله و تعریف یک متغیر بر حسب دو معادله دیگر است. برای مثال ۰ c + ۱ r + ۲ g = ۱۰ به r = ۱۰-۲ g تبدیل می‌شود. این مقدار را برای r در دو معادله دیگر جایگزین کنید و به همین صورت ادامه دهید تا زمانی که تمام متغیرها را تنها برحسب یک متغیر تعریف کنید، که سپس می‌توانید آن را به طور دقیق حل کنید. سپس می‌توانید این فرآیند را تکرار کنید، و از متغیری که برای حل آن را حل کرده‌اید استفاده کنید تا متغیر بعدی را حل کنید.

اما روش پیچیده‌تر دیگر، ایجاد ماتریسی است که ورودی‌های آن ضرایب معادلات هستند. سه معادله به این ماتریس تبدیل می‌شوند.

سپس تعداد نامعلوم جوجه‌ها، کرگدن‌ها و بزها را با یک ماتریس دیگر نشان می‌دهیم.

در نهایت، ما تعداد مشاهده‌شده سرها، پاها و شاخ‌ها را با یک ماتریس سوم نشان می‌دهیم.

ما می‌توانیم این سه ماتریس را در یک سیستم خطی واحد ترکیب کنیم، که در آن ماتریس اول ضرب شده در مقادیر نامشخص ماتریس دوم برابر با ماتریس سوم است-که در آن نقطه ما می‌توانیم از جبر خطی برای حل ماتریس دوم استفاده کنیم.

چه معادلات را دستکاری کنید و چه مسیر ماتریس را انتخاب کنید، در نهایت همان تعداد مراحل محاسباتی را برای حل مساله انجام خواهید داد. این عدد مکعب تعداد متغیرها در سیستم است (n ۳). در این مورد ما سه متغیر داریم، بنابراین 3۳ یا ۲۷ مرحله محاسباتی طول می‌کشد. اگر ما چهار حیوان و چهار معادله داشتیم، ۴ به توان ۳ یا ۶۴ مرحله برای حل آن‌ها طول می‌کشید.

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

در سال ۱۹۶۹، Volker Strassen الگوریتمی را برای اجرای ضرب ماتریس‌ها تنها در nبه توان ۲.۸۱ مرحله ابداع کرد. از آن زمان به بعد، ریاضی‌دانان و دانشمندان کامپیوتر برای کاهش بیشتر توان، تلاش کردند. آخرین پیشرفت که اکتبر گذشته توسط ویرجینیا واسیلوسکا ویلیامز از موسسه تکنولوژی ماساچوست و جاش آلمن محقق فوق‌دکترا در دانشگاه هاروارد انجام شد، اثبات کرد که امکان انجام ضرب ماتریس در nبه توان ۲.۳۷۲۸۶ گام وجود دارد، که بهبود در نمای ۰.۰۰۰۰۱نسبت به بهترین علامت قبلی است.

نتیجه همه این‌ها این است که هر سیستم خطی که می‌خواهید حل شود را می‌توان به یک سوال در مورد ضرب ماتریس کاهش داد، و در حال حاضر، ضرب ماتریس را حداقل می‌توان به صورت نظری در n ۲.۳۷۲۸۶ مرحله اجرا کرد. اما ویژگی‌های فنی مختلف نشان می‌دهند که باید حل سیستم‌های خطی سریع‌تر از این-درn ۲ مرحله امکان پذیر باشد. ما از ضرب ماتریس‌ها استفاده می‌کنیم، چون بهترین ابزار موجود بوده‌است، اما این بدین معنی نیست که ابزار بهتری برای کشف شدن وجود ندارد.

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

مطالعه مقاله برنامه راهنما برای یادگیری علوم داده در ۲۰۲۱ توصیه می‌شود.

راه‌حل‌های حدس‌زنی

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

این «رویکرد تکراری» رویکردی است که مهندسان و دانشمندان اغلب از آن استفاده می‌کنند. این روش برای بسیاری از مسائل عملی خوب جواب می‌دهد، چون معمولا متخصصان کورکورانه حدس نمی‌زنند، که تعداد حدس‌های تکراری لازم برای رسیدن به راه‌حل را کاهش می‌دهد. پنگ گفت: «برای مشکلات محاسبات علمی در دنیای واقعی، انسان‌ها شهود بسیار خوبی برای آنچه که پاسخ‌ها باید باشند دارند.»

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

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

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

تصادفی بودن هماهنگی

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

جیزبرشت گفت: «این توازن جایی است که جادو اتفاق می‌افتد.» ممکن است واضح به نظر برسد که به کار بردن چند حدس در یک زمان مفید است، اما کار استراتژی چندان ساده نیست. اثربخشی الگوریتم جدید تا حد زیادی به هوشمند بودن در مورد چگونگی ایجاد حدس‌های اولیه که فرآیند تکرار‌شونده را به وجود می‌آورند و یافتن روش‌های هوشمندانه برای ترکیب نتایج حدس‌های موازی در یک پاسخ نهایی واحد بستگی دارد.

برای بازگشت به مثال انبار، این الگوریتم ممکن است سه حدس اولیه بزند، که در آن هر حدس یک ماتریس ۳ در ۱ است که تعدادی مرغ، کرگدن‌ها و بزها را مشخص می‌کند. الگوریتم مشاهده می‌کند که هر حدس چقدر دور است، سپس حدس‌های بیشتری می‌زند و به حدس زدن رشته‌های موازی ادامه می‌دهد.

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

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

واپالا گفت: «تصادفی بودن هماهنگ‌شده‌ای وجود دارد.» این بدان معنی است که حدس‌های تصادفی نه تنها مقادیر دقیق حدس‌ها را در نظر می‌گیرند بلکه تمام حدس‌های بالقوه بین آن‌ها را نیز پوشش می‌دهند. از نظر روحی شبیه به این است که چطور دو نفر که در جنگل می‌گردند، تنها زمینی را که در آن راه می‌روند جستجو نمی‌کنند؛ بلکه تمام خطوط دید بین آن‌ها را نیز پوشش می‌دهند.

واپالا گفت: «هر چیزی بین دو حدس نیز پوشش داده می‌شود.» این ویژگی جستجو تضمین می‌کند که الگوریتم در جایی با راه‌حل مواجه خواهد شد. اما به خودی خود راه‌حل را مشخص نمی‌کند. برای انجام این کار-در واقع قرار دادن دستان‌شان بر روی راه‌حل-پنگ و واپالا باید چیز دیگری را اثبات کنند.

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

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

در نتیجه، الگوریتم Peng و Vemala می‌تواند راه‌حل درون ماتریس را سریع‌تر از آنچه که می‌تواند در ماتریسی با همان تعداد ورودی پیدا کند، اما هیچ یک از تقارن‌های مفید وجود ندارد. تقارن‌های ماتریس نیز یک مزیت مهم دیگر را منتقل می‌کنند: آن‌ها کمک می‌کنند تا اطمینان حاصل شود که حدس‌ها هرگز آنقدر بزرگ نمی‌شوند که از دیدگاه کارایی الگوریتمی ضعیف شوند.

پنگ گفت: «ما مجبور بودیم کنترل کنیم که یک عدد چقدر بزرگ ظاهر می‌شود چرا که ما این کار را با حدس زدن و هماهنگی انجام می‌دهیم.» پنگ و استامالا اثبات کردند که الگوریتم آن‌ها می‌تواند هر سیستم خطی پراکنده را در n به توان ۲.۳۳۲ مرحله حل کند. این امر نمای بهترین الگوریتم برای ضرب ماتریس (n ۲.۳۷۲۸۶) را با حدود چهار صدم برابر می‌کند. پر کردن ضرب ماتریس‌ها به این زودی‌ها برای کاربردهای عملی مهم نخواهد بود، اما به عنوان اثبات مفهوم، این بهبود جزئی یک شکاف است: نشان می‌دهد که یک راه کاملا بهتر برای حل سیستم‌های خطی وجود دارد.

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

این متن با استفاده از ربات مترجم مقاله ریاضیات ترجمه شده و به صورت محدود مورد بازبینی انسانی قرار گرفته است.در نتیجه می‌تواند دارای برخی اشکالات ترجمه باشد.

مقالات لینک‌شده در این متن می‌توانند به صورت رایگان با استفاده از مقاله‌خوان ترجمیار به فارسی مطالعه شوند.