כפל מטריצות מהיר

נניח שנרצה להכפיל שתי מטריצות $A,B$ מגודל $n\times n$ ולקבל את מטריצת המכפלה $C$ כאשר

האלגוריתם הנאיבי כמובן הוא לחשב את המכפלה לפי הנוסחה לכל $i,j\in [n]$ בזמן ריצה $O(n^3)$ .

לאורך ההסטורייה הצליחו לחסום את בעיית כפל המטריצות בזמנים נמוכים יותר ויותר . נסמן את החזקה של $n$ שתהווה את החסם לאלגוריתם כפל המטריצות ב $\omega$ . ובאופן כללי נסמן את זמן הריצה של כפל מטריצות ב $O(n^{\omega })$ תחת ההבחנה שלא יתאפשר $\omega <2$ כי חייבים לעבור על המטריצות $A,B$ לפחות פעם אחת לצורך החישוב.

מספר חסמים שכדאי להכיר שקיימים-
A) נאיבי: $\omega \le 3$
B) סטרסן: $\omega \le 2.81$
C) קופרסימת ווינוגראד: $\omega \le 2.376$
D) סתות׳רס: $\omega \le 2.374$
E) ואסילבסקה וויליאמס: $\omega \le 2.3729$
F) לה-גאל: $\omega \le 2.37287$

הגדרת FMM
אלגוריתם כפל מטריצות עם זמן $O(n^{3-\epsilon })$ עבור $\epsilon >0$ נקרא FMM - כפל מטריצות מהיר.

בעיית כפל מטריצות בוליאניות BMM
קלט: מטריצות בוליאניות $A,B$ מגודל $n\times n$
פלט: $C=A\cdot B$ כאשר $c_{ij}=\underset{k=1}{\overset{n}{\bigvee }}{a}_{ik}\wedge b_{kj}$

כמובן שאת בעיה זו ניתן לפתור בעזרת FMM בזמן $O(n^{\omega })$ .
נרצה להראות מספר בעיות שניתן לפתור עם FMM ועם BMM

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

הגדרה: $\tilde{O}\text{ notation}$
סימון שמתעלם מכל פקטור פולינומי בזמן הריצה למשל

זיהוי משולשים בגרף

הגדרת משולש בגרף
משולש בגרף לא מכוון הוא מעגל לא מכוון באורך 3 קשתות

בעיית זיהוי המשולשים
קלט: גרף $G=(V,E)$ לא מכוון שמיוצג על ידי מטריצת שכנויות $M$
פלט: האם $G$ מכיל משולש או לא.

הפתרון של הבעיה טמון במשפט הבא:
עבור המטריצה $M^3$ , המחושבת על ידי BMM , האלכסון הראשי ב $M^3$ מכיל 1 אמ״מ $G$ מכיל משולש.

הוכחה:

$\leftarrow$ נניח שהאלכסון הראשי ב $M^3$ מכיל $1$, וצריך שקיים משולש ב $G$
אם כן קיים $i$ כלשהו כך ש $m_{ii}^3=1$ כלומר

כלומר קיים $r$ עבורו

ולכן כל אחד מהגורמים הנ״ל הוא $1$ , $m_{ri}=1$ וגם $\underset{k=1}{\overset{n}{\bigvee }}(m_{ik}\wedge m_{kr})=1$ ולכן קיים $k$ כשלהו עבורו

התוצאה היא שקיבלנו 3 קשתות $m_{ik}=m_{kr}=m_{ri}=1$ כלומר הקשתות $(i,k),(k,r),(r,i)$ שזה בעצם משולש.

$\to$ נניח שב $G$ יש משולש
נסמנו $(a,b),(b,c),(c,a)$ . המשמעות היא שב $M$ מתקיים

נסמן : $i=a,k=b,r=c$ ומהנוסחה שפתחנו עבור ההוכחה הקודמת יתקיים $m_{ii}=m_{aa}=1$ .

משפט:
אם ניתן לפתור את בעיית זיהוי המשולשים קומבינטורית בזמן $\tilde{O}(V^{3-\epsilon })$ אז ניתן לפתור את בעיית $BMM$ בזמן $\tilde{O}(n^{3-\frac{\epsilon }{3}})$ .

זה הקשר שהזכרתי בתחילת הסיכום שאמרתי שנסתכל עליו שתמיד יעמוד בסתירה להנחה שלא ניתן לפתור את בעיית BMM בזמן $O(n^{3-\epsilon })$ .

הוכחה:
קודם כל , נראה דרך שבהינתן אלגוריתם קומבינטורי שפותר בעיית זיהוי משולשים בגרף , אז ניתן לנצל את זה ולבנות אלגוריתם שפותר BMM.
אם כן בהינתן שתי מטריצות $A,B$ מגודל $n\times n$ נרצה לחשב את בעיית המכפלה $C=AB$ כאשר הכפל בוליאני.
לאחר מכן, ננתח זמן ריצה ונראה שבעיית זיהוי המשולשים משפיעה על זמן הריצה של גרף זה.

נבנה גרף תלת צדדי $G=(V,E)$ (כלומר גרף שהקשתות הן רק בין הקבוצות שנגדיר כמו ב גרף דו צדדי) כאשר

נגדיר את הקשתות באופן הבא

במילים איפה שיש $1$ במטריצה $A$ נבנה קשת בין $I$ ל $J$ ואיפה שיש $1$ ב $B$ יש קשת בין $J$ ל $K$ ונוסיף את כל הקשתות האפשריות בין $K$ ל $I$ . נשים לב שיש לנו $3n$ קודקודים ו $O(n^2)$ קשתות.

לדוגמה- עבור המטריצות

הגרף שיווצר יהיה

לשם חלק מהוכחות נשתמש בצבעים האלה תמיד בקונבצייה לייצוג קשת מסויימת בין צדדים. למשל מ $I$ ל $J$ זה תמיד יהיה כחול.

כעת נוכיח טענת עזר ומשם ניגש לניסיונות שלנו להוכיח את הטענה הנ״ל-

למה
עבור $k_{\gamma }\in K$ ו $i_{\alpha }\in I$ הקשת $(i_{\alpha },k_{\gamma })\in E$ משתתפת במשולש אמ״מ $c_{\alpha \gamma }=1$ .

הוכחה:
משולש הוא קשת אדומה, כחולה, ירוקה.
ניקח קשת אדומה כלשהי $(i_{\alpha },k_{\gamma })$ (כי אלו מתקיימות תמיד מהגדרת קשתות אלו), לכן שאר הקשתות במשולש צריכות להיות ירוקה אחת וכחולה אחת.
הכחולה אומרת שתא ב $A$ שווה ל $1$ נניח שהתא הוא $a_{\alpha \beta }$ ובגרף זאת הקשת $(i_{\alpha },j_{\beta })$ ובאופן דומה, הירוקה אומרת שתא ב $B$ הוא $1$ . אם התא הזה הוא $b_{\beta \gamma }$ בגרף זאת תהיה הקשת $(j_{\beta },k_{\gamma })$ ויש לנו משולש. כמו כן כפי שמוגדר כפל מטריצות בוליאני אז

לכן הוכחנו את שתי הצדדים, אם יש משולש בגרף בהכרח ערך המתאים ב $C$ יהיה $1$.

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

	BMM(A,B)
		create  G = (IxJxK, E) from A,B
		C = new matrix[n,n] = {0,0}
		while G contains triangle (i_t,j_l,k_p)
			C[t,p] = 1
			delete (i_t, k_p) from G

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

הוכחת נכונות:
נשווה את $c_{\alpha ,\gamma }$ מתוצאת הכפל הנאיבי ונראה שהאלגוריתם אכן ימקם את הערך המתאים לאיבר זה.
נניח שהנ״ל ערכו $1$ מהלמה שהוכחנו אנחנו יודעים ש $(i_{\alpha },k_{\gamma })\in E$ משתתפת במשולש , כיוון שהשתמשו בזיהוי משולשים כקופסה שחורה ומניחים את נכונותו הרי שהאלגוריתם יזהה אותו ויציב $c_{\alpha ,\gamma }=1$ וימחק את הקשת הזאת.

אם $c_{\alpha \gamma }=0$ אז מהלמה הנ״ל הקשת $(i_{\alpha },k_{\gamma })\in E$ לא שייכת למשולש , האלגוריתם לא יזהה את הקשת הזאת כחלק מהמשולש ולא ישנה את ערכה.

ניסיון 2
הרעיון יהיה לבצע מעין הפרד ומשול של הגרף.
נחלק את $I,J,K$ ל $t$ תתי חלוקות כשבכל תת חלוקה $\frac{n}{t}$ קודקודים

נשים לב שיש לנו $t^3$ שלישיות אפשריות $(I_x,J_y,K_z)$ ועליהן נריץ את האלגוריתם מהניסיון הראשון.

BMM(A,B)
	create  G = (IxJxK, E) from A,B
	C = new matrix[n,n] = {0,0}
	divide I,J,K to t sub sets. (each sub group will have n/t vertex)

	for each (I_x, J_y, K_z)
		while sub graph of those vertex containg edges (i_t, j_l, k_p)
			C[t,p] = 1
			delete (i_t,k_p) from G

הוכחה נכונות:
לפני שבכלל נבדוק מיהו $t$ שיאפשר זמן ריצה אופטימלי. נוכיח שאכן התוצאה בסוף של $C$ נכונה ותהיה שקולה לכפל המטריצות הנאיבי.
בדומה להוכחה הקודמת אם ניקח שלישייה $(i_{\alpha },j_b,k_{\gamma })$ משלישייה $(I_x,J_y,K_z)$ כך שהיא מייצרת משולש בגרף $G$ אז אנחנו יודעים בוודאות שהקשת $(i_{\alpha },k_{\gamma })$ לא נמחקה והיא כעת תמחק באיטרצייה של השלישייה הנ״ל לאחר שתבוצע ההשמה $c_{\alpha \gamma }=1$ . לאחר מכן הקשת תמחק ולא נוכל יותר לזהות משולש עם הקשת $(i_{\alpha },k_{\gamma })$ גם אם נרוץ על שלישייה שמכילה את $I_x,K_z$ בתוכה.

זמן ריצה:
נרצה לספור כמה פעמים האלגוריתם קורא לזיהוי משולשים בגרף מגודל $\frac{3n}{t}$ (גודל של שלישייה אחת).

• מספר ההשמות במטריצה $C$ הוא לכל היותר $n^2$ כגודל המטריצה.
• מספר הפעמים שבהם לא נזהה משולש הוא לכל היותר $t^3$ כיוון שכל פעם שלא מוצאים משולש מיד עוברים לשלשה חדשה.

סך הכל מספר הפעמים שמפעילים את האלגוריתם לזיהוי משולשים הוא $t^2+n^3$ .
נסמן ב $T(n)$ להיות זמן הריצה לאלגוריתם זיהוי משולשים על גרף עם $n$ קודקודים וזמן הריצה של כל האלגוריתם שלנו יהיה:

כלומר עבור $t=n^{\frac{2}{3}}$ נקבל זמן ריצה

APSP על גרף לא מכוון ולא משוקלל

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

הגדרה:
קלט- גרף $G=(V,E)$ קשיר, לא מכוון , לא ממושקל וללא קשתות כפולות שמיוצג על ידי מטריצת שכנויות $A$ .
פלט- לכל $u,v\in V$ נחשב את המסלול הקצר ביותר (במספר הקשתות) בין $u$ ל $v$.

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

כדי להתחיל לבנות את האלגוריתם, נגדיר גרף חדש

המיוצג על ידי מטריצת השכנויות

המשמעות של $A^{\prime }$ היא ש $a_{ij}^{\prime }=1\leftrightarrow (a_{ij}^2=1)\vee a_{ij}=1$ כלומר, במטריצת יהיה $1$ במיקום $ij$ אם ורק אם יש מסלול באורך 2 מ קודקוד $i$ לקודקוד $j$ או שהקודקוד ה $i$ והקודקוד ה $j$ הם שכנים. זה נובע מההבחנה שעשינו בתחילת הסיכום ש $A^n$ מייצג את התכנות המסלולים באורך $n$ בין שתי קודקודים $i,j$ בגרף.

בגלל שהגרף המקורי $G$ הוא קשיר ולא מכוון, הרי שב $A^2$ יהיו איברים באלכסון שערכם יהיה $1$ כיוון שאם יש מסלול באורך 2 מ $i$ ל $j$ בגרף אז בהכרח גם יש מסלול באורך $2$ מ $j$ ל $i$. תחת ההבחנה הזאת נשים לב שבגלל שבגרף שמיוצג על ידי $A^{\prime }$ אסור שיהיו לולאות עצמיות, נדאג לאפס את איברי האלכסון שלו.

הקשתות של הגרף יהיו

כלומר בנוסף לכל הקשתות שיש ל $G$ , הגרף $G^{\prime }$ יבנה קשת נוספת בין כל הקודקודים שבגרף $G$ היה בהם מסלול מאורך 2.

טענה אורך המסלול הקצר ביותר בין $u,v\in V$ בגרף $G^{\prime }$ שקול לחצי מעוגל כלפי מעלה של המסלול הקצר ביותר בינהם בגרף $G$.

הוכחה:
נסמן $p$ את המסלול הקצר ביותר מ $u$ ל $v$ בגרף $G$
נחלק למקרים-
א) $\delta (u,v)=2k$ כלומר $p=(v_1,v_2,v_3\dots ,v_{2k+1})$ . מההגדרה, ב $G^{\prime }$ יש את המסלול $p^{\prime }=(v_1,v_3,\dots ,v_{2k-1},v_{2k+1})$ כלומר מסלול באורך $k$ קשתות.
אם כן , נניח בשלילה ש מסלול זה אינו הקצר ביותר ב $G^{\prime }$ מ $u$ ל $v$ כלומר קיים מסלול אחר $p^{\ast }$ שהוא מינימלי כלומר $|p^{\ast }|<k$ . מהגדרת הקשתות בגרף $G^{\prime }$ אנחנו יודעים שב $G$ יש מסלול שמתאים ל $p^{\ast }$ עם מספר קשתות שקול או לכל היותר $2|p^{\ast }|<2k$ בסתירה למינימליות של $p$ .
כלומר $p^{\prime }$ הוא מסלול קצר ביותר ב $G^{\prime }$ מ $u$ ל $v$ ויתקיים

ב) $\delta (u,v)=2k+1$ כלומר $p=(v_1,v_2,v_3\dots ,v_{2k+2})$ לפי הגדרת $G^{\prime }$ קיים מסלול $p^{\prime }$ בגרף זה כל ש
$p^{\prime }=(v_1,v_3\dots ,v_{2k-1},v_{2k+1},v_{2k+2})$ כלומר מסלול עם $k+1$ קשתות. נניח בשלילה שהוא אינו המסלול הקצר ביותר וקיים $p^{\ast }$ קצר יותר. כלומר $|p^{\ast }|<k+1$ ולכן יש ב $G$ מסלול מתאים ב $p^{\ast }$ עם לכל היותר $2|p^{\ast }|<2k+1$ בסתירה למינימליות של $p$ . כלומר

האלגוריתם הבא פותר את בעיית APSP לגרפים לא מכוונים ולא ממושקלים.
נסמן $\mathrm{\Delta }$ כמטריצת המרחקים הסופית של $G$ ובאופן שקול ${\mathrm{\Delta }}^{\prime }$ כמטריצת המרחקים הסופים של $G^{\prime }$

seidel_generic(A):
	if A is all 1 except for the diagonal 
		return A
	𝚫' = seidel_generic(A*A V A)
		for u,v in V
			if 𝚫[u,v] is odd
				𝚫[u,v] = 𝜹(u,v) = 2𝜹'(u,v)-1
			else 
				𝚫[u,v] = 𝜹(u,v) = 2𝜹'(u,v)
		return 𝚫

נסביר, האלגוריתם בונה כל פעם מטריצה חדשה עד אשר תנאי הבסיס שבו יש קשת ישירה מכל קודקוד בגרף $G^{\prime }$ מתקיים (כיוון שהגרף קשיר אנחנו נבצע את הפעולה הזאת לכל היותר $\log |V|$ פעמים) ולאחר מכן יורדים בחזרה כאשר אנחנו מפרקים אחורנית את ערך המסלול הקצר ביותר לפי המשפט שהראנו למעלה.

נשים לב שבדקנו האם המרחק הקצר ביותר $\delta (u,v)$ בין שתי קודקודים הוא זוגי או אי זוגי מבלי לחשב אותו כלל, איך עשינו זאת?

יהי $u,v\in V$ , נניח ש $w\in V$ שכן של $v$ . על פי למת אי שיוויון המשולש :

יש 4 מקרים עבור הזוגיות של $\delta (u,v)$ ו $\delta (u,w)$
א) $\delta (u,v){\equiv }_2\delta (u,w)$ כלומר הם שקולים מודולו 2. המשמעות של זה היא ששניהם זוגיים או אי זוגיים ביחד ובהכרח יתקיים שיוויון בינהם (כיסינו 2 מקרים).
הסיבה היא-
שאם שניהם זוגיים נסמן $\delta (u,v)=2k$ ו $\delta (u,w)=2r$ ולפי מה שרשמנו למעלה

המספר השלם היחיד שנמצא בין $2k-1$ ל $2k+1$ הוא $2k$ ולכן $2k=2r$ ולכן המרחקים שווים.

באופן דומה אם שניהם אי זוגיים נקבל ש

וההסבר שקול למה שעשינו במקרה הזוגי $2k+1$ הוא המספר השלם היחיד שנמצא בין שתי מספרים אלו.

נשים לב שהמשמעות של תרחיש זה היא ש $w$ אינו במסלול הקצר ביותר מ $u$ ל $v$ ובאופן דומה $v$ אינו במסלול הקצר ביותר מ $u$ ל $w$. זה נובע מאי שיוויון המשולש .

ב) אם $\delta (u,v)$ זוגי ו $\delta (u,w)$ אי זוגי:

כלומר

ג) אם $\delta (u,v)$ אי זוגי ו $\delta (u,w)$ זוגי:

כלומר

הגדרה: נסמן ב $N(v)$ את הקודקודים השכנים של $v$ ב $G$ . נשים לב-

טענה

הוכחה
$\leftarrow$ : $\delta (u,v)$ זוגי ולכן לכל $w$ שכן של $v$ יתקיים $\delta (u,w)$ זוגי או אי זוגי כלומר ממה שהוכחנו

$\to$ נוכיח לפי הcontra positive של הטענה. נניח $\delta (u,v)$ אי זוגי כלומר ממה שהוכחנו למעלה אנחנו יודעים שהמקרים שמתאפשרים על שכן $w$ הוא ש ${\delta }^{\prime }(u,w)\le {\delta }^{\prime }(u,v)$ כלומר

רק נשאר להסביר למה האי שיוויון הזה הוא חזק כלומר במקום $\le$ צריך להיות $<$ הסיבה לכך היא שכפי שאמרנו בהבחנה שלנו עבור השכן $w$ שהוא חלק מהמסלול הקצר ביותר יתקיים אי שיוויון חלש כלומר כל הסכום הזה יהיה קטן ממש ולא קטן או שווה ולכן האי שיוויון חלש וזה מוכיח את הcp של הטענה שלנו.

אם כן אנחנו יכולים לקבוע את הזוגיות של מסלול קצר ביותר מבלי לחשב אותו ישירות בעזרת ערכי ${\delta }^{\prime }$ שלו . מטרתנו כעת היא להבין איך מחשבים את הגורמים הרלוונטים לקביעת הזוגיות באופן יעיל.

א) על מנת לחשב את דרגת הקודקוד עלינו לסרוק את שורת המטריצה של $v$ כלומר יעלה לנו $O(V)$ זמן.
אם כן, חישוב הדרגה לכל הקודקודים הוא $O(V^2)$. סך הכל בהינתן ${\delta }^{\prime }$ נוכל לחשב את הביטוי $\mathrm{deg}(v)\cdot {\delta }^{\prime }(u,v)$ בזמן $O(V^2)$ לכל קודקודי הגרף.

ב) כדי לחשב את $\sum _{w\in N(v)}{\delta }^{\prime }(u,w)$ נגדיר את המטריצה $M={\mathrm{\Delta }}^{\prime }\cdot A$ (הכפל הוא רגיל ולא בוליאני). נוכיח ש

הוכחה -

האלגוריתם של סיידל

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

seidel(A):
	if A is all 1 except for the diagonal
		return A
	𝚫' = seidel(A*A V A)
	M = 𝚫'* A
	for u,v in V
		if M[u,v] < deg(v)𝚫'[u,v]
			𝚫[u,v] = 2𝚫'[u,v]-1
		else
			𝚫[u,v] = 2𝚫'[u,v]
	return 𝚫

זמן ריצה
אם אורך המסלול הארוך ביותר בגרף הוא $d$ , אז צריך $\mathrm{\Theta }(\log d)$ איטרציות לפני שנגיע למקרה הבסיס במקרה הגרוע $d=|V|$ . בנוסף לכל יש את העבודה המקומית שהיא ביצוע כפל מטריצות מהיר FMM וחישוב דרגות כל קודקודי הגרף. זמן העבודה המקומית הוא

כי כפי שאמרנו $\omega >2$ בהכרח. ביחד עם הקריאה הריקורסיבית והתייחסות לעומק עץ הריקורסייה זמן הריצה יהיה