Kommunikationskostnaden för algoritmer (även känd som I/O-komplexitet) visas vara nära relaterad till expansionsegenskaperna för motsvarande beräkningsdiagram. Vi demonstrerar detta på Strassens och andra snabba matris multiplikationsalgoritmer, och få de första lägre gränserna på deras kommunikationskostnader. I det sekventiella fallet, där processorn har ett snabbt minne av storlek M, för litet för att lagra tre n- by- n matriser, är den lägre gränsen på antalet ord som rör sig mellan snabbt och långsamt minne, för en stor klass av matrismultiplikationsalgoritmer, ((n/ M) 0 · M), där 0 är exponenten i det aritmetiska antalet (t. ex., 0 = lg 7 för Strassen, och 0 = 3 för konventionell matris multiplikation). Med p parallella processorer, var och en med snabbt minne av storlek M, är den nedre gränsen asymptotiskt lägre med en faktor av p. Dessa gränser kan uppnås både för sekventiella och för parallella algoritmer och därmed optimal.
Författare presenterar beräknings- och kommunikationskostnader analyser av algoritmen, och visar att det matchar kommunikationen lägre gränser som beskrivs i REF.
Graph expansion and communication costs of fast matrix multiplication
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}