The primary objective of this study is to develop new computational methods for solving a general random eigenvalue problem (REP) commonly encountered in modeling and simulation of high-dimensional, complex dynamic systems. Four major research directions, all anchored in polynomial dimensional decomposition (PDD), have been defined to meet the objective. They involve: (1) a rigorous comparison of accuracy, efficiency, and convergence properties of the polynomial chaos expansion (PCE) and PDD methods; (2) development of two novel multiplicative PDD methods for addressing multiplicative structures in REPs; (3) development of a new hybrid PDD method to account for the combined effects of the multiplicative and additive structures in REPs; and (4) development of adaptive and sparse algorithms in conjunction with the PDD methods. The major findings are as follows. First, a rigorous comparison of the PCE and PDD methods indicates that the infinite series from the two expansions are equivalent but their truncations endow contrasting dimensional structures, creating significant difference between the two approximations. When the cooperative effects of input variables on an eigenvalue attenuate rapidly or vanish altogether, the PDD approximation commits smaller error than does the PCE approximation for identical expansion orders. Numerical analysis reveal higher convergence rates and significantly higher efficiency of the PDD approximation than the PCE approximation. Second, two novel multiplicative PDD methods, factorized PDD and logarithmic PDD, were developed to exploit the hidden multiplicative structure of an REP, if it exists. Since a multiplicative PDD recycles the same component functions of the additive PDD, no additional cost is incurred. Numerical results show that indeed both the multiplicative PDD methods are capable of effectively utilizing the multiplicative structure of a random response. Third, a new hybrid PDD method was constructed for uncertainty quantification of high-dimensional complex systems. The method is based on a linear combination of an additive and a multiplicative PDD approximation. Numerical results indicate that the univariate hybrid PDD method, which is slightly more expensive than the univariate additive or multiplicative PDD approximations, yields more accurate stochastic solutions than the latter two methods. Last, two novel adaptive-sparse PDD methods were developed that entail global sensitivity analysis for defining the relevant pruning criteria. Compared with the past developments, the adaptive-sparse PDD methods do not require its truncation parameter(s) to be assigned a priori or arbitrarily. Numerical results reveal that an adaptive-sparse PDD method achieves a desired level of accuracy with considerably fewer coefficients compared with existing PDD approximations.