انواع مختلف حلکنندههای چندشبکه – حلکنندههای چندشبکهای هندسی (GMG) و حلکنندههای چندشبکهای جبری (AMG)- در این بخش و همچنین الگوریتم چندشبکهای مورد بحث قرار میگیرند.
حل کننده هندسی چندشبکه ای/پیش شرطی
حلگر هندسی چندشبکه ای از سلسله مراتبی از سطوح چندشبکه ای استفاده می کندکه در آن هر سطح مربوط به یک مش و انتخابی از توابع شکل است. سپس می تواند همگرایی حل کننده تکراری را با حل مسئله المان محدود بر روی یک سری مش به جای یک شبکه واحد تسریع کند. الگوریتم چندشبکه هندسی با یک مش اولیه کنترل شده توسط فیزیک یا مش تعریف شده توسط کاربر شروع می شود و سپس یک سری مش های درشت تر می سازد. هر مش اضافی تقریباً دو برابر درشت تر از مش قبلی است. تعداد کل مش ها به اندازه مدل بستگی دارد: مش های هندسی چندشبکه ای به طور خودکار توسط حل کننده ساخته می شوند تا زمانی که درشت ترین مش به تعداد درجه آزادی به اندازه کافی پایین منجر شود که با یک حل کننده مستقیم قابل حل باشد. علاوه بر درشت کردن مش، می توان با کاهش ترتیب توابع شکل، یک سطح “درشت تر” جدید ساخت. وقتی به سطح چندشبکه درشت تر می روید، تعداد درجات آزادی کاهش می یابد. مش ها برای سطوح مختلف می توانند به صورت دستی یا خودکار ساخته شوند. گزینههای خودکار از یک الگوریتم درشتکننده برای مش ریز استفاده میکنند که منجر به مشهایی میشود که با یکدیگر تراز نیستند. همچنین گزینهای برای تولید مشهای ظریفتر از درشتترین مش با اصلاحهای متوالی مش وجود دارد که منجر به مشهای تراز (تودرتو) میشود. گزینه دستی زمانی می تواند مفید باشد که مش چهار ضلعی، شش وجهی یا منشوری دارید یا به دلایل دیگری می خواهید جزئیات را در مش ها کنترل کنید. همچنین گزینهای برای تولید مشهای ظریفتر از درشتترین مش با اصلاحهای متوالی مش وجود دارد که منجر به مشهای تراز (تودرتو) میشود. گزینه دستی زمانی می تواند مفید باشد که مش چهار ضلعی، شش وجهی یا منشوری دارید یا به دلایل دیگری می خواهید جزئیات را در مش ها کنترل کنید. همچنین گزینهای برای تولید مشهای ظریفتر از درشتترین مش با اصلاحهای متوالی مش وجود دارد که منجر به مشهای تراز (تودرتو) میشود. گزینه دستی زمانی می تواند مفید باشد که مش چهار ضلعی، شش وجهی یا منشوری دارید یا به دلایل دیگری می خواهید جزئیات را در مش ها کنترل کنید.
حلگر هندسی چندشبکه ای (GMG) یا پیش شرط یک روش تکراری سریع و کارآمد برای مدل های بیضوی و سهمی است. یک یا چند چرخه از روش چندشبکه هندسی را انجام می دهد. الگوریتم چندشبکه ای کلاسیک از یک یا چند مش کمکی استفاده می کند که درشت تر از مش اصلی (ریز) هستند. ایده این است که فقط کسری از محاسبات را روی مش ریز انجام دهیم. در عوض، محاسبات را در صورت امکان روی مش های درشت تر انجام می دهد که منجر به عملیات کمتر می شود. اندازه حافظه اضافی مورد استفاده برای مش های درشت تر و ماتریس های مرتبط با اندازه داده های اصلی قابل مقایسه است. این منجر به یک الگوریتم تکراری می شود که هم سریع و هم کارآمد در حافظه است. رجوع کنید به رفر. 23 برای اطلاعات بیشتر
حل کننده هندسی چندشبکه ای با چندین مش
اگر میخواهید از حلکننده هندسی چندشبکهای با چندین مش استفاده کنید، باید قبل از تنظیم تنظیمات حلکننده، دنبالههای مشبندی اضافه شوند. برای مثال، زمانی که حل کننده چندشبکه ای از کار می افتد، می تواند مفید باشد. سپس، به جای اینکه به مششر اجازه دهید به طور خودکار مش های درشت تری را از مش اولیه بسازد، می توانید مش های شکست خورده را به صورت دستی با استفاده از توالی های مش بندی تعریف شده توسط کاربر بسازید و این مش ها را در تنظیمات حل گره Multigrid انتخاب کنید . تعداد مش ها با مقدار موجود در قسمت Number of multigrid level تعیین می شود . اگر حلکننده پیام مشکل تنظیم چندشبکه را برگرداند ، سپس برای تجسم مشهای چندشبکهای و دیدن تعداد زیادی از آنها شکست خورده، نگه داشتن سطوح چندشبکهای تولید شده را انتخاب کنید.در تنظیمات گره Multigrid را علامت بزنید . پس از محاسبه مجدد، سطح چندشبکه به عنوان زیرگرههای سطح چندشبکه تحت یک گره مرحله مطالعه ثابت اضافه میشود، برای مثال (اگر در کادر محاورهای Show More Options تیک سطح Multigrid را انتخاب کرده باشید ). مش های درشت تر مربوطه در Model Builder به عنوان گره های مش اضافی ظاهر می شوند . احتمالاً درشت ترین مش از کار می افتد زیرا آنقدر درشت است که نمی تواند هندسه را گسسته کند.
شکل 20-10: مثال شکست مش. سمت چپ: سطوح در هر طرف لایه نازک یکدیگر را قطع می کنند که منجر به خطاهای مش بندی می شود. مش از عناصر چهار وجهی تشکیل شده است. راست: تلاقی این سطوح در هنگام استفاده از مش جاروب شده (ساختار یافته) برای لایه نازک به جای عناصر چهار وجهی پیش فرض رخ نمی دهد.
برای تصحیح مش درشت خراب، یکی از مراحل زیر را امتحان کنید:
•
|
دنباله مش بندی برای مش خراب را به صورت دستی با استفاده از یک مش ریزتر یا یک مش جارو شده بسازید.
|
•
|
یک مش درشت جدید اضافه کنید و تنظیمات را در گره Multigrid Level مربوطه تغییر دهید تا به مش جدید اشاره کنید.
|
•
|
درشت ترین مش و گره مربوط به سطح چندشبکه را حذف کنید تا تعداد سطوح چندشبکه ای کاهش یابد.
|
روش دیگر ساخت دستی تمام سطوح چندشبکه ای است. برای انجام این کار، مش ها را با استفاده از دنباله های مش بندی تعریف شده توسط کاربر بسازید. برای اطلاعات بیشتر در مورد افزودن مش به گره مش مراجعه کنید . هر توری بعدی باید تقریباً دو برابر درشتتر از مش قبلی باشد. مش اولیه را در مرحله مطالعه ثابت به عنوان مش 1 تنظیم کنید ، به عنوان مثال، مش های اضافی را به عنوان زیرگره های سطح چندشبکه در گره مرحله مطالعه تنظیم کنید، مش های درشت تر را به هر سطح چندشبکه ای اختصاص دهید. همچنین در تنظیمات حل کننده گره Multigrid ، از لیست روش تولید سلسله مراتب، Manual را انتخاب کنید .
حلکنندههای چندشبکهای جبری/پیششرطیکنندهها
حلکنندهها یا پیششرطیکنندههای چندشبکه جبری (AMG) یک یا چند چرخه از روش چندشبکهای جبری را انجام میدهند. این شبیه به الگوریتم چندشبکهای هندسی است، تفاوت آن در این است که سطوح چندشبکهای را مستقیماً از ماتریس سیستم A 0 در بهترین سطح میسازد . یعنی امتدادهای P i را از A 0 بدون استفاده از مش های کمکی می سازد. ماتریس های سطح درشت A i را از A 0 می سازدبا روش طرح ریزی گالرکین مزیت این است که نیازی نیست در مورد سطوح درشت چندشبکه ای زحمت بکشید. حلکننده AMG شامل یک روش درشتسازی موازی است که میتواند مصرف حافظه و زمان محاسبه در هر تکرار را کاهش دهد.
الگوریتم چندشبکه ای
برای توصیف الگوریتم چندشبکه ای، فرض کنید که N + 1 سطح چندشبکه ای دارید که از 0 تا N شماره گذاری شده اند ، جایی که 0 بهترین سطح است (سطحی که به دنبال راه حل برای آن هستید). برای حل سیستم خطی A 0 x = b (مرتبط با سطح 0 )، الگوریتم باید ماتریس های سیستم A 1 ، …، A N را برای سطوح چندشبکه درشت اصلاح کند. همچنین باید ماتریس های افزایشی P i را محاسبه کند که یک راه حل x بردار را در سطح i ترسیم می کندبه بردار محلول مربوطه P i x در سطح ریزتر بعدی i − 1 .
ماتریس های افزایش با استفاده از درون یابی ساده از یک سطح چندشبکه ای به سطح دیگر ساخته می شوند. ماتریس های سیستم برای سطوح درشت را می توان به دو روش ساخت:
•
|
با مونتاژ A i روی مش سطح i (روش پیش فرض).
|
•
|
با طرح ریزی از سطح ریزتر: A i = P i T A i – 1 P i . به این روش گالرکین نیز گفته می شود. معمولاً به عناصر غیر صفر بیشتری در ماتریس سیستم A i منجر می شود ، اما همگرایی می تواند سریعتر از روش پیش فرض باشد.
|
الگوریتم زیر یک چرخه چندشبکه ای را توصیف می کند:
1
|
ورودی الگوریتم مقداری حدس اولیه x 0 برای حل سیستم A 0 x = b است .
|
2
|
با شروع با x 0 , چند تکرار از یک پیش موتر را روی سیستم خطی A 0 x = b اعمال کنید و تکرار x 0s دقیق تری را به دست آورید . معمولاً presmoother یک الگوریتم تکراری ساده مانند SOR است، اما شما همچنین می توانید هر حل کننده تکراری را انتخاب کنید.
|
3
|
باقیمانده r 0 = b – A 0 x 0s را محاسبه کنید . پیش صاف کننده باقیمانده را “صاف” می کند، بنابراین نوسانات در r آنقدر طول موج دارند که در سطح درشت تر بعدی به خوبی حل می شوند (1). بنابراین، با اعمال جابجایی طولانی شدن، باقیمانده را روی سطح 1 قرار دهید : r 1 = P 1 Tr 0 .
|
4
|
اگر N = 1 از حلگر درشت برای حل سیستم A 1 x 1 = r 1 استفاده کنید . حل کننده درشت معمولاً یک حل کننده مستقیم مانند MUMPS است. تعداد درجات آزادی در سطح 1 کمتر از سطح 0 است، به این معنی که حل A 1 x 1 = r 1 هزینه کمتری دارد. اگر به جای N > 1 ، سیستم A 1 x 1 = r 1 (تقریبا) را با اعمال بازگشتی یک چرخه از الگوریتم چندشبکه برای سطوح 1 حل کنید., 2 , …, N . در هر دو مورد، راه حل بدست آمده x 1 را تصحیح شبکه درشت می نامند .
|
5
|
تصحیح شبکه درشت را با استفاده از ماتریس افزایش به سطح 0 ترسیم کنید: x 0c = x 0s + P 1 x 1 .
|
6
|
با شروع با x 0c , چند تکرار از یک postsmoother را روی سیستم خطی A 0 x = b اعمال کنید و تکرار دقیق تری x 0mg را به دست آورید . postsmoother پیش فرض SORU است (نسخه SOR با استفاده از مثلث بالایی ماتریس). تکرار x 0mg خروجی چرخه چندشبکه ای است.
|
چرخه ای که توضیح داده شد، چرخه V نامیده می شود. فراخوانی بازگشتی در مرحله 4 (زمانی که N > 1 ) نیز یک چرخه V است. برای چرخه W و چرخه F، مراحل 1 تا 6 در بالا یکسان است، اما با این پیچش که فراخوانی بازگشتی در مرحله 4 با دو تماس چندشبکه ای برای سطوح درشت تر جایگزین می شود. برای چرخه W، این دو تماس، تماسهای بازگشتی هستند (تماسهای چرخه W). برای چرخه F اولین فراخوانی یک چرخه W و دومی یک چرخه V است.
فقط برای دو سطح چندشبکه ای ( N = 1 ) این چرخه ها یکسان هستند زیرا الگوریتم از حلگر درشت مرحله 4 استفاده می کند. همچنین میزان کار در بهترین سطح برای چرخه های مختلف یکسان است. به طور معمول چرخه V کافی است، اما چرخه W و چرخه F می توانند برای مسائل دشوارتر مفید باشند.
هنگام استفاده از چندشبکه به عنوان پیش شرط، عملکرد این پیش شرطی با اعمال تعداد ثابتی از چرخه های چندشبکه ای به دست می آید. هنگام استفاده از چندشبکه به عنوان حل کننده، چرخه چندشبکه تا زمانی که به همگرایی برسد تکرار می شود.
هنگام استفاده از چندشبکه به عنوان پیش شرطی برای روش گرادیان مزدوج برای یک ماتریس متقارن A ، ماتریس پیش شرطی M نیز باید متقارن باشد. اگر ماتریسهای M مرتبط با پیشصوتکننده و پسموتر جابهجا شوند، این شرط برآورده میشود. به عنوان مثال، این مورد در صورتی است که پیش صافکننده SOR و پسموتر SORU باشد، و اگر از همان تعداد مراحل هموارسازی استفاده شود. این ترکیب با دو مرحله هموارسازی پیش فرض است.
نکاتی در مورد کارایی صاف کننده ها
COMSOL Multiphysics هموارسازی را در همه سطوح به جز درشتترین سطح چندشبکهای انجام میدهد. نرمکننده باید از نظر محاسباتی ارزان و در کاهش بخشی از خطا که دارای فرکانس فضایی بالایی در مشی است که روی آن اعمال میشود، موثر باشد. بنابراین، اعمال یک صاف کننده روی چندین مش با سلسله مراتبی از اندازه های مش، حل کننده کارآمدتری نسبت به زمانی که صاف کننده فقط بر روی بهترین مش اعمال می شد، منجر می شود.
کارایی روش چندشبکه ای با تکرارهای ساده به عنوان یک روش هموارتر (مانند تکرار Jacobi و SOR) به بیضوی بودن مسئله ریاضی اساسی بستگی دارد. برای مسائل هلمهولتز که از یک معادله منشا می گیرند
یا
مسئله خطی به دست آمده برای فرکانس های بزرگ ω نامشخص است . برای این مشکلات، اگر مش خیلی درشت باشد، یک تکرار ساده حالت های ویژه صاف را تقویت می کند و این روش ها را به عنوان صاف کننده ها نامناسب می کند. برای تعیین زمان استفاده از یک تکرار ساده، از معیار Nyquist استفاده کنید :
که می گوید مش باید حداقل دو عنصر مش در هر طول موج داشته باشد. بنابراین، هنگام استفاده از حلکننده هندسی چندشبکهای برای این نوع مسائل، اگر از تکرارهای ساده بهعنوان هموارتر استفاده میشود، اطمینان حاصل کنید که این معیار روی درشتترین مش انجام میشود. در شرایطی که این معیار روی مش های درشت برآورده نمی شود، GMRES می تواند صاف کننده مناسبی باشد ( مراجعه 26 ). با این حال، این تنظیم باعث میشود که نرمکنندهها در همه سطوح گرانتر شوند و ممکن است در مقایسه با انتخاب یک شبکه درشت که معیار Nyquist را برآورده میکند، همیشه جوابگو نباشد. همچنین توجه داشته باشید که یک نرمافزار مبتنی بر پیششرطیکننده Krylov مانند GMRES نیاز به حلکننده تکراری (بیرونی) دارد که روی FGMRES تنظیم شود.
اپراتور لاپلاس تغییر یافته پیچیده
همگرایی روش Multigrid را می توان با افزودن یک سهم لاپلاس جابجا شده پیچیده (CSL) بهبود بخشید – یعنی یک عبارت کاملاً پیچیده که اثر میرایی نوسانات در محلول را دارد. CSL معمولاً برای مشکلات موج در فرکانس بالا اعمال می شود. اثر آن به پیشتهویهکننده و نرخ همگرایی محدود میشود و میتوان آن را بهطور مستقل هم در سطوح ریز و هم در سطوح چندشبکه اعمال کرد. CSL ماتریس اصلی سیستم و راه حل نهایی را تغییر نمی دهد. سهم CSL تابعی از تعداد موج مسئله است و به طور کلی در ضریب آرامش O (1) ضرب می شود. انتخاب ضریب آرامش یک مبادله بین عدم میرایی (0) و میرایی زیاد است اما بدتر شدن عملکرد پیشتهویهکننده (مقادیر بزرگ).