Airborne and spaceborne hyperspectral sensors, due to their limited spatial resolution, often record the spectral response of a mixture of materials. In order to extract the abundances of these materials, linear and nonlinear unmixing algorithms have been developed. In this paper, we focus on nonlinear mixing models that are able to model macro-and microscopic scale interactions. Although very useful, these models may be inverted only by means of optimization techniques, typically impossible to be performed in matrix form. Thereby, only nonlinear mixing models that describe macroscopic effects (e.g., two-reflections schemes) are currently considered as they have lower computational costs. On the other hand, this limitation may result in a loss in terms of description accuracy for the images. In this paper, we propose a new approach for nonlinear unmixing that aims at providing excellent reconstruction performance for arbitrary polynomial nonlinearities making use of the polytope decomposition (POD) method. Additionally, POD transforms nonlinear unmixing into a linear problem, and can be easily implemented in high-performance computing architectures. Results using synthetic and real data confirm the effectiveness and accuracy of the proposed framework. To prove its feasibility for fast computational applications, its complexity is analytically derived and compared with real data analysis.