Матрица горизонта
В научных вычислениях используется матричное хранилище горизонта , или SKS, или матричное хранилище с переменной полосой , или схема хранения конверта. [1] представляет собой форму матрицы формата хранения с разреженной матрицей , которая снижает требования к объему памяти для матрицы в большей степени, чем полосовое хранилище . При групповом хранении сохраняются все записи в пределах фиксированного расстояния от диагонали (так называемой половины пропускной способности). В хранилище горизонтов, ориентированном на столбцы, сохраняются только записи от первой ненулевой записи до последней ненулевой записи в каждом столбце. Существует также хранилище линий горизонта, ориентированное на строки, а для симметричных матриц обычно сохраняется только один треугольник. [2]
Хранение линий горизонта стало очень популярным в кодах конечных элементов для строительной механики , поскольку линия горизонта сохраняется за счет разложения Холецкого (метод решения систем линейных уравнений с симметричной положительно определенной матрицей ; все заполнения попадают в пределы линии горизонта). , а системы уравнений из конечных элементов имеют относительно небольшую линию горизонта. Кроме того, усилия по кодированию горизонта Холецкого [3] примерно то же самое, что и для Холецкого для полосчатых матриц (доступно для полосчатых матриц , например, в LAPACK ; прототип кода линии горизонта см. [3] ).
Перед сохранением матрицы в формате линии горизонта строки и столбцы обычно перенумеровываются, чтобы уменьшить размер линии горизонта (количество сохраняемых ненулевых записей) и уменьшить количество операций в алгоритме линии горизонта Холецкого. Тот же эвристический алгоритм перенумерации, который уменьшает полосу пропускания, также используется для уменьшения линии горизонта. Базовым и одним из первых алгоритмов, позволяющих это сделать, является обратный алгоритм Катхилла – Макки .
Однако хранилище горизонтов не так популярно для очень больших систем (многие миллионы уравнений), потому что горизонт Холецкого не так легко адаптировать для массово-параллельных вычислений и общих разреженных методов. [4] которые хранят только ненулевые элементы матрицы, становятся более эффективными для очень больших задач из-за гораздо меньшего количества заполнения.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Уоткинс, Дэвид С. (2002), Основы матричных вычислений (второе изд.), Нью-Йорк: John Wiley & Sons, Inc., стр. 60, ISBN 0-471-21394-2
- ^ Барретт, Ричард; Ягода; Чан; Деммель; Донато; Донгарра; Эйкоут; Посо; Ромин; Ван дер Ворст (1994), «Skyline Storage (SKS)» , Шаблоны для решения линейных систем , SIAM, ISBN 0-89871-328-5
- ^ Перейти обратно: а б Джордж, Алан; Лю, Джозеф WH (1981), Компьютерное решение больших разреженных положительно определенных систем , Prentice-Hall Inc., ISBN 0-13-165274-5 . Книга также содержит описание и исходный код простых процедур с разреженными матрицами, которые по-прежнему полезны, даже если их давно заменили.
- ^ Дафф, Иэн С.; Эрисман, Альберт М.; Рид, Джон К. (1986), Прямые методы для разреженных матриц , Oxford University Press, ISBN 0-19-853408-6
