В научных вычислениях , хранении матрицы горизонта , или СКСЕ, или хранении матрицы переменной полосы или схеме хранения огибающего [1] является формой разреженной матрицы матрицы формата для хранения , что снижает требование хранения матрицы более чем полосчатое хранение . В ленточном хранилище сохраняются все записи на фиксированном расстоянии от диагонали (называемом половинной шириной полосы). В хранилище горизонтов, ориентированном на столбцы, сохраняются только записи от первой ненулевой записи до последней ненулевой записи в каждом столбце. Существует также ориентированное на строки хранилище горизонтов, а для симметричных матриц обычно сохраняется только один треугольник. [2]
Хранение горизонта стало очень популярным в кодах конечных элементов для структурной механики , потому что линия горизонта сохраняется с помощью разложения Холецкого (метод решения систем линейных уравнений с симметричной положительно определенной матрицей ; вся заливка попадает в горизонт) , а системы уравнений из конечных элементов имеют относительно небольшой горизонт. Кроме того, усилия по кодированию линии горизонта Холецкого [3] примерно такие же, как и в случае Холецкого для полосовых матриц (доступны для полосовых матриц , например, в LAPACK ; прототип кода горизонта см. [3] ).
Перед сохранением матрицы в формате горизонта строки и столбцы обычно перенумеровываются, чтобы уменьшить размер линии горизонта (количество сохраненных ненулевых записей) и уменьшить количество операций в алгоритме горизонта Холецкого. Тот же эвристический алгоритм перенумерации, который уменьшает полосу пропускания, также используется для уменьшения горизонта. Основным и одним из самых ранних алгоритмов для этого является обратный алгоритм Катхилла – Макки .
Однако хранилище горизонтов не так популярно для очень больших систем (многие миллионы уравнений), потому что горизонт Холецкого не так легко адаптировать для массово-параллельных вычислений , и общие разреженные методы [4], которые хранят только ненулевые элементы матрицы, становятся более эффективен для очень больших задач из-за гораздо меньшего количества заполнений.
См. Также [ править ]
Ссылки [ править ]
- ^ Уоткинс, Дэвид С. (2002), Основы матричных вычислений (второе изд.), Нью-Йорк: John Wiley & Sons, Inc., стр. 60, ISBN 0-471-21394-2
- ^ Барретт, Ричард; Ягода; Чан; Деммель; Донато; Донгарра; Eijkout; Посо; Ромине; Ван дер Ворст (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
