Адаптивное интегрирование: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
 
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
Незаконченный вариант статьи
 
  
== Свойства и структура алгоритма ==
 
 
=== Общее описание алгоритма ===
 
 
'''Адаптивное интегрирование''' используется в качестве быстрого варианта вычисления интеграла функции, используя адаптивное изменение плотности сетки интегрирования. В тех местах где функция гладкая, сетка будет более разреженная, и наоборот в тех местах, где функция не гладкая, сетка будет сгущаться для получения необходимой точности.
 
 
=== Математическое описание алгоритма ===
 
 
Формулы метода:
 
 
# Производится подсчет интеграла функции квадратурной [https://ru.wikipedia.org/wiki/Формула_Симпсона формулой Симпсона] с числом узловых точек равным 4 и 8 на отрезке [a, b].
 
# Считается разность посчитанных значений
 
## Если разность посчитанных интегралов меньше либо равна желаемой точности интегрирования ε заканчиваем процедуру.
 
## Если разность больше, то происходит разбиение отрезка на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.
 
 
Из описания видно, что алгоритм имеет рекурсивную природу.
 
 
=== Макростуктура алгоритма ===
 
 
Как уже записано в описании алгоритма, основную часть метода составляют рекурсивные вызовы интегралов отрезков меньшей длинны.
 
 
=== Входные данные ===
 
 
* Функция.
 
* Отрезок вида [a, b].
 
* Желаемая точность интегрирования ε.
 
 
=== Выходные данные ===
 
 
* Интеграл функции на отрезке [a, b] с точностью ε.
 
 
== Программная реализация алгоритма ==
 
 
=== Исходный код реализованного алгоритма ===
 
 
Весь исходный код в статье можно найти в репозитории на [https://github.com/bvdmitri/aintegrate GitHub].
 
 
=== Реализации на одном процессоре ===
 
 
Простейшую рекурсивную реализацию данного алгоритма , которая не использует ресурсы параллелизма можно посмотреть [https://github.com/bvdmitri/aintegrate/blob/master/src/method/sequential/SequentialMethod.cpp здесь].
 
 
<source lang="c++">
 
#include "SequentialMethod.h"
 
 
SequentialMethod::SequentialMethod(double eps, const std::function<double(double)> &f) : IntegrationMethod(eps, f) {}
 
 
double SequentialMethod::integrate(double a, double b) {
 
    double x = simpson(a, b, 4);
 
    double y = simpson(a, b, 8);
 
    if (fabs(x - y) < eps) {
 
        return y;
 
    } else {
 
        return integrate(a, (a + b) / 2.0) + integrate((a + b) / 2.0, b);
 
    }
 
}
 
 
SequentialMethod::~SequentialMethod() {}
 
</source>
 
 
<br>
 
Реализация с помощью библиотеки [https://www.threadingbuildingblocks.org Intel TBB] для более эффективного использования многоядерных процессоров можно посмотреть [https://github.com/bvdmitri/aintegrate/blob/master/src/method/tbb/TBBMethod.cpp здесь].
 
 
<source lang="c++">
 
 
#include "TBBMethod.h"
 
 
TBBMethod::TBBMethod(double eps, const std::function<double(double)> &f) : IntegrationMethod(eps, f) {}
 
 
double TBBMethod::integrate(double a, double b) {
 
    double x = simpson(a, b, 4);
 
    double y = simpson(a, b, 8);
 
    if (fabs(x - y) < eps) {
 
        return y;
 
    } else {
 
        tbb::task_group group;
 
 
        group.run([&] {
 
            x = integrate(a, (a + b) / 2.0);
 
        });
 
 
        group.run_and_wait([&] {
 
            y = integrate((a + b) / 2.0, b);
 
        });
 
 
        return x + y;
 
    }
 
}
 
 
TBBMethod::~TBBMethod() {}
 
 
</source>
 
 
=== Параллельная реализации ===
 
 
==== Реализация с помощью MPI для межпроцессорного взаимодействия и [https://www.threadingbuildingblocks.org Intel TBB]  для внутрипроцессорного взаимодействия ====
 
 
[https://github.com/bvdmitri/aintegrate/blob/master/src/method/mpi_tbb/MPI_TBBMethod.cpp Исходный код]
 
 
В данной реализации отрезок [a, b] делится на число доступных процессоров, каждый отрезок считается на своем процессоре, рекурсия заменяется на [https://www.threadingbuildingblocks.org/tutorial-intel-tbb-task-based-programming систему] задач библиотеки Intel MPI для более эффективного использования многоядерных процессоров.
 
 
==== Реализация только с помощью MPI ====
 
 
[https://github.com/bvdmitri/aintegrate/tree/master/src/method/mpi_farm Исходный код]
 
 
В данной реализации рекурсия заменяется на систему задач, каждая задача представляет собой подсчет интеграла на отрезке, в случае если необходимая точность не достигнута (см. Математическое описание алгоритма), создаются две новые задачи с меньшими отрезками и распределяются между другими процессорами. Данная реализация в теории решает проблему неравномерности гладких и не гладких участков функции, в случае когда большая часть участков гладкая и лишь небольшой участок функции сильно осциллирует.
 

Текущая версия на 00:32, 14 ноября 2016