Structured singular values and pseudospectra play an important role in assessing the properties of a linear system under structured perturbations. This paper discusses computational aspects of structured pseudospectra for structures that admit an eigenvalue minimization characterization, including the classes of real, skew-symmetric, Hermitian, and Hamiltonian perturbations. For all these structures we develop algorithms that require O (n2) operations per grid point, combining the Schur decomposition with a Lanczos method. These algorithms form the basis of a graphical Matlab interface for plotting structured pseudospectra. © 2009 Elsevier B.V. All rights reserved.