6CAD-CAE-23 Упорядочение (1014142), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

Говорят, что упорядочение является оптимальным в смысле заполнения, если оно приводит к наименьшему возможному за­полнению. Упорядочение считается оптимальным в смысле затрат арифметических операций, если число операций, выполняемых при обработке переупорядоченной матрицы, минимально. Для матрицы А порядка п существует n! различных упорядочений, из которых одно или более оказывается оптимальным в смысле за­полнения, и несколько упорядочений (не менее одного) оказы­ваются оптимальными в смысле минимизации числа арифмети­ческих операций. Можно было бы пожелать найти такие опти­мальные упорядочения, однако, к сожалению, задача их отыска­ния представляется чрезвычайно трудной и о существовании эффек­тивных алгоритмов, пригодных для этой цели, не известно ни­чего. Существующие процедуры являются эвристическими и обычно основываются на попытках отыскания упорядочений, обеспечи­вающих понижение заполнения и числа арифметических операций, но не гарантирующих достижения точного минимума этих величин.

Для разреженной матрицы А общего вида проблема упорядочения решается сложнее, так как в этом случае необходима для обеспечения численной устойчивости та или иная форма выбора главного элемента, т.е. перестановки строк и/или столбцов. Таким образом при заданной А общего вида получают разложение для РА или PAQ, где P и Q - матрицы перестановок соответствующих размеров.

Матрицей перестановок называется такая матрица, у которой все элементы либо 0, либо 1, а в каждой строке и в каждом столбце имеется только одна 1. Например:

0 1 0 0

1 0 0 0 или 1 0 0

0 0 1 0 0 0 1

0 0 0 1 0 1 0

Заметим, что умножение на Р слева переставляет строки А, а умножение на Q справа переставляет столбцы А.

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

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

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

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

Поскольку PAP^T также симметрична и положительно определена при любой матрице перестановки Р, это означает, что можно симметрично переупорядочить А, во-первых, не заботясь о численной устойчивости и, во-вторых, до начала реального численного разложения.

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

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

Таким образом три задачи:

1) выбор надлежащего упорядочения,

2) формирование подходящей схемы хранения,

3) реальные вычисления

могут быть разделены как самостоятельные объекты исследования и как разные модули программного обеспечения.

Ситуация изображена на рисунке:

Эта независимость задач имеет ряд отчетливых преимуществ.

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

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

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

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

Задачи, которые приходится решать при выборе метода решения.

Итак, при некоторой матрице перестановки Р мы вместо А разлагаем в произведение LL^T матрицу РАР^Т и, в соответствии с тем или иным критерием L может оказаться много привлекательнее, чем L.

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

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

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

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

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

Шаг1 (упорядочение). Найти хорошее упорядочение (перестановку Р) для данной матрицы с учетом выбранного метода хранения.

Шаг 2 (распределение памяти). Определить необходимую информацию о множителе Холесского L матрицы РАР^Т с тем, чтобы сформировать подходящую схему хранения.

Шаг 3 (разложение). Разложить переупорядоченную матрицу РАР^Т в произведение LL^T.

Шаг 4 (решение треугольных систем). Решить системы Ly=b и L^Тz=y, после этого положить x=P^TZ.

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

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

Чаще всего задачами при выборе метода решения являются :

а) уменьшить запросы к памяти,

б) уменьшить время исполнения,

в) уменьшить некоторую комбинацию памяти и времени исполнения; эта комбинация отражает относительную цену ресурсов в стоимости использования машинной системы.

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

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

По запросам памяти можно сказать следующее.

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

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

В качестве примера рассмотрим два упорядочения А₁ и А₂ некоторой матрицы А и соответствующие им множители L₁ и L₂, каждый из которых хранятся в своих схемах хранения. Элементы нижнего треугольника множителя L₁ (исключая диагональные) хранятся построчно в едином массиве, параллельный массив содержит их столбцовые индексы. Третий массив указывает положение каждой строки, а четвертый хранит диагональные элементы L₁.

Характеристики

Список файлов лекций