1 차원 적분을 수행하기 위해 병렬 알고리즘을 사용하는 수치 라이브러리?

Question

병렬 적응 알고리즘을 사용하여 1 차원 적분 (전역 적응 방법)을 수행 할 수있는 수치 라이브러리가 있습니까? 코드의 인프라는 여러 개의 수치 적분을 병렬 적으로 수행 할 수 없다고 결정하지만 속도를 높이기 위해서는 병행 알고리즘을 사용해야합니다.

감사합니다.

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의 가장 간단한 예제를 살펴 보겠습니다. 사다리꼴 규칙을 사용하여 적응 방법을 만드는 가장 간단한 방법은 점 격자에서 적분을 계산 한 다음 abscise 점의 수를 두 배로하여 결과를 비교하는 것입니다. 결과가 요청한 정확도보다 작 으면 컨버전스가 발생합니다. 각 단계에서

는 사다리꼴 규칙은 것입니다, 그러나, 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; 
} 

을 구현하기 위해 이제 다음과 같이 변경할 수 있습니다 다음과 같은 일반적인 구현

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; 
} 

을 사용하여 계산 될 수있다 integrand가 계산하는 데 비용이 많이 든다면 코드 속도를 높이십시오. 그렇지 않으면 더 높은 루프에서 코드를 병렬화해야하며 통합 자 내부에서는 병렬화해야합니다.

Answer 2

경계의 세분의 적분을 다른 스레드에 전달한 다음 단일 스레드 알고리즘에 래퍼를 구현 한 다음 끝에 함께 추가하는 것은 어떻습니까? 예 :

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

i = i0 + i1