Complexidade exponencial

Preso em um problema de complexidade computacional elevada. O problema é que o tempo computacional cresce exponencialmente no número de observações. A dificuldade está na seleção ótima de bandwidth em estimações não-paramétricas e semiparamétricas para um conjunto grande de dados.
Uma solução simples é realizar a seleção usando subsampling dos dados, mas é uma solução bem aproximada. Uma solução melhor seria paralelizar o algoritmo, mas aí tenho problemas para organizar a infra-estrutura de hardware e como estou sozinho nesse problema também levaria um bom tempo.