Параллельные методы решения систем линейных уравнений с симметричными положительно-определенными матрицами на основе аддитивного разложения с перекрытиями тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Коньшин, Игорь Николаевич

Оглавление диссертации кандидат физико-математических наук Коньшин, Игорь Николаевич

1 Метод сопряженных градиентов (МСГ)

1.1 Прямые и итерационные методы решения линейных систем

1.2 Описание предобусловленного метода сопряженных градиентов

1.3 Оценка сходимости МСГ через спектральное число обусловленности

1.4 Оценка сходимости МСГ через К-число обусловленности

1.5 Устойчивость предобусловливаний МСГ.

2 Методы приближенных треугольных разложений

2.1 Предобусловливания, основанные на треугольном разложении.

2.2 Неполные и приближенные треугольные разложения

2.3 Предварительное масштабирование как этап предобусловливания.

2.4 Теория приближенного треугольного разложения

2.4.1 Приближенное треугольное разложение 2-го порядка

2.4.2 Улучшение обусловленности, достигаемое применением приближенных треугольных разложений.

2.4.3 Устойчивость приближенных треугольных разложений

2.5 Алгоритмы безотказного приближенного треугольного разложения.

2.6 Трудности распараллеливания IC2 разложения.

3 Параллелизуемое аддитивное предобусловливание

3.1 Методы построения параллельных предобусловливаний

3.1.1 Использование окаймленной блочно-диагональной структуры.

3.1.2 Использование приближенных обратных матриц

3.2 Блочное неполное обратное треугольное разложение.

3.2.1 Построение BIIC-предобусловливания.

3.2.2 Оценка качества предобусловливания по методу BIIC-IC2.

3.3 Диагональное и блочно-диагональное предобусловливание

4 Параллельная реализация и балансировка вычислений

4.1 Параллельные ЭВМ и параллельные вычисления

4.2 Параллельная реализация итерационных методов.

4.3 Описание параллельной реализации.

4.4 Способы балансировки вычислений

4.5 Теоретический анализ стратегий постфильтрации построенного предобусловливателя.

4.6 Описание реализации балансировки и применения параллельного ВПС-1С2-предобусловливания.

5 Численные эксперименты

5.1 Тестовые задачи и методика проведения численных экспериментов

5.2 Численные эксперименты для задач упругости тонкостенных оболочек.

5.3 Численные эксперименты для задач теории линейной упругости в механике упругого тела.

5.4 Численные эксперименты по балансировке вычислений для задач из коллекции университета Флориды.

5.5 Сравнение метода ВНС-1С2-МСГ с другими методами

Рекомендованный список диссертаций по специальности «Вычислительная математика», 01.01.07 шифр ВАК

Введение диссертации (часть автореферата) на тему «Параллельные методы решения систем линейных уравнений с симметричными положительно-определенными матрицами на основе аддитивного разложения с перекрытиями»

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Целью диссертационной работы является разработка, исследование и реализация на параллельных ЭВМ высокопроизводительного итерационного метода решения жестких систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами, а также численные исследования работоспособности предложенного метода для различных типов плохо обусловленных систем линейных уравнений.

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

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

2. Разработка эффективного способа балансировки вычислений для подзадач на различных процессорах.

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

4. Подтверждение эффективности метода для различных типов решаемых задач и на различных вычислительных системах.

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

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

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

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

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

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

6. Численными экспериментами подтверждена теоретически обоснованная высокая параллельная эффективность и вычислительная надежность разработанного метода.

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

Положения, выносимые на защиту:

1. Теоретические основы построения эффективного параллельного пре-добусловливания для решения систем линейных алгебраических уравнений с симметричными положительно-определенными матрицами.

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

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

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

Апробация работы. Результаты работы докладывались и обсуждались на международной конференции "РаСТ99" (Санкт-Петербург, Россия, 1999 г.), Всемирном 16-ом Конгрессе "IMACS 2000" по научным вычислениям, прикладной математике и моделированию (Лозанна, Швейцария, 2000), Голландско-российском симпозиуме NWO (МГУ, Москва, июнь 2000), Симпозиуме NWO (Амстердам-Ниймеген, Голландия, ноябрь 2000), Втором Международном научно-практическом Семинаре и Всероссийской молодежной школе "Высокопроизводительные параллельные вычисления на кластерных системах" (Нижний Новгород, Россия, 2002), Международной конференции "Parallel CFD 2003" (Москва, 2003), Международной конференции "VIII Забабахинские научные чтения" (РФЯЦ-ВНИИТФ, Сне-жинск, Россия, 2005), Международной конференции по численной геометрии, построении расчетных сеток и научным вычислениям "NUM-GRID2008" (ВЦ РАН, Москва, 2008), на научно-исследовательских семинарах Вычислительного центра РАН, Московского физико-технического института, Института автоматизации проектирования РАН, а также на семинарах Департамента информационных технологий Республики Индия (С-DAC, Пуна, Индия), Institut Frangais du Petrol (Париж, Франция), ExxonMobil Upstream Research Co. (Хьюстон, США).

Личный вклад соискателя. В работах соискателя соавтором является научный руководитель Капорин И. Е., ему принадлежит постановка задач и выбор математических методов исследований. Соискателем проведены теоретические исследования, разработаны параллельные предобусловливания, выполнены параллельные реализации предложенных алгоритмов и исследованы границы применения предложенных методов.

Публикации. Основные публикации по теме диссертации включают 11 работ, из них 3 работы [27, 28, 37] в ведущих отечественных и международных рецензированных научных изданиях, рекомендованных ВАК, 3 в других международных рецензируемых изданиях, 1 в российском рецензируемом издании, 1 в трудах международной конференции, 3 публикации в других научных изданиях.

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

Структура и объем работы. Диссертационная работа состоит из введения, 5 глав, заключения, списка литературы, содержит 18 таблиц и 23 рисунка. Объем работы 138 страниц. Список литературы включает в себя 112 наименований.