Nonnegative Matrix Factorization is a data analysis tool that aims at representing a set of input data vectors as nonnegative linear combinations of a few nonnegative basis vectors. When dealing with continuous input signals, smoothness and accuracy of this representation can often be improved if nonnegative polynomials are used in the basis instead of vectors. However, algorithms using polynomials are usually more computationally demanding than their vector counterparts.In this work, we consider the Hierarchical Alternating Least Squares method, which displays state-of-the art performance on this problem and requires at each iteration to compute projections over the set of nonnegative polynomials. We introduce several heuristic algorithms designed to provide fast approximations of these projections, and show that their use significantly accelerates the resolution of nonnegative matrix factorization problems over polynomial signals without adverse effect on the accuracy of the obtained solutions.