چارچوبی برای حل معادلات دیفرانسیل جزئی سهموی

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

در زیر کاپوت، مسائل ریاضی به نام معادلات دیفرانسیل جزئی (PDEs) این فرآیندهای طبیعی را مدل می کنند. در میان بسیاری از PDE های مورد استفاده در فیزیک و گرافیک کامپیوتری، کلاسی به نام PDE های سهموی مرتبه دوم توضیح می دهد که چگونه پدیده ها می توانند در طول زمان صاف شوند. معروف ترین مثال در این کلاس معادله گرما است که روش انتشار گرما در طول یک سطح یا در یک حجم را در طول زمان پیش بینی می کند.

محققان در زمینه پردازش هندسه الگوریتم های متعددی را برای حل این مسائل طراحی کرده اند روی سطوح منحنی، اما روش های آنها اغلب فقط برای مسائل خطی یا برای یک PDE منفرد اعمال می شود. یک رویکرد کلی‌تر توسط محققان آزمایشگاه علوم کامپیوتر و هوش مصنوعی MIT (CSAIL) به یک کلاس کلی از این مسائل غیرخطی بالقوه می‌پردازد.

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

Leticia Mattos Da Silva SM ’23، یک دانشجوی دکترای MIT در رشته مهندسی برق و علوم کامپیوتر، می گوید: «ما یک دستور العمل ارائه می دهیم: اگر می خواهید یک PDE سهموی مرتبه دوم را به صورت عددی حل کنید، می توانید مجموعه ای از سه مرحله را دنبال کنید. (EECS) و وابسته به CSAIL. برای هر یک از مراحل این رویکرد، شما با استفاده از ابزارهای ساده‌تر از پردازش هندسه، یک مسئله ساده‌تر را حل می‌کنید، اما در پایان، راه‌حلی برای چالش‌برانگیزتر PDE سهموی مرتبه دوم دریافت می‌کنید.

برای انجام این کار، داسیلوا و همکارانش از تقسیم Strang استفاده کردند، تکنیکی که به محققان پردازش هندسه اجازه می‌دهد تا PDE را به مسائلی تقسیم کنند که می‌دانند چگونه آنها را به طور موثر حل کنند.

اول، الگوریتم آنها با حل معادله گرما (که “معادله انتشار” نیز نامیده می شود) یک راه حل را در زمان به جلو پیش می برد، که روش پخش گرمای یک منبع روی یک شکل را مدل می کند. تصویر استفاده از یک مشعل دمنده برای گرم کردن یک صفحه فلزی – این معادله توضیح می دهد که چگونه گرما از آن نقطه روی آن پخش می شود. این مرحله را می توان به راحتی با جبر خطی تکمیل کرد.

حال تصور کنید که PDE سهموی دارای رفتارهای غیرخطی اضافی است که با گسترش گرما توصیف نمی شوند. اینجاست که مرحله دوم الگوریتم وارد می‌شود: با حل یک معادله همیلتون-ژاکوبی (HJ)، یک PDE غیرخطی مرتبه اول، قطعه غیرخطی را محاسبه می‌کند.

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

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

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

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

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

ماتوس داسیلوا و سولومون این مقاله را با اودد استاین، استادیار دانشکده مهندسی ویتربی دانشگاه کالیفرنیای جنوبی نوشتند. کار آنها تا حدی توسط کمک هزینه تحصیلی کالج محاسباتی MIT شوارتزمن که توسط گوگل، کمک هزینه تحصیلی MathWorks، بنیاد ملی علوم سوئیس، دفتر تحقیقات ارتش ایالات متحده، دفتر تحقیقات علمی نیروی هوایی ایالات متحده، بنیاد ملی علوم ایالات متحده تامین شده بود، پشتیبانی شد. ، آزمایشگاه هوش مصنوعی MIT-IBM Watson، مرکز تحقیقات مشترک Toyota-CSAIL، Adobe Systems و Google Research.