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

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

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

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

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

הזן את מטריקס

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

הדרך המסורתית להכפיל שניים n-על ידי-n מטריצות - על ידי הכפלת מספרים מכל שורה במטריצה ​​הראשונה במספרים בעמודות בשנייה - דורשת n³ הכפלות נפרדות. עבור מטריצות של 2 על 2, זה אומר 2³ או 8 הכפלות.

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

שטראסן ניצל את אותו רעיון כדי להראות שהכל גדול יותר n-על ידי-n ניתן גם להכפיל מטריצות בפחות מ- n³ צעדים. מרכיב מרכזי באסטרטגיה זו כרוך בהליך הנקרא פירוק - פירוק מטריצה ​​גדולה לתת-מטריצות קטנות יותר ברציפות, שעלולות להיות קטנות כמו 2 על 2 או אפילו 1 על 1 (אלה רק מספרים בודדים).

הרציונל לחלוקת מערך ענק לחתיכות זעירות הוא די פשוט, לפי וירג'יניה וסילבסקה וויליאמס, מדען מחשבים במכון הטכנולוגי של מסצ'וסטס ומחבר שותף של אחד המאמרים החדשים. "קשה לאדם להסתכל על מטריצה ​​גדולה (נניח בסדר גודל של 100 על 100) ולחשוב על האלגוריתם הטוב ביותר האפשרי", אמרה ואסילבסקה וויליאמס. אפילו מטריצות של 3 על 3 עדיין לא נפתרו במלואן. "עם זאת, אפשר להשתמש באלגוריתם מהיר שכבר פיתח עבור מטריצות קטנות כדי להשיג גם אלגוריתם מהיר עבור מטריצות גדולות יותר."

המפתח למהירות, קבעו חוקרים, הוא להפחית את מספר שלבי הכפל, ולהוריד את המעריך מ n³ (עבור השיטה הסטנדרטית) ככל שהם יכולים. הערך הנמוך ביותר האפשרי, n², הוא בעצם כל זמן שנדרש רק כדי לכתוב את התשובה. מדעני מחשבים מתייחסים לאותו המעריך כאל אומגה, ω, עם n^ω להיות כמה שפחות צעדים האפשריים הדרושים כדי להצליח להכפיל שניים n-על ידי-n מטריצות כמו n גדל מאוד. "הפואנטה של ​​העבודה הזו", אמר ג'ואו, שגם היה שותף למחברת המאמר בינואר 2024, "היא לראות עד כמה קרוב ל-2 אתה יכול להגיע, והאם ניתן להשיג זאת בתיאוריה."

פוקוס לייזר

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

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

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

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

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

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

והניתוח הזה הוא מה שהוביל לשיפור הגדול ביותר באומגה מזה יותר מעשור.

נמצא הפסד

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

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

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

לאחר שהוכיח את קיומו של אובדן זה, הצוות של דואן שינה את האופן שבו שיטת הלייזר סימנה בלוקים, והפחית את הפסולת באופן משמעותי. כתוצאה מכך, הם קבעו גבול עליון חדש לאומגה בסביבות 2.371866 - שיפור לעומת הגבול העליון הקודם של 2.3728596, נקבע בשנת 2020 מאת ג'וש אלמן ווסילבסקה וויליאמס. זה עשוי להיראות כמו שינוי צנוע, המוריד את הגבול בכ-0.001 בערך. אבל זה השיפור הגדול ביותר שראו מדענים מאז 2010. התוצאה של ואסילבסקה וויליאמס ואלמן לשנת 2020, לשם השוואה, השתפרה רק ב-0.00001 לעומת קודמתה.

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

המאמר של ינואר 2024 חידד את הגישה החדשה הזו, ואיפשר לווסילבסקה וויליאמס, ג'ואו ולחבריהם המשותפים לצמצם עוד יותר את ההפסד הנסתר. זה הוביל לשיפור נוסף של הגבול העליון של האומגה, והפחית אותו ל-2.371552. המחברים גם הכלילו את אותה טכניקה לשיפור תהליך הכפל עבור מלבני (n-על ידי-m) מטריצות - הליך שיש לו יישומים בתורת הגרפים, למידת מכונה ותחומים אחרים.

התקדמות נוספת בכיוון הזה היא כמעט בטוחה, אבל יש גבולות. בשנת 2015, לה גאל ושני משתפי פעולה הוכיח שהגישה הנוכחית - שיטת הלייזר יחד עם המתכון של Coppersmith-Winograd - לא יכולה להניב אומגה מתחת ל-2.3078. כדי לבצע שיפורים נוספים, אמר לה גאל, "עליך לשפר את [הגישה] המקורית של קופרסמית' ווינוגרד שלא ממש השתנתה מאז 1987". אבל עד כה, אף אחד לא מצא דרך טובה יותר. אולי אפילו לא יהיה אחד.

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