关键词：沟通成本；矩阵乘法；内存模型
摘 要：In this note we obtain communication cost lower and upper bounds on the algo-rithms for LU and QR given in (Demmel, Dumitriu, and Holtz 2007). The algorithmsthere use fast, stable matrix multiplication as a subroutine and are shown to be asstable and as computationally effcient as the matrix multiplication subroutine. Weshow here that they are also as communication-effcient (in the sequential, two-level memory model) as the matrix multiplication algorithm. The analysis for LU and QRextends to all the algorithms in (Demmel, Dumitriu, and Holtz 2007). Further, weprove that in the case of using Strassen-like matrix multiplication, these algorithmsare communication optimal.