In the field of structural-acoustics, there is considerable interest in finding an efficient method for computing fluid-coupled mode shapes, resonance frequencies, and loss factors. The computations are difficult because the acoustic field created by a vibrating structure is generally not a simple function of frequency, making the associated eigenvalue problem nonlinear. A state-space formulation has been used previously to solve structural-acoustic eigenvalue problems for combined finite element / boundary element analyses. In this paper, the formulation is adapted for the software package ARPACK by generalizing the previous results for arbitrary polynomial order and developing simple formulas for the matrix inverse and matrix-vector multiplication required within ARPACK. Using an example problem of a circular cylinder, it is shown that higher order polynomial expansions can actually increase the overall computational efficiency because they allow a wider frequency range to be represented during a single iteration, resulting in fewer subdivisions of the overall frequency range.