Many people would say that Calderon-Zygmund operators have almost diagonal matrices in orthonormal wavelet bases. We will show that this statement is not true as stated. In contrast, the ''non-standard matrix representation'' of Calderon-Zygmund operators always yields almost diagonal matrices. The Beyklin-Coifman-Rokhlin fast algorithm amounts to replacing these almost diagonal matrices by banded ones. We compute the operator norm of the error term in this approximation and give sharp estimates. (C) 1996 Academic Press, Inc.