A parallel unstructured finite volume method is presented for analysis of the stability of two-dimensional steady Oldroyd-B fluid flows to small amplitude three-dimensional perturbations. A semi-staggered dilation-free finite volume discretization with Newton's method is used to compute steady base flows. The linear stability problem is treated as a generalized eigenvalue problem (GEVP) in which the rightmost eigenvalue determines the stability of the base flow. The rightmost eigenvalues associated with the most dangerous eigenfunctions are computed through the use of the shift-invert Arnoldi method. To avoid fine meshing in the regions where the flow variables are changing slowly, a local mesh refinement technique is used in order to increase numerical accuracy with a lower computational cost. The CUBIT mesh generation environment has been used to refine the quadrilateral meshes locally. In order to achieve higher performance on parallel machines the algebraic systems of equations resulting from the steady problem and the GEVP have been solved by implementing the MUltifrontal Massively Parallel Solver (MUMPS). The proposed method is applied to the linear stability analysis of the flow of an Oldroyd-B fluid past a linear periodic array of circular cylinders in a channel and a linear array of circular half cylinders placed on channel walls. Two different leading eigenfunctions are identified for close and wide cylinder spacing for the periodic array of cylinders. The numerical results indicate good agreement with the numerical and experimental results available in the literature. Crown Copyright (C) 2008 Published by Elsevier B.V. All rights reserved.