Интегрирование функций по выпуклым областям решетчатыми кубатурными формулами на многопроцессорных вычислительных системах

§ 1. Основные положения диссертации.

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

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

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

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

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

Вот почему так важно квалифицированное отображение математических достижений в «механическую» плоскость.

Объектом исследования данной диссертации является приближенное интегрирование функций по многомерным областям (УДК 519.644 + 517.518.87).

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

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

Кубатурной формулой (КФ) назовем линейный функционал, задающий приближенное значение интеграла /п (/) — f dxf (x) в виде лип нейной комбинации значений функции /? W™(Q) в N произвольных точках — узлах кубатурной формулы: k=1 ' Перечислим основные методы построения кубатурных формул.

• Вероятностные методы типа Монте-Карло.

• Методы построения формул высокого алгебраического порядка (точных на многочленах большой степени) и инвариантных относительно некоторой группы изометрических преобразований.

• Функциональные методы построения решетчатых кубатурных формул.

• Теоретико-числовые методы построения формул, точных для конечных тригонометрических рядов.

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

Слабыми сторонами вероятностного подхода, однако, являются.

• малый порядок сходимости кубатурных формул.

• вероятностные оценки точности формул.

• «подстроение» класса интегрантов под свойства решений интегральных уравнений, а также итерационный метод их решения.

Существуют также программы, реализующие методы решетчатых кубатурных формул, созданные в разные годы Н. И. Блиновым [3, 2], JI. В. Войтишек [10], И. Умархановым [45], а также на основе методов теоретико-числового анализа, созданные Н. М. Коробовым [14]. Их основные недостатки:

• малая доступная размерность пространства интегрирования (не больше трех).

• малая точность вычислений.

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

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

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

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

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

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

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

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

Основными целями данной диссертации являются:

• решение задачи численного интегрирования функций по многомерным областям. В качестве теоретической базы используется аппарат решетчатых кубатурных формул с ограниченным пограничным слоем. Посредником, обеспечивающим преобразование математического алгоритма в машинный, является язык программирования С++ [25] с библиотекой параллельных функций MPI [36]. Конечным результатом является стандартная параллельная программа, предназначенная для использования в суперкомпьютерах с МРР (Massively Parallel Processing — массовый параллелизм) архитектурой — многопроцессорных системах с распределенной памятью.

• теоретическое исследование решеток узлов, дающих наилучший порядок приближения для оптимальных кубатурных формул в неизотропном пространстве ТУ&trade- (К2).

В диссертационной работе мы используем следующие методы исследования:

• теоретические методы функционального анализа.

• теоретические методы вычислительной математики.

• экспериментальные методы тестирования программ на многопроцессорных вычислительных системах.

Перечислим результаты, выносимые на защиту (попутно отмечая их новизну).

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

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

• Создана параллельная программа, эффективно использующая возможности передовых технологий (суперкомпьютеров) и языков программирования (С++ и MPI).

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

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

• Найден новый способ построения решеток узлов в пространстве W^iR2), на которых оптимальные формулы имеют наилучший порядок приближения.

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

• Экспериментально исследованы вычислительные свойства предложенного способа, сделаны выводы.

Основные результаты диссертанта отражены в работах [29, 34, 35, 37,.

38].

Заключение

.

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

В диссертации предложен, реализован и проанализирован один из самых быстрых и точных способов приближенного интегрирования по многомерным выпуклым областям с гладкими границами по функциям различной гладкости (из пространства W™(Cl) с т = 2.6). За основу берется алгоритм М. Д. Рамазанова, дополненный, оптимизированный и реализованный в виде стандартной параллельной программы автором диссертации.

Полученный результат обладает как вычислительными достоинствами (точностью, быстродействием, эффективностью, хорошей масштабируемостью на произвольное количество процессоров, переносимостью на любые платформы, совместимые с библиотекой MPI), так и теоретическими — строгим обоснованием алгоритма и гарантированной оценкой погрешности вычислений. Теоретическое обоснование стало возможным благодаря достижениям теории кубатурных формул, развитой C.JI. Соболевым и продолженной его последователями, в частности М. Д. Рамазановым.

Результат является новым как по форме (используется язык программирования С++ вкупе со стандартной библиотекой параллельных функций MPIпрограмма предназначена для современных многопроцессорных вычислительных систем с распределенной памятью), так и по содержанию (алгоритм дополнен и оптимизирован).

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

Второй результат, изложенный в диссертации, является продолжением исследования хороших свойств кубатурных формул, построенных на основе последовательностей. кубических решеток. М. Д. Рамазановым и автором диссертации совместно был установлен неожиданный факт достижения наилучшего порядка приближения интегралов в неизотропных пространствах (размерности 2) кубатурными формулами с кубической решеткой узлов, не зависящей от параметров гладкости, а лишь только повернутой на фиксированный угол.

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

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