A generalization of the tree-cotree technique for the removal of imaginary and dc spurious modes in finite-element-based eigenanalysis of 3-D lossy unbounded structures is introduced. Five frequently encountered types of polynomial eigenvalue problems are tackled including: 1) closed structures with finite metals conductivity losses; 2) closed structures with material losses due to migrating charge carriers; 3) open-radiating structures using the absorbing boundary conditions of both first- and second-order; 4) open-radiating structures with finite conductivity metallic objects; and 5) any combination of the aforementioned cases. The resulting polynomial eigenvalue problems are linearized utilizing both the companion and the symmetric approaches. The different linearization techniques are being compared for their efficiency and robustness.