Polynomial Chaos Generalizability and Reduction

[fbelik]

Interested in making the polynomial chaos (PCE) methods more general and applicable to expensive models. Happy to open a PR for this if there is interest! I already have basic implementations of these locally.

Ideas:

• Allow constructor for PolynomialChaosBasis to take in various multi-index sets α. This would mean moving the defined inner constructor outside of the struct and allowing that method to accept as input an arbitrary multi-index set α (with possible assertions to make sure it is a reasonable multi-index set).
• Rename multivariate_indices to total_degree_set or something similar. Then, perhaps create methods for hyperbolic_cross_set and q_ball_set.
• Remove factorial calls from line 63 and replace with binomial(p+d,d) in case p+d>20 and the factorial overflows.
• Implement weighted approximate Feteke points (WAFP) option for polynomial chaos with least squares constructor as in UncertainSCI and as described in this paper. This will not reduce the number of polynomial evaluations but can reduce the number of model evaluations drastically allowing for significant speed ups when the bottle-neck is model evaluations. This would mean polynomial_chaos(inputs,model,Ψ,output,ls) would have possibly three additional (optional) arguments of whether the user wishes to use WAFP sampling and its hyper parameters. WAFP sampling would not replace MonteCarlo or SobolSampling, it would form a sparse subsample from one of these options.

[FriesischScott]

I'll take a closer look at the paper but this sounds very interesting. Reducing the number of model calls required for the PCE is always great.

[FriesischScott]

First of all the WAFP sampling would be great to have and we'd very much appreciate a PR. It's also great to have a method that doesn't originate in engineering. Instead of adding optional inputs to the existing method I would prefer to introduce a new WeightedApproximateFeketePoints struct and dispatch on this.

However, as it's independent from the sampling used generalizing the basis to alternative muti-indices is best done in a separate PR I think.

[fbelik]

Sounds good, I can plan to make a new PR for the WAFP method on its own. I have implemented a WeightedApproximateFeketePoints struct and methods for polynomialchaos where ls::LeastSquares or ::GaussQuadrature is replaced with wafp::WeightedApproximateFetekePoints. It seems to work very well when the underlying function is well represented by the PolynomialChaosBasis. In the case that the basis does not capture well the model, the result will likely be worse than a Monte-Carlo approach I can attach some testing code to the PR.

I agree that the generalization of multi-indices is a separate topic. I can plan to make that a separate PR if that would be of interest.

I also noticed one other possible update (also unrelated to WAFP). It pertains to the evaluation of a PolynomialChaosBasis. The current code is a nice one-linear but is unfortunately quite a bit slower on my machine due to the excess allocations (maybe 5-10x slower) than a for loop. If you are okay with making this function a bit longer, see the below screenshot for the modification.

I was similarly able to get another big speedup in the least squares (and WAFP) polynomial chaos method by replacing the one-liner for forming the Vandermonde-type matrix, A, with a loop (see below)

[fbelik]

I'm glad we were able to get WAFP implemented! I am not sure that implementing different types of multi-indices is immediately essential (unless an application requires very high individual polynomial degrees but a sparse multi-index set in which case the hyperbolic cross set may be useful). @FriesischScott what are your thoughts on the two modifications above for a speed-up in polynomial evaluations and formation of the Vandermonde matrix A? I noticed a significant speedup for moderate sized multi-index sets with the changes I suggested in my previous comment.

Here is an example of the runtime difference. I noticed it in testing when calling polynomial_chaos in the runtime needed to form the Vandermonde matrix.

And here is with changing how the Vandermonde matrix is formed.

[FriesischScott]

I'm glad we were able to get WAFP implemented!

Thanks again for the contribution!

I am not sure that implementing different types of multi-indices is immediately essential (unless an application requires very high individual polynomial degrees but a sparse multi-index set in which case the hyperbolic cross set may be useful).

Yes, there's still lot to be done for the PCE in general. I'll be opening a new issue to track larger changes and improvements like sparse PCE and sparse quadrature rules. You seem to know a lot more about PCE than I do and I'd be grateful for some input on what to implement. I'll ping you in the new issue if you don't mind.

What are your thoughts on the two modifications above for a speed-up in polynomial evaluations and formation of the Vandermonde matrix A?

Improving efficiency and readability is always great. I'd be happy to accept a PR with your proposed improvements!