Stochastic collocation method have become the dominating methods for uncertainty quantification and stochastic computing of large and complex systems. Though the idea has been explored in the past, its popularity is largely due to the recent advance of employing high-order nodes such as sparse grids. These nodes allow one to conduct UQ simulations with high accuracy and efficiency.

The critical issue is, without any doubt, the standing challenge of "curse-of-dimensionality". For practical systems with large number of random inputs, the number of nodes for stochastic collocation method can grow fast and render the method computationally prohibitive. Such kind of growth is especially severe when the nodal construction is structured, e.g., tensor grids, sparse grids, etc. One way to alleviate the difficulty is to employ adaptive approach, where the nodes are added only in the region that is needed. To this end, it is highly desirable to design stochastic collocation methods that work with arbitrary number of nodes on arbitrary locations. Another strong motivation is the practical restriction one may face. In many cases one can not conduct simulations at the desired nodes.

In this work, we present an algorithm that allows one to construct high-order polynomial responses based on stochastic collocation on arbitrary nodes. The method is based on constructing a "correct" polynomial space so that multi-dimensional polynomial interpolation can be constructed for any data. We present its rigorous mathematical framework, its practical implementation details, and its applications in high dimensions.