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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-02-04T13:11:37Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

Вариант реализации параллельного алгоритма представлен ниже.
<source lang="с++">
sem_t semGlobalSum, semGlobalStack, semTaskPresent;

int numberOfActiveProcs = 0;
unsigned int maxGSelements = 10, maxLSelements = 5;
double integral = 0;
stack<SumRecord> globalStack;

void *JLS_thr(void *processNumber) {
stack<SumRecord> localStack;
double J = 0;
int pN = *((int*)(&processNumber));

while (1) {
sem_wait(&semTaskPresent);
sem_wait(&semGlobalStack);

SumRecord tmpRecordAB = globalStack.top();
double A = tmpRecordAB.A;
double fA = tmpRecordAB.fA;
double B = tmpRecordAB.B;
double fB = tmpRecordAB.fB;
double sAB = tmpRecordAB.s;
globalStack.pop();

if (!globalStack.empty())
sem_post(&semTaskPresent);
if (A <= B)
numberOfActiveProcs++;
sem_post(&semGlobalStack);
if (A > B) break;

while (1) {
double C = (A + B) / 2;
double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2;
double sCB = (fC + fB) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) < eps * abs(sACB)) {
J += sACB;

if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
} else {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
}

if ((localStack.size() > maxLSelements) &&
(globalStack.empty())) {
sem_wait(&semGlobalStack);
if (globalStack.empty()) {
sem_post(&semTaskPresent);
}
while ((localStack.size() > 1)
&& (globalStack.size() < maxGSelements)) {
SumRecord tmpRecord = localStack.top();
localStack.pop();
globalStack.push(tmpRecord);
}
sem_post(&semGlobalStack);
}
}

sem_wait(&semGlobalStack);
numberOfActiveProcs--;
if ((!numberOfActiveProcs) && (globalStack.empty())) {
for (int i = 0; i < nproc; i++) {
SumRecord terminalRecord = { 2, 1, 0 };
globalStack.push(terminalRecord);
}
sem_post(&semTaskPresent);
}
sem_post(&semGlobalStack);
}

sem_wait(&semGlobalSum);
integral += J;
sem_post(&semGlobalSum);
return 0;
}

pthread_t *thread;

typedef void *ThrSub(void *);

void StartThrTask(int NumberOfProcs, ThrSub *thrFunc) {
thread = (pthread_t *) malloc(NumberOfProcs * sizeof(pthread_t));

for (int i = 0; i < NumberOfProcs; i++)
pthread_create(&(thread[i]), NULL, thrFunc, (void *) i);
#ifdef HAVE_THR_SETCONCURRENCY_PROTO
int thr_setconcurrency(int);
thr_setconcurrency(NumberOfProcs);
#endif
}

void WaitThrTask(int NumberOfProcs) {
for (int i = 0; i < NumberOfProcs; i++)
pthread_join(thread[i], NULL);
}

int main() {
double A = 10e-5, B = 1;

sem_init(&semGlobalSum, 0, 1);
sem_init(&semGlobalStack, 0, 1);
sem_init(&semTaskPresent, 0, 0);
double fA = f(A);
double fB = f(B);
SumRecord tmpRecordAB = { A, fA, B, fB, (fA + fB) * (B - A) / 2. };
globalStack.push(tmpRecordAB);
sem_post(&semTaskPresent);
StartThrTask(nproc, JLS_thr);
WaitThrTask(nproc);
return 0;
}
</source>

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T11:59:33Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double fA;
double B;
double fB;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
SumRecord tmpRecordAB;

double J = 0;
double fA = f(A);
double fB = f(B);
double sAB = (fA + fB) * (B - A) / 2.;
while (1) {
double C = (A + B) / 2.;

double fC = f(C);
double sAC = (fA + fC) * (C - A) / 2.;
double sCB = (fC + fB) * (B - C) / 2.;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, fA, C, fC, sAC };
localStack.push(tmpRecordAC);
A = C;
fA=fC;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
fA = tmpRecordAB.fA;
B = tmpRecordAB.B;
fB = tmpRecordAB.fB;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T10:58:21Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Алгоритм итерационный. Сначала значение текущего отрезка равно общему отрезку интегрирования. На каждой итерации выполняются следующие действия: 
- На текущем отрезке считается приближенное значение интеграла 
- Текущий отрезок делится пополам, и на получившихся отрезках высчитываются интегралы 
- Сравнивается интеграл на всём отрезке с суммой двух интегралов на половинах. Если достигнута заданная точность, то: 
# Добавить значение интеграла текущего отрезка к общему интегралу 
# Если стек пуст, то завершить алгоритм 
# Иначе достать из стека отрезок и присвоить его значение текущему отрезку. 

- Иначе 
# Одну половину отрезка положить в стек 
# Текущему отрезку присвоить значение второй половины 

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double B;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
double J = 0;
double sAB = (f(A) + f(B)) * (B - A) / 2;
SumRecord tmpRecordAB;
while (1) {
double C = (A + B) / 2;
double sAC = (f(A) + f(C)) * (C - A) / 2;
double sCB = (f(C) + f(B)) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, C, sAC };
localStack.push(tmpRecordAC);
A = C;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
B = tmpRecordAB.B;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T10:49:20Z

Greno4ka:

Авторы: [[User:Greno4ka|Устинов Г.А.]](п. 1.6-1.10, 2.4, 2.7) [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]](п. 1.1-1.6)

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double B;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
double J = 0;
double sAB = (f(A) + f(B)) * (B - A) / 2;
SumRecord tmpRecordAB;
while (1) {
double C = (A + B) / 2;
double sAC = (f(A) + f(C)) * (C - A) / 2;
double sCB = (f(C) + f(B)) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, C, sAC };
localStack.push(tmpRecordAC);
A = C;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
B = tmpRecordAB.B;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T10:44:41Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
<source lang="с++">
struct SumRecord {
double A;
double B;
double s;
};

double JLS(double A, double B) {
stack<SumRecord> localStack;
double J = 0;
double sAB = (f(A) + f(B)) * (B - A) / 2;
SumRecord tmpRecordAB;
while (1) {
double C = (A + B) / 2;
double sAC = (f(A) + f(C)) * (C - A) / 2;
double sCB = (f(C) + f(B)) * (B - C) / 2;
double sACB = sAC + sCB;
if (abs(sAB - sACB) >= eps * abs(sACB)) {
SumRecord tmpRecordAC = { A, C, sAC };
localStack.push(tmpRecordAC);
A = C;
sAB = sCB;
} else {
J += sACB;
if (localStack.empty())
break;
else {
tmpRecordAB = localStack.top();
A = tmpRecordAB.A;
B = tmpRecordAB.B;
sAB = tmpRecordAB.s;
localStack.pop();
}
}
}
return J;
}
</source>

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T03:19:56Z

Greno4ka: /* Свойства алгоритма */

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе. 
3. Алгоритм является детерминированным, поскольку при одинаковых входных данных получается одинаковый результат.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:48:14Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В.<ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:47:55Z

Greno4ka: /* ЧАСТЬ. Литература */

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В. в <ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:47:42Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В. в <ref>Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.</ref>

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:40:37Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB] 
Есть реализация с использованием OpenMP от университета [https://doc.itc.rwth-aachen.de/display/CCP/Parallelizing+an+Algorithm+for+Adaptive+Integration+with+OpenMP RWTH AACHEN UNIVERSITY] 
Кроме того, схема реализации алгоритма представлена Якобовским М. В. в [[1]]

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Обсуждение участника:Greno4ka

2017-01-21T02:32:54Z

Greno4ka: /* Пункт 1.3 */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5
* Не указан вклад каждого автора
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма. (сделано)

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека.

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

Обсуждение участника:Greno4ka

2017-01-21T02:32:34Z

Greno4ka: /* Статья Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки */

--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK) Работа не готова. Нет разделов 1.3, 1.4, 1.6-1.8, 1.10, 2.4; нет описания параллельного алгоритма и исследования масштабируемости. Есть несколько замечаний (ниже с моей подписью) к тому, что уже написано, помимо выполнения основных требований к работе

== Статья [[Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки]] ==

* Нет краткой сводки свойств алгоритма в начале страницы
* В разделе 1.1 по сути нет описания алгоритма (сделано)
* Разделы 1.6-1.8 пусты (сделано)
* В разделах 1.3 и 1.4 хотелось бы видеть понятное словесное описание
* Содержимое раздела 1.4 должно быть внесено в раздел 1.5
* Не указан вклад каждого автора
* Не заполнен раздел 2.4 описания. [[Участник:ASA|Александр Сергеевич Антонов]] ([[Обсуждение участника:ASA|обсуждение]]) 15:59, 16 ноября 2016 (MSK)

== Пункт 1.2 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''в некоторых точках значение функции будет вычисляться несколько раз'''

В каких точках в формуле для приближенного вычисления интеграла функция вычисляется несколько раз? В чем проблема сохранять рассчитанные значения функции и использовать их далее без перерасчета?

== Пункт 1.3 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

В этом разделе нужно явно описать вычислительное ядро алгоритма.

== Пункт 1.4 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Вместо макроструктуры алгоритма здесь приведена реализация структуры данных для стека.

== Пункт 1.5 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

'''if (|sAB - sACB| ≥ ε|sACB|) {'''

Не отличается ли здесь условие на деление отрезка от того, что приведено в пункте 1.2?

== Пункт 1.9 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Как задается входная функция в алгоритме и реализации?
Нужно указать размер входных-выходных данных.

== Пункт 1.10 ==
--[[Участник:Evgeny Mortikov|Evgeny Mortikov]] ([[Обсуждение участника:Evgeny Mortikov|обсуждение]]) 05:18, 3 декабря 2016 (MSK)

Есть ли у алгоритма другие свойства, помимо того, что он адаптируется под заданную функцию?

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:31:13Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]] 
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:30:47Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки примечательно тем, что на разных участках интервала интегрирования количество узлов сетки зависит от необходимой точности. Вычисление на равномерной сетке неэффективно, поскольку предполагает равномерное сгущение сетки на всем отрезке интегрирования, без учета характера изменения подынтегральной функции.
[[Файл:Ustinov fx.png]]
В данном алгоритме используется адаптивное разбиение участка интегрирования: размер конкретного отрезка определяется во время подсчета значения функции на нем самом. Если заданная точность не была достигнута на данном отрезке, он рекурсивно разбивается на несколько новых и функция подсчитывается уже на них. Таким образом, выигрыш от применения рассмотренного алгоритма рекурсивного разбиения достигается за счет возможности использования сеток с разным числом узлов на разных участках интервала интегрирования. Как правило это бывает очень полезно при расчёте интегралов функций, содержащих области с высокими градиентами.

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:11:05Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции: 
- нахождение середины отрезка и значения функции в этой точке; 
- вычисление частичных сумм на половинах отрезка; 
- работа со стеком. 

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:10:46Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему. То есть основное время работы алгоритма приходится на следующие операции:
- нахождение середины отрезка и значения функции в этой точке;
- вычисление частичных сумм на половинах отрезка;
- работа со стеком.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-21T02:03:24Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

Оценить аналитически последовательную сложность представленного алгоритма невозможно, поскольку нельзя указать количество разбиений отрезка интегрирования для каждой отдельно взятой функции, оно зависит от свойств конкретно взятой функции.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T23:39:17Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T23:35:32Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма. 
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T23:35:12Z

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

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

В последовательной версии алгоритма используется только локальный стек, в который помещаются отрезки, перед очередным этапом деления отрезка. Таким алгоритм чем-то похож на алгоритм рекурсивного деления, только без прямого использования рекурсии. Отрезок делится до тех пор, пока не будет достигнута необходимая точность, вторая половина отрезка будет помещаться в локальный стек на каждом этапе деления. После достижения нужной точности, первым будет исследован последний добавленный отрезок, то есть соответствующий второй половине отрезка, разделённого на предыдущем этапе. Следующий рисунок содержит блок-схему данного алгоритма.
[[Файл:Ustinov localgraph.png]]

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

[[Файл:Ustinov infograph.png]]

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции. 
2. В параллельной версии алгоритма на основе не требуется управляющий процесс. Распределение отрезков и финальное сложение можно провести на нулевом процессе.

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T23:21:53Z

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T22:46:32Z

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T22:31:07Z

Greno4ka: /* Свойства алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T22:30:38Z

Greno4ka: /* Свойства алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T20:54:30Z

Greno4ka: /* Свойства алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T20:53:38Z

Greno4ka: /* Свойства алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2017-01-20T20:53:11Z

Greno4ka: /* Свойства алгоритма */

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T23:34:45Z

Greno4ka:

{{Assignment}}

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев_Данир_Владимирович|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Существует реализация в библиотеке [http://alglib.sources.ru/integration/adaptive.php ALGLIB].

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T22:07:03Z

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

Участник:Greno4ka

2016-10-15T21:26:58Z

Greno4ka: Новая страница: «Устинов Григорий Андреевич, группа 604.»

Устинов Григорий Андреевич, группа 604.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:26:22Z

Greno4ka:

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:24:13Z

Greno4ka:

Авторы: [[User:Greno4ka|Устинов Г.А.]] [[User:Лиджиев Д.В.|Лиджиев Д.В.]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:21:35Z

Greno4ka:

Авторы: [[User:Greno4ka|Greno4ka]] [[User:John Doe|John Doe]]

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:05:50Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

Ниже будет показано, что вычислительное ядро алгоритма состоит из основного цикла алгоритма и сложность зависит от количества проходов по нему.

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

= ЧАСТЬ. Литература =

Якобовский М.В., Кулькова Е.Ю. Решение задач на многопроцессорных вычислительных системах с разделяемой памятью. - М.: СТАНКИН, 2004. – 30 c.

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T21:01:16Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

.

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:53:19Z

Greno4ka: /* Свойства алгоритма */

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

1. Алгоритм адаптируется под конкретные особенности заданной функции

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:43:37Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования <math>a</math>, <math>b</math>.

Выходные данные:
* число <math>I</math>, равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:42:45Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

Входные данные:
* функция <math>y = f(x)</math>;
* точность <math>\epsilon</math>;
* границы отрезка интегрирования a, b.

Выходные данные:
* число I , равное <math>\int_a^b{f(x)dx}</math> с точностью <math>\epsilon</math>.

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:42:18Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз;
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

Входные данные:
* функция y = f(x);
* точность \epsilon;
* границы отрезка интегрирования a, b.

Выходные данные:
* число I , равное \int_a^b{f(x)dx} с точностью \epsilon.

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:41:42Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз.
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

Входные данные:
* функция y = f(x);
* точность \epsilon;
* границы отрезка интегрирования a, b.

Выходные данные:
* число I , равное \int_a^b{f(x)dx} с точностью \epsilon.

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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

Участник:Greno4ka/Вычисление определенного интеграла с использованием адаптивно сгущающейся сетки

2016-10-15T20:36:24Z

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

= ЧАСТЬ. Свойства и структура алгоритмов =

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

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

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

В качестве модельной задачи рассматривается проблема вычисления с точностью ε значение определенного интеграла:

<math>I(a,b) = \int_a^b{f(x)dx}</math>

Пусть на отрезке <math> [a,b] </math> задана равномерная сетка, содержащая <math> n+1 </math> узел:

<math> x_{i} = a + \frac{(b - a)} {n} i, i = 0,...,n </math>

Тогда, согласно методу трапеций, можно численно найти определенный интеграл от функции <math> f (x) </math> на отрезке <math>[a,b]</math>:

<math> \int_a^b{f(x)dx} = \frac{b - a}{n} \left( \frac{f(x_0)}{2} + \sum^{n-1}_{i=1} {f(x_i)} + \frac{f(x_n)}{2} \right)</math>

Будем полагать значение I найденным с точностью ε, если выполнено условие

<math> |I_{n_1} - I_{n_2}| \leq \epsilon |I_{n_2}|, n_1 > n_2, </math>
где <math> n_1 </math> и <math> n_2 </math> - количество узлов, образующих две разные сетки.

Данный метод неэффективен в силу ряда причин:
* в некоторых точках значение функции будет вычисляться несколько раз.
* на всём интервале интегрирования используется равномерная сетка, тогда как число точек, необходимых для достижения заданной точности, зависит от вида функции и может сильно различаться на разных участках сегмента интегрирования.

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

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

Метод локального стека
sp=0 // указатель вершины стека
struct {
A, B, fA, fB, s
} stk[1000]

// макроопределения доступа к данным стека

#define STACK_IS_NOT_FREE (sp>0)

#define PUT_INTO_STACK(A, B, fA, fB, s)
{
stk[sp].A=A
stk[sp].B=B
stk[sp].fA=fA
stk[sp].fB=fB
stk[sp].s=s
sp++
}

#define GET_FROM_STACK(A, B, fA, fB, s)
{
sp--
A=stk[sp].A
B=stk[sp].B
fA=stk[sp].fA
fB=stk[sp].fB
s=stk[sp].s
}

== Схема реализации последовательного алгоритма ==
IntTrap (A, B)
{
J=0
fA = f(A)
fB = f(B)
sAB = (fA + fB) * (B - A) / 2
while (1)
{
C = (A + B) / 2
fc = fun(C)
sAC = (fA + fC) * (C - A) / 2
sCB = (fC + fB ) * (B-C)/2
sACB = sAC + sCB
if (|sAB - sACB| ≥ ε|sACB|) {
PUT_INTO_STACK(A, C, fA, fC, sAC)
A = C
fA = fC
sAB = sCB
} else {
J += sACB
if (STACK_IS_NOT_FREE)
break
GET_FROM_STACK(A, B, fA, fB, sAB)
}
}
return J
}

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

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

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

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

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

= ЧАСТЬ. Программная реализация алгоритма =

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

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

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

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

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

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

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