מטריצה דלילה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

מטריצה דלילהאנגלית: Sparse Matrix) היא מטריצה שמרבית איבריה בעלי ערך אפס. למטריצה דלילה חשיבות ליעילותם של חישובים נומריים שונים שבהם ניתן להסתפק במעבר רק על איברי המטריצה שאינם בעלי ערך אפס ולקומפקטיות באחסון מידע בינארי. ישנם מספר פורמטים לאחסון מטריצה דלילה, כאשר ניתן להבדיל בין פורמטים תומכי עדכון יעיל של המטריצה, כגון: DOK,‏ LIL,‏ COO ופורמטים התומכים בפעולות מטריצה יעילות (כפל מטריצות, שחלוף וכו'), כגון: CSR ו-CSC. לרוב נעשה שימוש בפורמטים תומכי פעולה יעילה.

מוטיבציה[עריכת קוד מקור | עריכה]

המימוש הטריוויאלי של מבנה נתונים המייצג מטריצה מסדר m על n, (כאשר n,m הם מספרים טבעיים) הינו מערך דו ממדי בעל ממדים מתאימים n,m כאשר כל תא \ a_{ij} במטריצה נגיש במערך באמצעות האינדקסים j,i. כדי לייצג מטריצה מסדר m×n בזיכרון נדרש להקצות זיכרון בגודל לפחות m×n פעמים גודל האיבר הבודד. אם נשתמש במימוש הטריוויאלי של מטריצה בעבור מטריצות מסדרים גבוהים בהן רוב התאים מכילים את הערך 0, נתקל בבעיית זיכרון, למשל: בעבור מטריצה מסדר 10,000×10,000 המכילה מספרים שלמים נצטרך 4byte × 10,000² = 381.5MB, בעבור מטריצה מסדר 100,000×100,000 המכילה מספרים שלמים נצטרך כבר 37.25GB - מספרים מוגזמים לכל הדעות; לכן, בעבור מטריצות מהסוג הנ"ל, אם נאחסן רק את הערכים השונים מ-0 נצטרך כמות זיכרון קטנה הרבה יותר והיא O(nz), כאשר nz מייצג את מספר הערכים השונים מ-0 (nz - Non Zero).

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

כאשר מדברים על מטריצה דלילה מדברים על מטריצה בה רוב התאים מכילים את הערך 0, אך ניתן (לרוב לא רצוי) להחיל את העקרון על כל ערך קבוע. יכולת זו לא נתמכת באופן מוחלט מאחר שיש לערך השפעה על האופן בו מחשבים פעולות על מטריצות דלילות, אך בעבור מטריצה A וערך c קבוע A - c = B כאשר B הינה מטריצה בה הערך 0 החליף את ערכי c כנדרש.

אחסון מטריצה דלילה[עריכת קוד מקור | עריכה]

נחלק את השיטות השונות לאחסון מטריצה דלילה לשתי קבוצות:

  1. שינוי יעיל של המטריצה.
  2. פעולות יעילות על המטריצה.

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

[ 0 0 1 0 ]
[ 3 2 0 0 ]
[ 0 4 0 0 ]
[ 0 0 5 0 ]

שיטות המאפשרות שינוי יעיל של המטריצה[עריכת קוד מקור | עריכה]

(Dictionary of keys (DOK[עריכת קוד מקור | עריכה]

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

row,col]->1]
[0,1]->1
[1,2]->2
[1,3]->3
[2,2]->4
[3,1]->5

(List of lists (LIL[עריכת קוד מקור | עריכה]

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

[row->[val,col
0->[1,1]
1->[2,2]->[3,3]
2->[4,2]
3->[5,1]

(Coordinate list (COO[עריכת קוד מקור | עריכה]

COO הינה שיטה לייצוג התאים השונים מ-0 במטריצה כמערך של שלישיות סדורות המכילות את המיקום והערך של תא במטריצה הקוקנקרטית המקבילה.

[5, 4, 3, 2, 1] :val
[3, 2, 1, 1, 0] :row
[1, 2, 3, 2, 1] :col

שיטות המאפשרות פעולות יעילות על המטריצה[עריכת קוד מקור | עריכה]

אם יש צורך לבנות את המטריצה הדלילה באופן דינאמי, יש לבנותה עם אחת השיטות DOK,LIL,COO ואז להמירה לאחת מהשיטות הבאות:

Yale format[עריכת קוד מקור | עריכה]

שיטת Yale מאחסנת מטריצה דלילה מסדר m×n בתצורת שורה (משמע ע"פ שורה, שורה ואז טור) באמצעות 3 מערכים, A, IA, JA.
A, בגודל nz, הינו המערך המכיל את הערכים השונים מאפס סדורים לפי השורה והטור (משמאל לימין ואז מלמעלה למטה).
IA, בגודל m+1 (מספר השורות + 1), מכיל את מספר האינדקס המכיל את הערך הראשון השונה מאפס במערך A בשורה שהאינדקס שלה הוא אינדקס התא הנוכחי.
JA, בגודל nz, הינו המערך המכיל את מספרי הטור של כל אחד מהערכים השונים מאפס לפי סדרם ב-A.

[A: [1, 2, 3, 4, 5
[IA: [0, 1, 3, 4, 5
[JA: [1, 2, 3, 2, 1

הערה: השיטה הנ"ל חוסכת מקום רק כאשר מתקיים (nz < (m(n - 1) - 1.

(Compressed sparse row (CSR or CRS[עריכת קוד מקור | עריכה]

שיטת CSR למעשה זהה לשיטת Yale, מלבד שמערך הטורים מאוחסן לפני מערך השורות, משמע (val, col_ind, row_ptr). שיטה זו יעילה עבור פעולות ארתמטיות, גזירת שורות ספציפיות ומכפלת מטריצה-וקטור.

(Compressed sparse column (CSC or CCS[עריכת קוד מקור | עריכה]

שיטת CSC דומה לCSR, ההבדל טמון בכך שבעוד CSR היא בתצורת שורה, CSC היא בתצורת טור, משמע במקום לשמור מערך המכיל מצביעים אל תחילת כל שורה במערך הערכים, יהיה מערך המכיל מצביעים אל תחילת כל טור במערך הערכים (ובהתאמה המערך הנוסף המייצג את הקורדינאטה הנוספת). בשיטה זו אופן מילוי המערך A (מערך הערכים) יהיה מלמעלה למטה ואז מימין לשמאל. שיטה זו יעילה עבור פעולות ארתמטיות, גזירת שורות ספציפיות ומכפלת מטריצה-וקטור.

Code Frameworks[עריכת קוד מקור | עריכה]

++C++: SparseLib
‏Python: SciPy