We consider the problem of computing an approximate banded solution of the continuous-time Lyapunov equation (AX) under bar + (XA) under bar (T) = (P) under bar, where the coefficient matrices (A) under bar and (P) under bar are large, symmetric banded matrices. The (sparsity) pattern of (A) under bar describes the interconnection structure of a large-scale interconnected system. Recently, it has been shown that the entries of the solution (X) under bar are spatially localized or decaying away from a banded pattern. We show that the decay of the entries of (X) under bar is faster if the condition number of (A) under bar is smaller. By exploiting the decay of entries of (X) under bar, we develop two computationally efficient methods for approximating (X) under bar by a banded matrix. For a well-conditioned and sparse banded (A) under bar, the computational and memory complexities of the methods scale linearly with the state dimension. We perform extensive numerical experiments that confirm this, and that demonstrate the effectiveness of the developed methods. The methods proposed in this paper can be generalized to (sparsity) patterns of (A) under bar and (P) under bar that are more general than banded matrices. The results of this paper open the possibility for developing computationally efficient methods for approximating the solution of the large-scale Riccati equation by a sparse matrix. (C) 2016 Elsevier Ltd. All rights reserved.