Адаптивное интегрирование
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Адаптивное интегрирование используется в качестве быстрого варианта вычисления интеграла функции, используя адаптивное изменение плотности сетки интегрирования. В тех местах где функция гладкая, сетка будет более разреженная, и наоборот в тех местах, где функция не гладкая, сетка будет сгущаться для получения необходимой точности.
1.2 Математическое описание алгоритма
Формулы метода:
- Производится подсчет интеграла функции квадратурной формулой Симпсона с числом узловых точек равным 4 и 8 на отрезке [a, b].
- Считается разность посчитанных значений
- Если разность посчитанных интегралов меньше либо равна желаемой точности интегрирования ε заканчиваем процедуру.
- Если разность больше, то происходит разбиение отрезка на два [a, (a + b) / 2] и [(a + b) / 2, b] и для каждого отрезка повторяется процедура 1, затем возвращается сумма полученных значений.
Из описания видно, что алгоритм имеет рекурсивную природу.
1.3 Макростуктура алгоритма
Как уже записано в описании алгоритма, основную часть метода составляют рекурсивные вызовы интегралов отрезков меньшей длинны.
1.4 Входные данные
- Функция.
- Отрезок вида [a, b].
- Желаемая точность интегрирования ε.
1.5 Выходные данные
- Интеграл функции на отрезке [a, b] с точностью ε.
2 Программная реализация алгоритма
2.1 Реализации на одном процессоре
Простейшую рекурсивную реализацию данного алгоритма , которая не использует ресурсы параллелизма можно посмотреть здесь.
Реализация с помощью библиотеки Intel TBB для более эффективного использования многоядерных процессоров можно посмотреть здесь.
2.2 Параллельная реализации
2.2.1 Реализация с помощью MPI для межпроцессорного взаимодействия и Intel TBB для внутрипроцессорного взаимодействия
В данной реализации отрезок [a, b] делится на число доступных процессоров, каждый отрезок считается на своем процессоре, рекурсия заменяется на систему задач библиотеки Intel MPI для более эффективного использования многоядерных процессоров.
2.2.2 Реализация только с помощью MPI
В данной реализации рекурсия заменяется на систему задач, каждая задача представляет собой подсчет интеграла на отрезке, в случае если необходимая точность не достигнута (см. Математическое описание алгоритма), создаются две новые задачи с меньшими отрезками и распределяются между другими процессорами. Данная реализация в теории решает проблему неравномерности гладких и не гладких участков функции, в случае когда большая часть участков гладкая и лишь небольшой участок функции сильно осциллирует.
