Уровень алгоритма

Участник:Rpu6/Алгоритм построения приближённого решения нерегулярно вырождающегося эллиптического дифференциального уравнения: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
 +
{{algorithm
 +
| name              = Алгоритм построения приближённого решения нерегулярно вырождающегося эллиптического дифференциального уравнения
 +
| serial_complexity = <math>O(KN\mathrm{max}(K, N))</math>
 +
| pf_height        = <math>?</math>
 +
| pf_width          = <math>?</math>
 +
| input_data        = <math>KN + 2N</math>
 +
| output_data      = <math>KN</math>
 +
}}
 +
 
Автор описания: [[Участник:Rpu6|Д. П. Емельянов]].
 
Автор описания: [[Участник:Rpu6|Д. П. Емельянов]].
  
Строка 19: Строка 28:
 
1. Приблизим функцию <math>f(x,y)</math> конечными суммами ряда Фурье по <math>x</math>:
 
1. Приблизим функцию <math>f(x,y)</math> конечными суммами ряда Фурье по <math>x</math>:
 
:<math>f(x,y)=\sum_{k=1}^{K}f_k(y)\sin \pi kx.</math>
 
:<math>f(x,y)=\sum_{k=1}^{K}f_k(y)\sin \pi kx.</math>
:<math>f_k(y)=4\int\limits_0^1f(x,y)\sin \pi kx\,dx.</math>
+
:<math>f_k(y)=2\int\limits_0^1f(x,y)\sin \pi kx\,dx.</math>
 
Для интеграла следует использовать квадратурную формулу.
 
Для интеграла следует использовать квадратурную формулу.
  
Строка 37: Строка 46:
 
\sum_{l=1}^{n}a_l\eta_{k,n-l}}{n(n-1)+nc_1-\pi^2k^2-a_0},n = \overline{1,N},\\
 
\sum_{l=1}^{n}a_l\eta_{k,n-l}}{n(n-1)+nc_1-\pi^2k^2-a_0},n = \overline{1,N},\\
 
\varphi_{kn}=\frac{
 
\varphi_{kn}=\frac{
\sum_{l=1}^na_l\varphi_{k,n-1}-
+
\sum_{l=1}^na_l\varphi_{k,n-l}-
 
\sum_{l=2}^{n+1}(n-l+1+r_k)c_l\varphi_{k,n-l+1}
 
\sum_{l=2}^{n+1}(n-l+1+r_k)c_l\varphi_{k,n-l+1}
 
}{n(n-1)+2nr_k+nc_1}
 
}{n(n-1)+2nr_k+nc_1}
Строка 50: Строка 59:
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
 +
 +
Алгоритм решения задачи можно разделить на три крупные части примерно одинаковой вычислительной сложности:<br>
 +
1. Разложение заданной функции <math>f(x,y)</math> в ряд Фурье, разложение её коэффициентов Фурье в ряды Тейлора, разложение заданных функций <math>a(y), c(y)</math> в ряды Тейлора.
 +
На этом этапе известные сеточные функции скалярно умножаются на тригонометрические функции или полиномы Лежандра. В первом случае коэффициент является скалярным произведением,
 +
во втором - линейной комбинацией соответствующих коэффициентов полиномов Лежандра, помноженных на отвечающие данному полиному скалярные произведения.<br>
 +
2. Построение коэффициентов ряда Тейлора для функций <math>\eta_k(y), \varphi_k(y)</math> с последующим построением самих функций.
 +
Используются формулы этапа 4 пункта 1.2.<br>
 +
3. По построенным функциям <math>\eta_k(y), \varphi_k(y)</math> строится решение задачи <math>u(x,y)</math> (формула этапа 5 пункта 1.2).
 +
 
== Макроструктура алгоритма ==
 
== Макроструктура алгоритма ==
 +
 +
Макроструктура этого алгоритма фактически совпадает с его вычислительным ядром (см. пункт 1.3).
 +
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
 +
 +
Алгоритм принимает на вход сеточные функции <math>f(x_i, y_j), a(y_j), c(y_j); x_i = \frac{i}{K}, y_j = \frac{j}{N}; i = \overline{0,K-1}, j=\overline{0,N-1}</math>.
 +
:<math>
 +
f_k(y_j) = \frac{2}{K}\sum_{l=1}^K f(x_l, y_j) sin (\pi kx_l), k=\overline{1,K},\\
 +
f_{kn} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} f_k(y_l) L_m(y_l), n=\overline{0,N-1},\\
 +
a_{n} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} a(y_l) L_m(y_l),\\
 +
c_{n} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} c(y_l) L_m(y_l).
 +
</math>
 +
Тут <math>\mathrm{coeff}_n</math> - коэффициент при n-й степени y в полиноме-аргументе (подразумевается, что алгоритм их знает), <math>L_m</math> - нормированный полином Лежандра степени m.<br>
 +
Формулы для вычислений на других шагах алгоритма изложены в пункте 1.2. Достаточно заметить, что при все функции вычисляются в узлах заданной сетки, суммирование можно вести, запоминая <math>y^{n-1}</math>
 +
с предыдущего шага, вычисляется лишь <math>y^{n-1}y</math>.
 +
 
== Последовательная сложность алгоритма ==
 
== Последовательная сложность алгоритма ==
 +
 +
Будем оценивать количество операций умножения вещественных чисел. Произведём оценку отдельно для каждого шага алгоритма.<br>
 +
1. <math>(K + 1)N</math> умножение для вычисления <math>f_k(y_j)</math> (N возникает в силу необходимости вычислять функцию в каждой точке сетки по y),
 +
<math>((N + 1)N + 1)K</math> операций для вычисления <math>f_{kn}</math> (считаем, что значения гармоник и полиномов Лежандра известны заранее),
 +
<math>2((N + 1)N + 1)</math> операций для вычисления <math>a_n, c_n</math>.
 +
2. Для вычисления n-го коэффициента требуется <math>5 + 3(n-1)</math> операций, для вычисления всех коэффициентов -
 +
<math>\sum_{n=1}^{N-1} (5 + 3(n-1))=5(N-1) + 3\frac{N-2}{2}(N-1)=(N-1)(5 + 1,5 (N-2))</math>, суммирование <math>\stackrel{\circ}{\varphi}_k(b)</math> требует <math>2N</math> операций,
 +
коррекция <math>\varphi_k(y_j)</math> требует <math>N + 2</math> операции, построение самих функций - <math>N(2N)=2N^2</math> операций. Это всё нужно проделать <math>K</math> раз.<br>
 +
3. Вычисление значения функции в узле сетки стоит <math>3K</math> операций умножения. Это нужно проделать в <math>KN</math> узлах.<br>
 +
Выделим главный член асимптотики по всем шагам: <math>KN^2 + 3,5KN^2 + 3K^2N=O(KN\mathrm{max}(K,N)).</math><br>
 +
Если положить <math>K=N</math>, то сложность алгоритма имеет порядок <math>O(N^3)</math>.
 +
 
== Информационный граф ==
 
== Информационный граф ==
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==

Версия 01:08, 15 ноября 2017


Алгоритм построения приближённого решения нерегулярно вырождающегося эллиптического дифференциального уравнения
Последовательный алгоритм
Последовательная сложность [math]O(KN\mathrm{max}(K, N))[/math]
Объём входных данных [math]KN + 2N[/math]
Объём выходных данных [math]KN[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы [math]?[/math]
Ширина ярусно-параллельной формы [math]?[/math]


Автор описания: Д. П. Емельянов.

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

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

Алгоритм позволяет построить приближения к точному решению эллиптического дифференциального уравнения с нерегулярным вырождением и аналитическими коэффициентами в прямоугольнике. Точные формулы решения уравнения и их строгое обоснование получены с использованием метода спектрального выделения особенностей[1]. Решение строится в виде ряда. Погрешность алгоритма заключается в замене рядов на конечные суммы.

Алгоритм решает следующую задачу:

[math] \begin{cases} y^2u''_{yy}+u''_{xx}+c(y)u'_y-a(y)u=f(x,y),(x,y)\in(0,1)\times(0,b), \\ u(0,y)=u(1,y)=u(x,b)=0,|u(x,0)|\lt +\infty. \end{cases}[/math]

Функции [math]a(y), c(y)[/math] полагаем аналитическими в круге [math]|y|\lt R[/math], где [math]R\gt b[/math]. Кроме того, [math]c(y), a(y) \ge 0[/math] в [math][0,b][/math], [math]c(0)=0[/math].

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

1. Приблизим функцию [math]f(x,y)[/math] конечными суммами ряда Фурье по [math]x[/math]:

[math]f(x,y)=\sum_{k=1}^{K}f_k(y)\sin \pi kx.[/math]
[math]f_k(y)=2\int\limits_0^1f(x,y)\sin \pi kx\,dx.[/math]

Для интеграла следует использовать квадратурную формулу.

2. Приблизим функции [math]f_k(y),a(y),c(y)[/math] полиномами:

[math]a(y)=\sum_{n=0}^{N}a_ny^n, c(y)=\sum_{n=1}^{N}c_ny^n, f_k(y)=\sum_{n=0}^{N}f_{kn}y^n.[/math]

Разложение можно проводить по аналогии с разложением в ряд Фурье, но с использованием полиномов Лежандра.

3. Введём в рассмотрение числа:

[math]\lambda_k=\pi^2k^2+a_0, k = \overline{1,K},[/math]
[math]r_k=\frac{1-c_1 + \sqrt{(c_1-1)^2+4\lambda_k}}{2}, k = \overline{1,K}.[/math]

4. Построим функции [math]\eta_k(y),\varphi_k(y)[/math], они будут использованы при построении приближения к решению:

[math]\eta_k(y)=\sum_{n=0}^{N}\eta_{kn}y^n, \stackrel{\circ}{\varphi}_k(y)=\sum_{n=0}^{N}\varphi_{kn}y^n,[/math]
[math]\begin{matrix} \eta_{kn}=\frac{f_{kn}-\sum_{l=2}^{n+1}c_l(n+1-l)\eta_{k,n+1-l}+ \sum_{l=1}^{n}a_l\eta_{k,n-l}}{n(n-1)+nc_1-\pi^2k^2-a_0},n = \overline{1,N},\\ \varphi_{kn}=\frac{ \sum_{l=1}^na_l\varphi_{k,n-l}- \sum_{l=2}^{n+1}(n-l+1+r_k)c_l\varphi_{k,n-l+1} }{n(n-1)+2nr_k+nc_1} ,n= \overline{1,N},\\ \eta_{k,0}=\frac{f_{k,0}}{-\pi^2k^2-a_0}, \varphi_{k,0}=1, \varphi_k(y)=-\frac{\eta_k(b)}{\stackrel{\circ}{\varphi}_k(b)}\stackrel{\circ}{\varphi}_k(y). \end{matrix}[/math]

5. Построим приближение к решению:

[math]u(x,y)=\sum_{k=1}^{K}\left(\left(\frac{y}{b}\right)^{r_k}\varphi_k(y)+\eta_k(y)\right)\sin \pi kx.[/math]

За счёт выбора [math]K[/math] и [math]N[/math] можно добиться той или иной точности.

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

Алгоритм решения задачи можно разделить на три крупные части примерно одинаковой вычислительной сложности:
1. Разложение заданной функции [math]f(x,y)[/math] в ряд Фурье, разложение её коэффициентов Фурье в ряды Тейлора, разложение заданных функций [math]a(y), c(y)[/math] в ряды Тейлора. На этом этапе известные сеточные функции скалярно умножаются на тригонометрические функции или полиномы Лежандра. В первом случае коэффициент является скалярным произведением, во втором - линейной комбинацией соответствующих коэффициентов полиномов Лежандра, помноженных на отвечающие данному полиному скалярные произведения.
2. Построение коэффициентов ряда Тейлора для функций [math]\eta_k(y), \varphi_k(y)[/math] с последующим построением самих функций. Используются формулы этапа 4 пункта 1.2.
3. По построенным функциям [math]\eta_k(y), \varphi_k(y)[/math] строится решение задачи [math]u(x,y)[/math] (формула этапа 5 пункта 1.2).

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

Макроструктура этого алгоритма фактически совпадает с его вычислительным ядром (см. пункт 1.3).

1.5 Схема реализации последовательного алгоритма

Алгоритм принимает на вход сеточные функции [math]f(x_i, y_j), a(y_j), c(y_j); x_i = \frac{i}{K}, y_j = \frac{j}{N}; i = \overline{0,K-1}, j=\overline{0,N-1}[/math].

[math] f_k(y_j) = \frac{2}{K}\sum_{l=1}^K f(x_l, y_j) sin (\pi kx_l), k=\overline{1,K},\\ f_{kn} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} f_k(y_l) L_m(y_l), n=\overline{0,N-1},\\ a_{n} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} a(y_l) L_m(y_l),\\ c_{n} = \sum_{m=0}^{N-1} (\mathrm{coeff}_n L_m) \frac{2}{N} \sum_{l=0}^{N-1} c(y_l) L_m(y_l). [/math]

Тут [math]\mathrm{coeff}_n[/math] - коэффициент при n-й степени y в полиноме-аргументе (подразумевается, что алгоритм их знает), [math]L_m[/math] - нормированный полином Лежандра степени m.
Формулы для вычислений на других шагах алгоритма изложены в пункте 1.2. Достаточно заметить, что при все функции вычисляются в узлах заданной сетки, суммирование можно вести, запоминая [math]y^{n-1}[/math] с предыдущего шага, вычисляется лишь [math]y^{n-1}y[/math].

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

Будем оценивать количество операций умножения вещественных чисел. Произведём оценку отдельно для каждого шага алгоритма.
1. [math](K + 1)N[/math] умножение для вычисления [math]f_k(y_j)[/math] (N возникает в силу необходимости вычислять функцию в каждой точке сетки по y), [math]((N + 1)N + 1)K[/math] операций для вычисления [math]f_{kn}[/math] (считаем, что значения гармоник и полиномов Лежандра известны заранее), [math]2((N + 1)N + 1)[/math] операций для вычисления [math]a_n, c_n[/math]. 2. Для вычисления n-го коэффициента требуется [math]5 + 3(n-1)[/math] операций, для вычисления всех коэффициентов - [math]\sum_{n=1}^{N-1} (5 + 3(n-1))=5(N-1) + 3\frac{N-2}{2}(N-1)=(N-1)(5 + 1,5 (N-2))[/math], суммирование [math]\stackrel{\circ}{\varphi}_k(b)[/math] требует [math]2N[/math] операций, коррекция [math]\varphi_k(y_j)[/math] требует [math]N + 2[/math] операции, построение самих функций - [math]N(2N)=2N^2[/math] операций. Это всё нужно проделать [math]K[/math] раз.
3. Вычисление значения функции в узле сетки стоит [math]3K[/math] операций умножения. Это нужно проделать в [math]KN[/math] узлах.
Выделим главный член асимптотики по всем шагам: [math]KN^2 + 3,5KN^2 + 3K^2N=O(KN\mathrm{max}(K,N)).[/math]
Если положить [math]K=N[/math], то сложность алгоритма имеет порядок [math]O(N^3)[/math].

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

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

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

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

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

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

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

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

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

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

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

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

3 Литература

<references \>

  1. Ломов С. А., Ломов И. С. Основы математической теории пограничного слоя. М.: Издательство Московского университета, 2011. – 456 с.