LEC-25 (Материалы к лекциям), страница 2

На коммерческом рынке сейчас имеются хорошие программы для разреженных матриц. В каталоге [Heath, 1982] перечислено более 120 программ. Многие программы описаны в каталоге Харуэлла [Hopper, 1980] и двух обзорных статьях [Duff, 1982; Parlett, 1983]. Составление хорошей программы для разреженных матриц — дело непростое. Оно требует мастерского программирования. Как и в любой области техники, конструктор программы должен построить прототип, тщательно испытать [Duff, 1979, Eisenstat , 1979, Duff et al., 1982] и усовершен­ствовать его, прежде чем будет получена окончательная модель и начнется массовое производство. В применении к программному обеспечению массовое производство означает многократное копи­рование программы и перенос ее на многие разные машины. Сле­довательно, программа должна быть переносимой. С точки зре­ния пользователя, инженер по программному обеспечению ответ­ствен за правильный выбор программы и файловых структур и установку их на машине. Для пользователя продуктом служит не программа, а результат. Обеспечить выполнение требований, предъявляемых к хорошей программе, нелегко. Следует отметить, что структура и объем программ для ЭВМ определяются алгоритмами решения задачи. Машинную программу строит соответствующий транслятор с алгоритмического языка, и возможности ее улучшения исчерпываются применением ассемблера (в предположении, если программирование выполнено грамотно). В то же время структуры данных выбираются авторами, и от рациональности этого выбора в значительной степени зависит общая эффективность решения задачи.

11. Разреженные матрицы и их хранение

Во многих областях человеческой деятельности информацию часто представляют в форме матриц. Матрица — это регулярный числовой массив. В специальной литературе имеется несколько определений разреженной матрицы. Суть их состоит в том, что матрица разрежена, если в ней «много» нулевых элементов. Не­которые авторы используют понятия, связанные с предельным переходом: матрицу порядка п они называют разреженной, если число ее ненулевых элементов есть f(n) . Это означает, что число отличающихся от нуля элементов при достаточно больших п пропорционально п. Однако для заданной матрицы число п не является не только достаточно большим, но и вполне конкретным числом. Приве­денное определение полезно только для теоретических целей типа попытки оценить асимптотическое поведение алгоритма. В [Brayton, 1970] критерием разреженности предлагается считать ограниченность числа ненулевых элементов в строке, в типичном случае от 2 до 10. Другое определение принадлежит Альварадо [Alvarado, 1979]: чтобы матрица порядка п была разреженной, число ее ненулевых элементов должно выражаться как п^1+у, где у < 1. Типичные значения у: 0.2 для электрических задач; 0.5 для ленточных матриц, ассоциированных с сетками. Матрица порядка 1000 при у = 0.9 имеет 501187 ненулевых элементов, и возникает вопрос, стоит ли считать такую матрицу разреженной.

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

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

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

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

Эта система имеет только 16 коэффициентов, а мы используем 64 позиции! С этой точки зрения даже кажется весьма неесте­ственным заполнять несущественные позиции нулями, а затем пытаться извлечь выгоду из наличия столь большого числа ну­лей. Строго говоря, разреженную матрицу следует вообще пред­ставлять себе не как матрицу, а скорее как граф, где каждая пара уравнение — неизвестное ассоциируется с вершиной, а каж­дый коэффициент — с ребром. Вот почему теория графов играет такую важную роль в технологии разреженных матриц. И в этом как раз причина возникновения технологии разреженных матриц. Разреженная матрица, будучи множеством чисел, не имеющим регулярности, не может быть представлена в памяти машины тем же простым способом, что и полная матрица. Если мы сохра­няем численные значения коэффициентов нашей системы урав­нений, мы должны вместе со значением каждого коэффициента хранить номер соответствующего уравнения и номер соответствующего неизвестного.

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

Матричные алгоритмы должны проектироваться таким обра­зом, чтобы обрабатывались только ненулевые элементы и чтобы на основании предварительного знания о расположении ненулевых элементов избегались операции типа сложения с нулем или умно­жения на нуль. Таким образом, число операций, производимых машиной при исполнении алгоритма, пропорционально числу ненулевых элементов, а не числу всех элементов матрицы. Заме­тим, что было бы неправильно хранить все элементы, включая нули, а затем обходить операции с нулями с помощью опера­тора IF. Этот оператор будет без необходимости выполняться п² раз или более, превращая алгоритм в квадратичный по порядку п матрицы. Хороший алгоритм для разреженных матриц использует имеющиеся у него сведения о позициях ненулевых элементов, чтобы делать только необходимые операции. Если для разрежен­ной матрицы число ненулевых элементов в строке постоянно, то во многих случаях порядок хорошего алгоритма может умень­шаться до n.

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

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

• хранить только ненулевые элементы,

• оперировать только с ненулевыми элементами

• сохранять разреженность.

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

И последнее.

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

Хранение разреженных матриц

Упакованная форма хранения.

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

а) такая форма позволяет хранить и обрабатывать в оперативной памяти компьютера матрицы больших размерностей, чем при обычном хранении;

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

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

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

Существует много различных схем упаковки.

Пусть квадратная матрица А порядка n содержит  нулевых элементов, причем << n². Ясно, что матрица А является разреженной.

Обозначим элемент i -ой строки и j-го столбца матрицы через a_ij . Для того, чтобы хранить в памяти только ненулевые элементы a_ij  0, необходимо запомнить i, j и a_ij.. Если используется одна ячейка памяти для каждой из этих величин, то для хранения всех ненулевых элементов матрицы А требуется 3 ячеек. Очевидно 3 должно быть существенно меньше n², чтобы имело смысл тратить на введение упаковки дополнительные усилия и машинное время.

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

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

11.1. Схемы с непосредственной адресацией

11.1. 1.Использование адресных функций

Простейшая структура данных — это массив.

Все существующие в настоящее время серийные ЭВМ имеют оперативное ЗУ линейной структуры. Это означает, что положение объекта в ЗУ характеризуется одним числом - адресом, позволяющим однозначно определить обращение (запись - чтение) к этому объекту.

Таким образом, формально ОЗУ можно рассматривать как вектор, а адрес -как индекс элемента этого вектора. Тогда размещение различных объектов, например, матриц в ОЗУ описывается задание взаимно-однозначного соответствия между элементами этих объектов и линейной последовательностью индексов. Это соответствие в различных случаях может устанавливаться по-разному для одного и того же объекта.

Например, обычная матрица А=а_{i j}, представляющая двумерную совокупность элементов, может быть отображена на линейную память двояко: в порядке перебора по строкам или по столбцам.

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

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