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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2011
منشور خارجيًانعم
الحدث23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11 - San Jose, CA, الولايات المتّحدة
المدة: ٤ يونيو ٢٠١١٦ يونيو ٢٠١١

سلسلة المنشورات

الاسمAnnual ACM Symposium on Parallelism in Algorithms and Architectures

!!Conference

!!Conference23rd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA'11
الدولة/الإقليمالولايات المتّحدة
المدينةSan Jose, CA
المدة٤/٠٦/١١٦/٠٦/١١

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!Theoretical Computer Science
  • !!Hardware and Architecture

بصمة

أدرس بدقة موضوعات البحث “Graph expansion and communication costs of fast matrix multiplication: Regular submission'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا