  We consider the problem of computing an approximate banded solution of the
continuous-time Lyapunov equation
$\underline{A}\underline{X}+\underline{X}\underline{A}^{T}=\underline{P}$,
where the coefficient matrices $\underline{A}$ and $\underline{P}$ are large,
symmetric banded matrices. The (sparsity) pattern of $\underline{A}$ describes
the interconnection structure of a large-scale interconnected system. Recently,
it has been shown that the entries of the solution $\underline{X}$ are
spatially localized or decaying away from a banded pattern. We show that the
decay of the entries of $\underline{X}$ is faster if the condition number of
$\underline{A}$ is smaller. By exploiting the decay of entries of
$\underline{X}$, we develop two computationally efficient methods for
approximating $\underline{X}$ by a banded matrix. For a well-conditioned and
sparse banded $\underline{A}$, 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 $\underline{A}$ and $\underline{P}$ 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.
