一个使用并行算法进行一维积分的数值库？

Question

是否有一个数值库可以使用并行算法进行一维积分(全局自适应方法)？我的代码基础结构决定了我不能并行地进行多个数值积分，但我必须使用并行算法来加快速度。

谢谢!

Answer 1

Nag C数值库有一个并行版本的自适应求积(link 这里)。他们的诀窍是向用户请求以下函数

void (*f)(const double x[], Integer nx, double fv[], Integer *iflag, Nag_Comm *comm)

在这里，函数"f“在nx脓肿点上计算由向量x[]给出的被积体。这就是并行化出现的原因，因为您可以使用parallel_for (例如，在开虾中实现)来同时计算这些点上的f。积分器本身是单线程的。

Nag是一个非常昂贵的库，但是如果您自己使用数值配方编写积分器，那么使用NAG修改串行实现来创建并行自适应积分器并不困难。

我不能复制数字食谱书，以显示哪里是必要的修改，因为许可证的限制。因此，让我们以梯形规则的最简单的例子为例，其中的实现非常简单，而且众所周知。用梯形规则建立自适应方法的最简单方法是计算点网格上的积分，然后将脓肿点的数目增加一倍，并将结果进行比较。如果结果变化小于所要求的精度，则存在收敛性。

在每一步中，都可以使用以下泛型实现计算梯形规则

double trapezoidal( double (*f)(double x), double a, double b, int n)
{
  double h = (b - a)/n;
  double s = 0.5 * h * (f(a) + f(b));
  for( int i = 1; i < n; ++i ) s += h * f(a + i*h);
  return s;
}

现在，您可以进行以下更改以实现NAG思想

double trapezoidal( void (*f)( double x[], int nx, double fv[] ), double a, double b, int n)
{
  double h = (b - a)/n;
  double x[n+1];
  double fv[n+1];
  for( int i = 0; i < n; ++i ) x[i+1] = (a + i * h);
  x[n] = b;

  f(x, n, fv); // inside f, use parallel_for to evaluate the integrand at x[i], i=0..n

  double s = 0.5 * h * ( fv[0] + fv[n] );
  for( int i = 1; i < n; ++i ) s += h * fv[i];
  return s;
}

然而，这个过程只会在integrand计算非常昂贵的情况下加速您的代码.否则，您应该在更高的循环中并行化代码，而不是在积分器内并行。

Answer 2

为什么不简单地在单个线程算法周围实现一个包装器，该算法将边界的细分积分分配给不同的线程，然后在最后将它们相加在一起？例如：

thread 0: i0 = integral(x0, (x0+x1)/2)
thread 1: i1 = integral((x0+x1)/2, x1)

i = i0 + i1