Участник:Abogovski/Вспомогательная задача при решении задачи Штурма-Лиувилля с условиями сопряжения

Боговский Антон, 409

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

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

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

Искомые области находятся перебором параметров области (углы, на которых коэффицент постоянен, и значения коэффицента на этих подобластях.

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

Рассмотрим задачу Дирихле на ограниченной области для эллиптического уравнения в дивергентной форме с кусочно-постоянными коэффицентами. [math]div(\varkappa grad u) = div F [/math], где коэффицент [math]\varkappa[/math] -- кусочно-постоянный. При решении задачи методом разделения переменных в полярных возникает задача Штурма-Лиувилля относительного полярного угла [math]\Phi'(\varphi) = \lambda \Phi(\varphi)[/math] c условиями сопряжения на разрывах коэффицента: непрерывность [math]\Phi(\varphi)[/math] и [math]\varkappa(\varphi)\Phi'(\varphi)[/math].

В качестве области для модельной задачи возьмем круг (или сектор круга) с радиальными линиями разрыва [math]\varkappa(\varphi)[/math]. Тогда на каждом отрезке непрерывности [math]\varkappa(\varphi)[/math] решение -- линейная комбинация [math]cos(\sqrt{-\lambda}\varphi)[/math] и [math]sin(\sqrt{-\lambda}\varphi)[/math]. Если для области такого вида (набора значений [math]\varkappa[/math] и величин углов) существуют набор постоянных при [math]cos(\sqrt{-\lambda}\varphi)[/math] и [math]sin(\sqrt{-\lambda}\varphi)[/math], такой что граничные условия и условия сопряжения выполнены, то существует собственная функция.

Ищем такие области. Заметим, что решения задачи штурма Лиувилля зависят от [math]\alpha = \sqrt{-\lambda}\varphi[/math] -- перейдем к такой переменной. Зададим граничное условие на одной стороне сектора, условия сопряжения на линиях разрыва и проверим (переберем) различные значения [math]\alpha, \varkappa[/math] на выполнение граничного условия на правой стороне.

(Условия сопряжения дают связь между коэффицентами при [math]cos,sin[/math] через композицию матриц растяжения и поворота, зависящих от [math]\alpha, \varkappa[/math]).

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

Перебор параметров. Можно рассматривать вычислительное как обход дерева всех наборов значений параметров.

• Для первой подобласти фиксируется значение [math]\varkappa=1[/math] и поддиапазон перебора значений [math]\alpha[/math]
• Остальные значения перебираются в заданном диапазоне -- обход дерева всех наборов значений параметра (при заданном шаге по значениям).

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

• Для каждого процесса из его номера вычисляется поддерево наборов значений для обхода.
• Каждым из процессов выполняется обход своего поддерева
• 0-ой процесс, закончив обход своего поддерева, собирает все результаты и сохраняет их в файл с уникальным именем

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

В первой подобласти: зафиксируем [math]\varkappa=1[/math] Далее перебор значений остальных параметров.

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

• n - число областей непрерывности [math]\varkappa[/math]
• k - число пробных значений в диапазоне перебора

сложноть последовательной реализации -- [math]O(k^{2n})[/math]

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

Вычислительное ядро -- "паралелельные" независимые ветви.

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

Так как структура алгоритма представляет собой дерево (с большим количеством потомков в каждом узле) -- алгоритм хорошо распараллеливается. Наблюдается линейная масштабируемость. Сбор и сохранение данных в конце почти не влиют на производительность.

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

Параметрами задачи являются: число областей непрерывности, диапазон и точность перебора [math]\varkappa, \alpha[/math], требуемая точность выполнения граничного условия. Выходные данные: наборы [math]\varkappa, \alpha[/math] -- с их помощью можно построить искомые области.

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

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

Ключевым ограничением масштабируемости является сбор результатов одним процессом.

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

• Алгоритм имеет линейную масштабируемость на любой системе, где сохранение данных не займет существенную часть времени. (вычислительные ядра не взаимодействуют)
• Алгоритм не учитывает возможность оптимизации с помощью векторизации.