לדלג לתוכן

פותר וקדם־התניה

הפותר הליניארי של FrontISTR בנוי כך שניתן לבחור שיטה ישירה או שיטה איטרטיבית, ובשיטה איטרטיבית לשלב קדם־התניה לפתרון מערכת המשוואות הליניארית. שיטת הטיפול ב־MPC וסילוק דרגות חופש של מגע הן בחירות עזר הקובעות באיזו צורה תטופל המערכת הליניארית הכוללת אילוצים רב־נקודתיים או אילוצי מגע.

סקירת הפונקציות

הפותר וקדם־ההתניה מורכבים מהאפשרויות הבאות. תחילה בוחרים בין שיטה איטרטיבית לשיטה ישירה; קדם־התניה משולבת רק כאשר נבחרה שיטה איטרטיבית.

קטגוריה אפשרויות עיקריות תפקיד
שיטות איטרטיביות CG, BiCGSTAB, GMRES, GPBiCG, GMRESR, GMRESREN פתרון חסכוני בזיכרון של מטריצות דלילות גדולות.
קדם־התניה לשיטות איטרטיביות SSOR, סקיילינג אלכסוני, BILU, AMG, SAINV, RIF משפרת את התכנסות השיטה האיטרטיבית; אינה משמשת בשיטה ישירה.
שיטות ישירות MUMPS, MKL פתרון רובוסטי של המשוואות הליניאריות באמצעות פירוק.
שיטת טיפול ב־MPC שיטת קנס, סילוק מפורש של דרגות חופש משקפת אילוצים רב־נקודתיים במערכת הליניארית.
סילוק דרגות חופש של מגע אוטומטי, פעיל תמיד מחליף את אופן הטיפול בדרגות החופש הנוספות של מגע SLAGRANGE.
פונקציות עזר אומדן מספר תנאי, פלט מטריצה, פלט יומן מסייעות בניפוי שגיאות, בדיקת התכנסות והערכת ביצועים.

בהרצה מקבילית ניתן לשלב מקביליות MPI באמצעות חלוקת תחום עם מקביליות תהליכונים של OpenMP. שיטות איטרטיביות הן הבחירה המקובלת לאנליזות מקביליות גדולות; שיטות ישירות משמשות בסביבה שבה הספרייה המתאימה מקושרת וכאשר נדרש פתרון רובוסטי יותר.

בחירת פותר וקדם־התניה

תחילה מחליטים אם להשתמש בשיטה איטרטיבית או ישירה, ואם נבחרה שיטה איטרטיבית בוחרים לאחר מכן קדם־התניה.

שיקול גישה מומלצת
גודל הבעיה בבעיות קטנות ובינוניות שיטה ישירה יציבה וקלה לשימוש. בבעיות גדולות שיטה איטרטיבית יעילה יותר בזיכרון.
סימטריית המטריצה לבעיה סימטרית וחיובית־מוגדרת, CG הוא מועמד מתאים. לבעיה לא־סימטרית יש לשקול BiCGSTAB, ‏GMRES, ‏GPBiCG וכדומה.
סביבת מקביליות במקביליות MPI משלבים שיטה איטרטיבית עם חלוקת תחום. בקדם־התניה תחת OpenMP, ‏SSOR התומך בריבוי צבעים הוא מועמד מתאים.
קדם־התניה (כאשר נבחרה שיטה איטרטיבית) מתחילים בדרך כלל ב־SSOR המוגדר כברירת מחדל, ולאחר מכן שוקלים AMG. ‏SSOR קל לחישוב כאשר ההתכנסות טובה; AMG מתאים לבעיות גדולות ומורכבות. AMG זמין כמימוש המבוסס על Trilinos-ML או כ־SA-AMG המובנה ב־HEC-MW; יש לבחור לפי תצורת הבנייה.
מגע ו־MPC באנליזה הכוללת מגע או אילוצים רב־נקודתיים, בחירת שיטת הטיפול ב־MPC וסילוק דרגות חופש של מגע עשויה להשפיע על ההתכנסות והרובוסטיות.
ספריות חיצוניות MUMPS, ‏MKL ו־AMG (Trilinos-ML) זמינים בבנייה שבה הספריות המתאימות מקושרות. AMG (SA-AMG) זמין בבנייה שבה LAPACK מופעל.

באנליזות סטנדרטיות, ערך מבחן ההתכנסות, מספר האיטרציות המרבי, מקדם התיקון האלכסוני של קדם־ההתניה וכדומה פועלים בדרך כלל היטב עם ערכי ברירת המחדל. רק כאשר ההתכנסות איטית או מתבדרת, יש לבחון לפי הסדר את השיטה האיטרטיבית, קדם־ההתניה, שיטת הטיפול ב־MPC וסילוק דרגות חופש של מגע. לערכי הפרמטרים ולפורמט שלהם ראו !SOLVER ברפרנס מילות המפתח.

שיטות איטרטיביות

שיטות איטרטיביות פותרות מטריצות דלילות גדולות על ידי עדכון חוזר של הפתרון באמצעות מכפלות מטריצה־וקטור וקדם־התניה. ב־FrontISTR ניתן לבחור בשיטות הבאות.

שיטה איטרטיבית התאמה עיקרית הערות
CG בעיה סימטרית וחיובית־מוגדרת מועמד סטנדרטי באנליזה מבנית ובהולכת חום.
BiCGSTAB בעיה לא־סימטרית מועמד כאשר קיימת אי־סימטריה חזקה עקב מגע או צימוד.
GMRES בעיה לא־סימטרית משמש עם גודל מרחב Krylov הניתן להגדרה.
GPBiCG בעיה לא־סימטרית גרסה משופרת ממשפחת BiCGSTAB.
GMRESR בעיה לא־סימטרית, שימוש מתקדם אפשרות המשתמשת ב־GMRES בצורה מקוננת.
GMRESREN בעיה לא־סימטרית, שימוש מתקדם גרסה רקורסיבית ממשפחת GMRESR.

CG מניח שהמטריצה סימטרית וחיובית־מוגדרת. כאשר אי־הסימטריה משמעותית עקב מגע עם חיכוך, טיפול לא־סימטרי באילוצים, צימוד וכדומה, יש לשקול BiCGSTAB, ‏GMRES, ‏GPBiCG וכדומה. ב־GMRES, הגדלת גודל מרחב Krylov יכולה לשפר את ההתכנסות, אך גם מגדילה את צריכת הזיכרון.

כאשר מציינים METHOD2, ניתן לעבור לשיטה איטרטיבית חלופית אם CG מתבדר או נכשל. פונקציה זו היא מנגנון גיבוי כאשר CG הוא הפותר הראשי, ושאר ערכי ההגדרה ושורות הנתונים זהים לאלה של הפותר הראשי.

CG, ‏BiCGSTAB, ‏GPBiCG ו־PipeCG מעדכנים את וקטור השארית באמצעות נוסחת נסיגה. ככל שהאיטרציות נמשכות, שגיאות עיגול מצטברות והשארית המתעדכנת רקורסיבית עלולה לסטות מן השארית האמיתית. כדי למנוע זאת, וקטור השארית מחושב מחדש במרווחי איטרציות קבועים מתוך אגף ימין ומכפלת מטריצה־וקטור. את המרווח ניתן להגדיר באמצעות RECOMPUTE_RESIDUAL. מרווח ארוך יותר מפחית את מספר מכפלות המטריצה־וקטור, אך מגדיל את הסיכון שהשארית המתעדכנת רקורסיבית תתרחק מן השארית האמיתית ופתרון שעדיין לא התכנס ייחשב כמתכנס. לעומת זאת, מרווח קצר מדי לא רק מגדיל את מספר מכפלות המטריצה־וקטור, אלא גם עלול לשבש את הקשר בין השארית לבין וקטורי העזר שנשמר על־ידי נוסחת הנסיגה, וכך לפגוע בהתכנסות עצמה. ערך ברירת המחדל של כל שיטה מאזן בין ההשפעות האלה; אם משנים אותו, יש לבדוק את היסטוריית ההתכנסות ואת השארית היחסית הסופית.

קדם־התניה

קדם־התניה היא טרנספורמציה של מטריצת המקדמים שנועדה לשפר את ההתכנסות של שיטה איטרטיבית, והיא מיושמת רק כאשר נבחרה שיטה איטרטיבית. בשיטה ישירה אין שימוש בקדם־התניה. גם עבור אותה שיטה איטרטיבית, בחירת קדם־ההתניה יכולה לשנות במידה רבה את מספר האיטרציות ואת זמן החישוב עד להתכנסות.

קדם־התניה מאפיינים התאמה עיקרית
SSOR קדם־התניה סטנדרטית; תומכת בסידור רב־צבעי. מועמד ראשון; נפוץ באנליזה מבנית.
סקיילינג אלכסוני קדם־התניה קלה המשתמשת ברכיבים האלכסוניים. כאשר רוצים להפחית עלות חישובית.
BILU פירוק LU לא מלא ברמת בלוקים. מועמד לבעיות שבהן SSOR מתקשה להתכנס.
AMG (Trilinos-ML) רב־רשת אלגברי המשתמש בספרייה החיצונית Trilinos-ML. מועמד לבעיות גדולות או לבעיות שבהן שולטים רכיבי שגיאה היררכיים.
AMG (SA-AMG) רב־רשת אלגברי מסוג Smoothed Aggregation המובנה ב־HEC-MW. כנ״ל; מועמד לשימוש ב־AMG ללא הוספת ספרייה חיצונית.
SAINV Sparse Approximate Inverse. אפשרות מיוחדת לבעיות מגע או לסביבה מבוזרת.
RIF Robust Incomplete Factorization. חלופה נוספת ממשפחת הפירוקים הלא־מלאים.

SSOR הוא הבחירה הסטנדרטית, ובמקביליות OpenMP משתמשים בגרסה עם סידור רב־צבעי. סקיילינג אלכסוני קל לחישוב, אך השפעתו על ההתכנסות תלויה בבעיה. BILU ממומש כפירוק LU לא מלא לפי בלוקים ותומך גם במטריצות עם מספר כללי של דרגות חופש. במשפחת BILU קיים מסלול שבו, לאחר התבדרות השיטה האיטרטיבית, מגדילים אוטומטית את מקדם התיקון האלכסוני SIGMA_DIAG ומנסים שוב; ציון הערך מפורט ברפרנס מילות המפתח.

ל־AMG (רב־רשת אלגברי) יש שני מימושים: מימוש המשתמש בספרייה החיצונית Trilinos-ML ו־SA-AMG המובנה ב־HEC-MW. אלה מימושים עצמאיים, ותצורות הבנייה הנדרשות והאפשרויות הזמינות בהם שונות.

AMG המבוסס על Trilinos-ML דורש ש־ML יהיה פעיל בעת הבנייה. ניתן לקבוע מחליק, מחזור רב־רשת, שיטת הגסה והגדרות נוספות; לערכים המפורטים ראו את רפרנס מילות המפתח.

SA-AMG היא שיטת קדם־התניה מסוג רב־רשת אלגברי בשיטת Smoothed Aggregation ואינה דורשת Trilinos-ML. עם זאת, היא משתמשת פנימית ב־LAPACK, ולכן נדרשת בנייה שבה LAPACK מופעל; אם היא נבחרת בבנייה ללא LAPACK, התוכנית מסתיימת לפני תחילת האנליזה. לפתרון ברשת הגסה ניתן להשתמש ב־MUMPS בבנייה שבה MUMPS מופעל; אחרת נעשה שימוש בשיטה הישירה המובנית למטריצה צפופה.

SA-AMG מיועדת בעיקר למערכות סימטריות מוגדרות חיובית (CG), אך תומכת גם במערכות מצומצמות לא־סימטריות הנוצרות ממגע בחיכוך (BiCGSTAB, ‏GMRES ואחרות). היא תומכת ב־1 (הולכת חום), 2 (מישור), 3 (מוצק) ו־6 (קליפה) דרגות חופש לצומת, אך אינה תומכת במטריצות שבהן מספר דרגות החופש משתנה מצומת לצומת. ניתן לקבוע את פותר הרשת הגסה, מחזור הרב־רשת, דרגת המחליק ואפשרויות נוספות, אך באנליזות סטנדרטיות אפשר להשתמש בערכי ברירת המחדל. לערכים ולפורמט ראו את רפרנס מילות המפתח. בבניות שבהן GPU (OpenACC) מופעל, שלב החלת קדם־ההתניה רץ על ה־GPU.

כאשר משתמשים ב־SAINV באנליזה מקבילית הכוללת מגע או MPC, עומק החפיפה בחלוקת התחום עשוי להשפיע על ההתכנסות.

שיטות ישירות

שיטה ישירה פותרת את מערכת המשוואות הליניארית באמצעות פירוק מטריצת המקדמים. מאחר שאינה תלויה במספר איטרציות היא רובוסטית, ולעיתים בחירה יציבה באנליזות מגע או באנליזות עם אילוצים. מנגד, צריכת הזיכרון גדלה עם גודל הבעיה.

שיטה ישירה סביבת מקביליות שימוש
MUMPS מקביליות MPI פתרון מטריצה דלילה בשיטה ישירה בסביבת זיכרון מבוזר.
MKL Intel MKL / OpenMP השיטה הישירה של Intel MKL; באופן פנימי פועל Intel PARDISO. במספר תהליכי MPI נעשה שימוש במסלול Cluster MKL. ‏DIRECTmkl הוא כינוי נוסף ל־MKL.

ניתן להשתמש בשיטות ישירות הן במטריצות סימטריות והן במטריצות לא־סימטריות. MUMPS ו־MKL דורשים שהספרייה המתאימה תהיה מקושרת בזמן הבנייה. בסביבה שבה הספרייה אינה קיימת הם אינם זמינים; לספריות התלויות ולאפשרויות CMake הדרושות ראו את מדריך הבנייה.

ל־FrontISTR יש גם מסלול של שיטה ישירה מובנית שאינו משתמש בספרייה חיצונית, אך באנליזה רגילה שבה בוחרים שיטה ישירה, MUMPS או MKL הם המועמדים העיקריים.

בשיטה ישירה לא מוחלת קדם־התניה. גם אם צוינה קדם־התניה ב־!SOLVER, היא אינה נלקחת בחשבון במסלול השיטה הישירה.

שיטת טיפול ב־MPC

שיטת הטיפול ב־MPC קובעת כיצד דרגות חופש המקושרות באילוץ רב־נקודתי משתקפות במשוואות הליניאריות. גם כאשר משוואת האילוץ בקלט זהה, שיטת הטיפול משנה את תכונות מטריצת המקדמים ואת ההתכנסות.

שיטת טיפול ב־MPC תפקיד שימוש ברירת מחדל
שיטת קנס מוסיפה קשיחות גדולה למשוואת האילוץ ומקיימת אותה בקירוב. ברירת המחדל בשיטה ישירה.
סילוק מפורש של דרגות חופש מסלקת את דרגות החופש המאולצות ופותרת מערכת ליניארית מצומצמת. ברירת המחדל בשיטה איטרטיבית.

בשיטה ישירה, שיטת הקנס היא ברירת המחדל; בשיטה איטרטיבית, סילוק מפורש של דרגות חופש הוא ברירת המחדל. שיטת MPC-CG, שהייתה זמינה בעבר, הוסרה; עבור קלט שבו מצוין MPCMETHOD=2 מופקת אזהרה, והעיבוד מתבצע לפי ברירות המחדל האלה.

בסילוק מפורש של דרגות חופש, גם המסות המרוכזות המשמשות באנליזה מודאלית ובאנליזה דינמית מפורשת מצומצמות באמצעות אותה טרנספורמציה של מטריצת הקשיחות. מכיוון שמטריצת המסה המצומצמת אינה אלכסונית בדרך כלל, סכומי השורות שלה משמשים כמסות מרוכזות. באילוצי חיבור או אינטרפולציה שבהם סכום המקדמים במשוואת האילוץ הוא 1, מסת דרגת החופש התלויה מחולקת בין דרגות החופש הראשיות ביחס למקדמים.

ניתן לציין במפורש את שיטת הטיפול ב־MPC באמצעות !SOLVER, בפרמטר MPCMETHOD. למשמעות הערכים ולפורמט ראו את רפרנס מילות המפתח.

סילוק דרגות חופש של מגע

סילוק דרגות חופש של מגע הוא פונקציה המצמצמת את דרגות החופש של המגע המתווספות במגע SLAGRANGE לפני העברת המערכת לפותר הליניארי. סילוק דרגות החופש של המגע עשוי לשפר את תכונות המערכת הליניארית המטופלת בשיטה איטרטיבית.

במצב האוטומטי המוגדר כברירת מחדל, סילוק דרגות החופש של המגע מופעל בעת שימוש בשיטה איטרטיבית ואינו מופעל בעת שימוש בשיטה ישירה. בשיטה ישירה קיים מסלול המטפל במערכת המוגדלת הכוללת את דרגות החופש של המגע כפי שהיא.

כאשר מציינים במפורש CONTACT_ELIM, ניתן לבצע סילוק דרגות חופש של מגע גם בשימוש בשיטה ישירה. לבחירת סוג המגע, זוג המגע ואלגוריתם המגע בצד הקלט, ראו את דף המגע וההטמעה.

פונקציות עזר

לבדיקת התכנסות הפותר וביצועיו ניתן להשתמש באומדן מספר תנאי, פלט מטריצה ופלט יומן. פונקציות אלה אינן דרושות בדרך כלל לאנליזה רגילה ומופעלות לצורכי ניפוי שגיאות או הערכת ביצועים.

פונקציה שימוש הערות
אומדן מספר תנאי מפיק מדד למספר התנאי עבור CG ו־GMRES. זמין בבנייה שבה LAPACK פעיל.
פלט מטריצה שומר לקובץ את המטריצה והאגף הימני המועברים לפותר. תומך בפורמטים Matrix Market, ‏CSR ו־BSR.
DUMPEXIT מסיים את האנליזה לאחר פלט המטריצה. משמש כאשר רוצים לחלץ רק את המטריצה ולאמת אותה בכלי חיצוני.
ITERLOG מפיק היסטוריית התכנסות של השיטה האיטרטיבית. משמש לבדיקת התפתחות השיור.
TIMELOG מפיק את זמן חישוב הפותר. עם VERBOSE מופק פירוט מפורט.
STEPLOG מפיק מידע על צעדים. משמש לבדיקת נוהל האנליזה.
LOGLEVEL מפיק מידע אבחוני כגון מבנה ההיררכיה של קדם־התניות AMG. מוגדר בנפרד מ־ITERLOG ומ־TIMELOG. ערך גדול יותר מגדיל את כמות הפלט.

פלט מטריצה מאפשר לבדוק בכלי חיצוני את מטריצת המקדמים שהורכבה באנליזה. כאשר DUMPEXIT פעיל, האנליזה מסתיימת לאחר שמירת המטריצה והאגף הימני. אומדן מספר התנאי הוא פונקציה ניסיונית הזמינה ב־CG וב־GMRES, ומשמשת לאבחון התכנסות.

נושאים קשורים