Graph expansion and communication costs of fast matrix multiplication: Regular submission

Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

The communication cost of algorithms (also known as I/O-complexity) is shown to be closely related to the expansion properties of the corresponding computation graphs. We demonstrate this on Strassen's and other fast matrix multiplication algorithms, and obtain the first lower bounds on their communication costs. For sequential algorithms these bounds are attainable and so optimal.

שפה מקוריתאנגלית אמריקאית
כותר פרסום המארחSPAA'11 - Proceedings of the 23rd Annual Symposium on Parallelism in Algorithms and Architectures
עמודים1-11
מספר עמודים11
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2011
פורסם באופן חיצוניכן
אירוע23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11 - San Jose, CA, ארצות הברית
משך הזמן: 4 יוני 20116 יוני 2011

סדרות פרסומים

שםAnnual ACM Symposium on Parallelism in Algorithms and Architectures

כנס

כנס23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11
מדינה/אזורארצות הברית
עירSan Jose, CA
תקופה4/06/116/06/11

ASJC Scopus subject areas

  • ???subjectarea.asjc.1700.1712???
  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1708???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Graph expansion and communication costs of fast matrix multiplication: Regular submission'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי