  In this article, we propose the use of partitioning and clustering methods as
an alternative to Gaussian quadrature for stochastic collocation. The key idea
is to use cluster centers as the nodes for collocation. In this way, we can
extend the use of collocation methods to uncertainty propagation with
multivariate, dependent input, in which the output approximation is piecewise
constant on the clusters. The approach is particularly useful in situations
where the probability distribution of the input is unknown, and only a sample
from the input distribution is available. We examine several clustering methods
and assess the convergence of collocation based on these methods both
theoretically and numerically. We demonstrate good performance of the proposed
methods, most notably for the challenging case of nonlinearly dependent inputs
in higher dimensions. Numerical tests with input dimension up to 16 are
included, using as benchmarks the Genz test functions and a test case from
computational fluid dynamics (lid-driven cavity flow).
