  We study spectra and pseudospectra of certain bounded linear operators on
$\ell^2({\mathbb Z})$. The operators are generally non-normal, and their matrix
representation has a characteristic off-diagonal decay. Based on a result of
Chandler-Wilde, Chonchaiya and Lindner for tridiagonal infinite matrices, we
demonstrate an efficient algorithm for the computation of upper and lower
bounds on the pseudospectrum of operators that are merely norm limits of band
matrices -- the so-called band-dominated operators. After approximation by a
band matrix and fixing a parameter $n\in{\mathbb N}$, one looks at $n$
consecutive columns $\{k+1,...,k+n\}$, $k\in{\mathbb Z}$, of the corresponding
matrix and computes the smallest singular value of that section via QR
factorization. We here propose a QR factorization by a sequence of Givens
rotations in such a way that a large part of the computation can be reused for
the factorization of the next submatrix -- when $k$ is replaced by $k+1$. The
computational cost for the next factorization(s) is ${\mathcal O}(nd)$ as
opposed to a naive implementation with ${\mathcal O}(nd^2)$, where $d$ is the
bandwidth. So our algorithm pays off for large bands, which is attractive when
approximating band-dominated operators with a full (i.e. not banded) matrix.
