Форматы хранения разреженных матриц

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

Разреженные матрицы в FEM-анализе

Матрицы, в которых большинство элементов равно нулю, называются разреженными. Элементы матрицы - образуют главную диагональ;
элементы матрицы образуют (k-1)-ую наддиагональ;
элементы образуют (k-1)-ую поддиагональ.

Пример. Ниже представлены две матрицы: матрица A - трехдиагональная матрица размера 5х5, элементы главной диагонали равны 10, элементы первой наддиагонали равны 3, элементы первой поддиагонали равны -1 ; матрица В - симметричная матрица размера 5х5, на главной диагонали которой все элементы равны 10, на второй наддиагонали элементы равны 5, а на третьей наддиагонали элементы равны 2.

В настоящее время во многих областях науки и техники многие расчеты ведутся с помощью систем линейных алгебраических уравнений (СЛАУ), причем матрица коэффициентов системы оказывается очень разреженной. Пример из электротехники: для расчета схемы, состоящей из 68 элементов, составляется матрица, разреженность которой составляет 0.085, т.е. отношение ненулевых элементов матрицы ко всем ее элементам равняется именно этому числу. Назрела необходимость найти быстрый и эффективный по затратам памяти способ решения СЛАУ с большим количеством ненулевых элементов. Ведь хранить полностью в памяти разреженную матрицу и тратить время на операции над нулевыми элементами слишком разорительно.

Динамический формат хранения разреженных матриц

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

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

Статический формат хранения разреженных матриц

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