Матрица горизонта - Skyline matrix

В научные вычисления, скайлайн матричное хранилище, или SKS, или матричная память с переменной полосой пропускания, или схема хранения конвертов[1] это форма разреженная матрица матрица формата хранения, которая снижает требования к хранению матрицы более чем ленточное хранилище. В ленточном хранилище сохраняются все записи в пределах фиксированного расстояния от диагонали (называемого половинной шириной полосы). В ориентированном на столбцы хранилище горизонтов сохраняются только записи от первой ненулевой записи до последней ненулевой записи в каждом столбце. Существует также ориентированное на строки хранилище горизонтов, а для симметричных матриц обычно сохраняется только один треугольник.[2]

Хранилище Skyline стало очень популярным в заключительный элемент коды для строительная механика, потому что линия горизонта сохраняется Разложение Холецкого (метод решения систем линейные уравнения с симметричным, положительно определенная матрица; все заполнять падает в пределах горизонта), а системы уравнений из конечных элементов имеют относительно небольшой горизонт. Кроме того, усилия по кодированию скайлайна Холецкого[3] примерно такая же, как у Холецкого для ленточных матриц (доступно для ленточные матрицы, например в ЛАПАК; код прототипа горизонта см. [3]).

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

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

Смотрите также

использованная литература

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