使用並行算法進行一維集成的數字圖書館？

Question

有沒有可以使用並行算法進行一維積分（全局自適應方法）的數值庫？我的代碼基礎設施決定我不能並行進行多個數字集成，但我必須使用並行算法來加速。

謝謝！

Answer 1

Nag C數值庫有自適應正交（鏈路here）的並行版本。其關鍵是要請求用戶下面的函數

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

在這裏，函數「f」的計算結果在由矢量x[]給出nx abscise點積。這是並行化出現的地方，因爲您可以使用parallel_for（例如在openmp中實現）在這些點上同時評估f。集成商本身是單線程的。

Nag是一個非常昂貴的庫，但如果您使用自己的代碼集成器，例如numerical recipes，修改串行實現以創建使用NAG想法的並行自適應集成器並不困難。

我無法複製數字食譜書籍以顯示由於許可證限制需要修改的地方。那麼我們來看一下trapezoidal rule的最簡單的例子，其中的實現非常簡單而且衆所周知。使用梯形法則創建自適應方法的最簡單方法是計算網格點處的積分，然後加倍離散點數並比較結果。如果結果變化小於要求的精度，則會收斂。

在每一步，梯形規則可以使用以下通用實施

double trapezoidal(void (*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; 
} 

這個程序來計算，但是，將只有在被積函數計算非常昂貴的情況下才能加速代碼。否則，您應該在較高的循環中並行處理代碼，而不要在集成器中進行並行處理。

Answer 2

爲什麼不簡單地實現一個包裝單個線程算法的包裝器，該算法將邊界的細分積分分配給不同的線程，然後在最後將它們相加？例如

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

i = i0 + i1