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

• Автор: Коньшин, Игорь Николаевич
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 138 с. : ил.

Оглавление
Введение
1 Метод сопряженных градиентов (МСГ)
1.1 Прямые и итерационные методы решения линейных систем
1.2 Описание предобусловленного метода сопряженных градиентов
1.3 Оценка сходимости МСГ через спектральное число обусловленности
1.4 Оценка сходимости МСГ через К-число обусловленности
1.5 Устойчивость предобусловливаний МСГ
2 Методы приближенных треугольных разложений
2.1 Предобусловливания, основанные на треугольном разложении
2.2 Неполные и приближенные треугольные разложения
2.3 Предварительное масштабирование как этап предобусловливания
2.4 Теория приближенного треугольного разложения
2-го порядка
2.4.1 Приближенное треугольное разложение 2-го порядка
2.4.2 Улучшение обусловленности, достигаемое применением приближенных треугольных разложений
2.4.3 Устойчивость приближенных треугольных разложений
2.5 Алгоритмы безотказного приближенного треугольного разложения
2.6 Трудности распараллеливания 1С2 разложения
3 Параллелизуемое аддитивное предобусловливание
3.1 Методы построения параллельных предобусловливаний

3.1.1 Использование окаймленной блочно-диагональной структуры
3.1.2 Использование приближенных обратных матриц
3.2 Блочное неполное обратное треугольное разложение
3.2.1 Построение ВПС-предобусловливания
3.2.2 Оценка качества предобусловливания
по методу ВПС-1С2
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 Сравнение метода ВПСТС2-МСГ с другими методами
Заключение
Литература

Введение
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Объект исследования и актуальность темы. Актуальность темы диссертационной работы обусловлена необходимостью эффективного численного решения систем линейных алгебраических уравнений с разреженными симметричными положительно-определенными матрицами большой размерности. Численное решение систем линейных уравнений является одной из наиболее часто встречающихся задач в научно-технических исследованиях и практических приложениях. Подобные задачи возникают, например, в математической физике при численном решении дифференциальных и интегральных уравнений. При этом прикладные задачи часто требуют решения систем линейных уравнений с большим числом неизвестных. К таким системам, например, приводит численное решение двумерных и особенно трехмерных задач математической физики, в которых условия физической и геометрической аппроксимации двумерной и трехмерной области диктуют использование достаточно мелкой расчетной сетки с большим числом расчетных узлов. Для возникающих систем линейных уравнений применение прямых методов решения оказывается неприемлемым как по причине большого времени решения, так и недостаточности объема оперативной памяти для хранения данных задачи. Итерационные методы решения систем линейных уравнений намного экономичнее с точки зрения использования оперативной памяти, но для ускорения их сходимости требуется строить эффективные предобусловливания, особенно при решении систем с плохо обусловленными матрицами.
Существенные затруднения связаны с тем, что наиболее актуальной задачей является решение систем линейных уравнений настолько большой размерности, что их решение возможно только на современных параллельных ЭВМ с распределенной памятью, что подразумевает разбиение данных

Предобусловливания вида (3.3) были введены в работах И.Е.Капорина [82, 42], где было предложено выбирать значения ненулевых элементов матрицы (7 из условия оптимизации К-обусловленности матрицы М = САСТ:
С = аттК(СМ.С?г), (3.4)
и дополнительно исследованы в [89], где была установлена связь перемасштабированной матрицы С с приближением в фробениусовой норме к точному треугольному множителю матрицы А. К преимуществам предобусловливания (3.3) можно отнести большой (как правило, избыточный) ресурс параллельности, а к недостаткам - большие арифметические затраты на вычисление множителя С и недостаточное улучшение обусловленности матрицы М — ОАО1 при увеличении числа ненулевых элементов матрицы (7 (см. [45]). Укажем также работы [62, 63, 61, 77], где обсуждаются детали практической реализации и применения таких предобусловливаний.
3.2. Блочное неполное обратное треугольное разложение
Ниже будет описан метод предобусловливания, основанный на построении набора подматриц заданной матрицы А по числу доступных процессоров. При этом сумма размеров подматриц несущественно превосходит размер исходной задачи, а из их треугольных разложений строится К-оптимальное (для уже выбранного упорядочения и перекрывающегося разбиения) приближение к обратной для заданной матрицы. Наконец, замена упомянутых точных треугольных разложений на их приближения, построенные по методу 1С2, приводит к предобусловливанию, которое является главным объектом рассмотрения настоящей диссертации.
Заметим, что использование техники оптимизации К-обусловленности для повышения качества предобусловливания МСГ явилось непосредственным инструментом построения, в качестве отправной точки которого используется упомянутое выше неполное обратное треугольное разложение (3.3).