Алговики - Вклад [ru]

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T16:09:55Z

Valkyrie: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции - вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.
Таким образом, на текущем отрезке интегрирования <math>[a,b]</math> выполняется следующая последовательность макроопераций:
: подсчет <math>Q(a,b)</math> в качестве приближения значения интеграла на текущем отрезке интегрирования
: подсчет <math>\tilde{Q}(a,b)</math> для последующей оценки ошибки интегрирования <math>\tau</math>
: рекурсивное дробление текущего отрезка интегрирования на 2 подотрезка, если <math>\tau > \varepsilon </math>

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. Однако, в виде, описанном выше, данный алгоритм не может эффективно воспользоваться этой особенностью. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров, после чего, применить описанный алгоритм к каждому такому отрезку параллельно. Стоит отметить, что алгоритм сгущает сетку вокруг точек "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования. Таким образом, можно обеспечить равномерную нагрузку на все процессоры.

Из написанного выше и того факта, что алгоритм адаптивно дробит определенные отрезки на 2 части, можно сделать следующий вывод - максимальная производительность может быть достигнута, если количество процессоров <math>p \approx 2k</math>, где <math>k</math> - количество точек "малой гладкости". При дальнейшем увеличении количества процессоров скорость алгоритма будет лишь падать, так как результируещее количество подотрезков интегрирования, полученных в результате адаптивного дробления исходных отрезков, зависит в основном от <math>k</math>, следовательно, сложность вычислений останется неизменной, а накладные расходы лишь увеличатся.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 8
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 61.02 || 30.79 || 15.74 || 7.92 || 4.03 || 4.03 || 4.02 || 7.19
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Таким образом, отличная распараллеливаемость хорошо видна до тех пор, пока число процессов не превосходит количество "особых" точек в 2 раза. Это связано с тем фактом, что алгоритм сгущает сетку лишь около "особых" точек, дробя отрезки, содержащие их, на 2 подотрезка.
Очевидно, что дальнейшее увеличение числа процессоров никак не ускорит программу, а, скорее, наоборот, лишь замедлит ее из-за накладных расходов.

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T15:25:49Z

Valkyrie: /* Макроструктура алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции - вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.
Таким образом, на текущем отрезке интегрирования <math>[a,b]</math> выполняется следующая последовательность макроопераций:
: подсчет <math>Q(a,b)</math> в качестве приближения значения интеграла на текущем отрезке интегрирования
: подсчет <math>\tilde{Q}(a,b)</math> для последующей оценки ошибки интегрирования <math>\tau</math>
: рекурсивное дробление текущего отрезка интегрирования на 2 подотрезка, если <math>\tau > \varepsilon </math>

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 8
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 61.02 || 30.79 || 15.74 || 7.92 || 4.03 || 4.03 || 4.02 || 7.19
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Таким образом, отличная распараллеливаемость хорошо видна до тех пор, пока число процессов не превосходит количество "особых" точек в 2 раза. Это связано с тем фактом, что алгоритм сгущает сетку лишь около "особых" точек, дробя отрезки, содержащие их, на 2 подотрезка.
Очевидно, что дальнейшее увеличение числа процессоров никак не ускорит программу, а, скорее, наоборот, лишь замедлит ее из-за накладных расходов.

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T15:16:12Z

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции - вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 8
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 61.02 || 30.79 || 15.74 || 7.92 || 4.03 || 4.03 || 4.02 || 7.19
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Таким образом, отличная распараллеливаемость хорошо видна до тех пор, пока число процессов не превосходит количество "особых" точек в 2 раза. Это связано с тем фактом, что алгоритм сгущает сетку лишь около "особых" точек, дробя отрезки, содержащие их, на 2 подотрезка.
Очевидно, что дальнейшее увеличение числа процессоров никак не ускорит программу, а, скорее, наоборот, лишь замедлит ее из-за накладных расходов.

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T15:12:50Z

Valkyrie: /* Общее описание алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции - вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 8
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 61.02 || 30.79 || 15.74 || 7.92 || 4.03 || 4.03 || 4.02 || 7.19
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Таким образом, отличная распараллеливаемость хорошо видна до тех пор, пока число процессов не превосходит количество "особых" точек в 2 раза. Это связано с тем фактом, что алгоритм сгущает сетку лишь около "особых" точек, дробя отрезки, содержащие их, на 2 подотрезка.
Очевидно, что дальнейшее увеличение числа процессоров никак не ускорит программу, а, скорее, наоборот, лишь замедлит ее из-за накладных расходов.

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T15:10:14Z

Valkyrie: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 8
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 61.02 || 30.79 || 15.74 || 7.92 || 4.03 || 4.03 || 4.02 || 7.19
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Таким образом, отличная распараллеливаемость хорошо видна до тех пор, пока число процессов не превосходит количество "особых" точек в 2 раза. Это связано с тем фактом, что алгоритм сгущает сетку лишь около "особых" точек, дробя отрезки, содержащие их, на 2 подотрезка.
Очевидно, что дальнейшее увеличение числа процессоров никак не ускорит программу, а, скорее, наоборот, лишь замедлит ее из-за накладных расходов.

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-11T15:03:48Z

Valkyrie: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}
{| class="wikitable"
|+ k = 16
! Количество процессоров
! 1
! 2
! 4
! 8
! 16
! 32
! 64
! 128
|-
! Время, с
| 232.29 || 117.49 || 60.34 || 30.23 || 15.37 || 7.99 || 7.75 || 13.57
|}

Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. 
Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> 
Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. 

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:48:18Z

Valkyrie: /* Информационный граф */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:47:55Z

Valkyrie: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:46:50Z

Valkyrie: /* Ресурс параллелизма алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки.

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:46:20Z

Valkyrie: /* Существующие реализации алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:34:45Z

Valkyrie: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|800px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-12-01T01:34:25Z

Valkyrie: /* Масштабируемость алгоритма и его реализации */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета. В качестве интегрируемой области был выбран отрезок <math>[a,b] = [0,10]</math>, допустимая погрешность интегрирования составляла <math>\varepsilon = 10^{-6}</math>, а интегрируемой функцией была <math>f_k(x) = \sum\limits_{i = 0}^{k-1} (x - x_i) * sin(\frac{1}{x - x_i})</math>, где <math>x_i = a + \frac{b-a}{2k} + i * \frac{b-a}{k}</math>. В процессе тестирования менялось количество "особых" точек <math>k</math> и число процессоров <math>p</math>. Число процессоров выбиралось как <math>2^i</math>, <math>i = 0,1,..,7</math>; количество "особых" точек - <math>4,5,..20,25,30</math>. Ниже представлен график времени работы программы.

[[file:ValkyrieScalability.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T23:00:39Z

Valkyrie: /* Входные и выходные данные алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math>, и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T23:00:17Z

Valkyrie: /* Входные и выходные данные алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, заданной в виде формулы на отрезке <math>[a,b]</math> и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T22:58:57Z

Valkyrie: /* Входные и выходные данные алгоритма */

{{algorithm
| name = Адаптивное интегрирование
| serial_complexity =
| input_data =
| output_data =
}}

Автор: [[Участник:Valkyrie|В.А. Мастинен]]

== Свойства и структура алгоритма ==

=== Общее описание алгоритма ===

Адаптивное интегрирование - это метод численного интегрирования, в котором интеграл функции <math>f(x)</math> аппроксимируется с использованием статических [http://algowiki-project.org/ru/Квадратурные_формулы квадратурных формул ]<ref>Самарский А. А., Гулин А. В. Численные методы: Учеб. пособие для вузов. — М.: Наука. Гл. ред. физ-мат. лит., 1989. — 432 с.</ref> на адаптивно уточненных подынтервалах области интегрирования. Как правило, адаптивные алгоритмы столь же эффективны, как и традиционные алгоритмы для «достаточно гладких» подынтегральных функций, но также неэффективны для «плохих» подынтегральных функций, на которых традиционные алгоритмы терпят неудачу.

Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

=== Математическое описание алгоритма ===

Исходные данные : интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math>, допустимая погрешность интегрирования <math>\varepsilon</math>.

Вычисляемые данные : приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

Пусть <math>Q(a,b)</math> - квадратурная формула, аппроксимирующая значение интеграла на отрезке <math>[a,b]</math>.

Оценим <math>\tau \approx |Q(a,b) - \int\limits_a^b f(x)\,dx|</math>.

Если <math>\tau > \varepsilon</math>, поделим отрезок <math>[a,b]</math> пополам и применим этот же алгоритм к каждому из отрезков <math>[a,c]</math> и <math>[c,b]</math>, где <math> c = \frac{a+b}2 </math>, задав погрешность интегрирования на каждом из отрезков <math>\frac{\varepsilon}2</math>.

Если в качестве квадратурной формулы выбрать формулу Симпсона, то <math>\tau</math> можно положить равным <math>\frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math> (<ref> Lyness J. N. Notes on the adaptive Simpson quadrature routine //Journal of the ACM (JACM). – 1969. – Т. 16. – №. 3. – С. 483-495.</ref>).

Далее в качестве квадратурной формулы будет использоваться формула Симпсона.

=== Вычислительное ядро алгоритма ===

Основную часть алгоритма составляют вычисления квадратурной формулы, следовательно, и значений интегрируемой функций в трех точках, на каждом отрезке интегрирования. Так же на каждом отрезке подсчитывается ошибка интегрирования, которая представляет собой разность обычной квадратурной формулы <math>Q(a,b)</math> и уточненной <math>\tilde{Q}(a,b) = Q(a,c) + Q(c,b)</math>.

=== Макроструктура алгоритма ===

Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.

=== Описание схемы реализации последовательного алгоритма ===

Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{|Q(a,c) + Q(c,b) - Q(a,b)|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,c) + Q(c,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

=== Последовательная сложность алгоритма ===

Число операций, необходимых для вычисления приближенного значения интеграла, вообще говоря, зависит от допустимой погрешности интегрирования <math>\varepsilon</math> и от степени гладкости интегрируемой функции <math>f(x)</math>. Пусть алгоритм разбил <math>k</math> отрезков пополам, тогда в окончательном разбиении отрезка интегрирования получилось <math>k+1</math> отрезков. На каждом таком отрезке и на этапе разбиения приходится считать <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, то есть необходимо произвести вычисление значений <math>f(x)</math> в 5 точках, для подсчета каждой квадратуры необходимо выполнить 3 сложения, 1 вычитание, 1 умножение и 2 деления, а также 1 сложение, 1 вычитание и 1 деление для проверки критерия разбиения отрезка пополам и 1 деление при каждом разбиении отрезка. Таким образом, получается:
*<math>5(2k+1)</math> вычислений значения <math>f(x)</math> в некоторых точках
*<math>6(2k+1) </math> сложений и вычитаний
*<math>9k+4</math> делений и умножений

=== Информационный граф ===

На рисунке 1 приведена работа алгоритма при <math>\varepsilon = 4*10^{-6}</math>, <math>a = 0</math>, <math>b = 1</math> и <math>f(x) = \left\{ \begin{matrix} sin(\pi x) \text{ при } x \in [0, \frac{1}{2}] \text{,} \\ 1 - 4 (x - \frac{1}{2})^2 \text{ при } x \in [\frac{1}{2}, 1] \text{.}\end{matrix} \right. </math>

[[File:ValkyrieGraph.png|thumb|center|800px|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]

Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

=== Ресурс параллелизма алгоритма ===

Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий".

=== Входные и выходные данные алгоритма ===

На вход алгоритму подается интегрируемая функция <math>f(x)</math>, определенная на отрезке <math>[a,b]</math> и допустимая погрешность интегрирования <math>\varepsilon</math>. Результатом работы алгоритма является приближенное значение <math>Q</math> интеграла <math>\int\limits_a^b f(x)\,dx</math>.

=== Свойства алгоритма ===

== Программная реализация алгоритма ==

=== Особенности реализации последовательного алгоритма ===

=== Локальность данных и вычислений ===

=== Возможные способы и особенности параллельной реализации алгоритма ===

=== Масштабируемость алгоритма и его реализации ===

=== Динамические характеристики и эффективность реализации алгоритма ===

=== Выводы для классов архитектур ===

=== Существующие реализации алгоритма ===

== Литература ==

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T22:55:22Z

Valkyrie: /* Ресурс параллелизма алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T21:22:47Z

Valkyrie: /* Информационный граф */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T21:16:39Z

Valkyrie: /* Информационный граф */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T21:14:17Z

Valkyrie: /* Информационный граф */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T21:13:23Z

Valkyrie: /* Информационный граф */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T20:40:53Z

Valkyrie: /* Информационный граф */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T16:23:25Z

Valkyrie: /* Последовательная сложность алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T16:06:20Z

Valkyrie: /* Последовательная сложность алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T16:05:31Z

Valkyrie: /* Последовательная сложность алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T14:44:23Z

Valkyrie: /* Математическое описание алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-26T14:43:54Z

Valkyrie: /* Математическое описание алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:35:28Z

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:34:34Z

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:33:20Z

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:26:00Z

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:12:29Z

Valkyrie: /* Вычислительное ядро алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:09:15Z

Valkyrie: /* Вычислительное ядро алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T19:06:58Z

Valkyrie: /* Математическое описание алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T18:49:29Z

Valkyrie:

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T18:46:51Z

Valkyrie:

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T18:45:15Z

Valkyrie: /* Вычислительное ядро алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T18:41:21Z

Valkyrie: /* Макроструктура алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T16:59:29Z

Valkyrie: /* Вычислительное ядро алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T16:57:28Z

Valkyrie: /* Вычислительное ядро алгоритма */

Участник:Valkyrie/Адаптивное интегрирование

2017-11-25T16:52:52Z

Valkyrie: /* Математическое описание алгоритма */

Участник:Valkyrie

2017-10-22T20:04:14Z

Valkyrie: Полностью удалено содержимое страницы

Участник:Valkyrie/Адаптивное интегрирование

2017-10-22T20:03:31Z

Valkyrie: Новая страница: «{{algorithm | name = Адаптивное интегрирование | serial_complexity = | input_data = | output_data = }} Ав…»

Участник:Valkyrie

2017-10-22T20:01:58Z

Valkyrie: /* Общее описание алгоритма */

Участник:Valkyrie

2017-10-22T20:00:37Z

Valkyrie: /* Общее описание алгоритма */

Участник:Valkyrie

2017-10-22T19:57:41Z

Valkyrie: Новая страница: «{{algorithm | name = Адаптивное интегрирование | serial_complexity = | input_data = | output_data = }} Ав…»