Что такое разреженная матрица
Перейти к содержимому

Что такое разреженная матрица

  • автор:

Объясните, что такое разреженные матрицы, как их генерировать и математические операции над ними

Скажите, пожалуйста, правильно ли я думаю.
На сколько я понял разреженная матрица — это матрица вроде этой:

1 0 0 0 0 0 1 1 0 1 0 0 1 0 0 1 

Если это разреженная матрица — то генерировать ее элементы можно функцией rand() : rand()%2 Идентичен ли этот вид матриц квадратным матрицам (ряды=столбцам)? Математические операции (+,-,*,/) проводятся так же?
Спасибо!

Отслеживать
33.1k 2 2 золотых знака 33 33 серебряных знака 66 66 бронзовых знаков
задан 2 ноя 2018 в 14:38
Boris Makhlin Boris Makhlin
521 5 5 серебряных знаков 12 12 бронзовых знаков

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

2 ноя 2018 в 14:41
Какие шаги Вы предприняли, чтобы выяснить это самостоятельно?
– user176262
2 ноя 2018 в 15:12

@Igor Я читал в Википедии, но сугубо про математическую точку зрения. Более ничего не смог найти. Поэтому и обратился на этот форум

2 ноя 2018 в 15:43

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Вот представьте, что вам нужно работать с матрицами целых чисел размером 1000х1000. Легко подсчитать, что размер каждой матрицы будет 4Мб, а для перемножения двух матриц потребуется миллиард умножений и почти столько же сложений.

Если же мы знаем, что ненулевых элементов в матрице будет в районе 0.1%, то есть порядка 1000, то представление матрицы и работу с ней можно сильно оптимизировать. Например, можно представить матрицу как простой массив ненулевых элементов, где каждый ненулевой элемент представлен такой структурой:

typedef struct < short row; short column; int value; >NonZeroElem; 

Тогда матрица вместо миллиона четырехбайтовых целых будет представлена всего лишь тысячью восьмибайтовых описателей. То есть 8кб вместо 4Мб — в пятьсот раз меньше.

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

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

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

Разреженная матрица получается при использовании метода конечных элементов в двух измерениях. На картинке ненулевые элементы показаны черным.

Разреженная матрица — это матрица с преимущественно нулевыми элементами.

Среди специалистов нет единства в определении того, какое именно количество ненулевых элементов делает матрицу разреженной. Разные авторы предлагают различные варианты. Для матрицы порядка n число ненулевых элементов [1] :

  • есть O(n). Такое определение подходит разве что для теоретического анализа асимптотических свойств матричных алгоритмов;
  • в каждой строке не превышает 10 в типичном случае;
  • ограничено n^<1+\gamma>» width=»» height=»» />, где <img decoding=.
  • таково, что для данного алгоритма и вычислительной системы имеет смысл извлекать выгоду из наличия в ней нулей [1] .

По существу, разреженность соответствует системам со слабыми связями. Можно представить линию шариков, соединенных один за другим пружинками — это пример разреженной системы. Для контраста, если эти же шарики будут соединены пружинками каждый с каждым, то такая система будет представлять собой плотную матрицу. Термин разреженности используется также в комбинаторике и таких прикладных областях как сетевой анализ, при определении малой плотности значимых данных или соединений [источник не указан 70 дней] .

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

При хранении и преобразовании разреженных матриц в компьютере бывает полезно, а часто и необходимо, использовать специальные алгоритмы и структуры данных, которые учитывают разреженную структуру матрицы. Операции и алгоритмы, применяемые для работы с обычными, плотными матрицами, работают относительно медленно и требуют значительных объёмов памяти, когда применяются к большим разреженным матрицам. Разреженные данные по природе своей легко сжимаются, а учёт разреженности часто [источник не указан 70 дней] приводит к уменьшению требований к компьютерной памяти.

Представление

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

Алгоритмы

Согласно замыслу одного из участников Википедии, на этом месте должен располагаться раздел, посвящённый алгоритмам с разреженными матрицами.
Вы можете помочь проекту, написав этот раздел.

Применение

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

Библиотеки программ

Для вычислений с разреженными матрицами создано несколько библиотек:

  • SparseLib++ (C++) [2]
  • uBLAS (C++, в составе Boost) [3]
  • SPARSPAK (Fortran) [4]
  • CSparse (C) [5]

Примечания

  1. 12Писсанецки, 1988, Введение
  2. SparseLib++
  3. uBLAS / Boost
  4. Alan George, Esmond NgA brief description of SPARSPAK Waterloo sparse linear equations package (англ.) // ACM SIGNUM Newsletter, Volume 19 Issue 4, October 1984. — N.Y, 1984. — С. 17-20. — ISBN 978-1-4503-0245-6. — DOI:10.1145/1057931.1057933
  5. T. A. Davis, Direct Methods for Sparse Linear Systems, SIAM, Philadelphia, September 2006

Литература

  • Reginald P. Tewarson Sparse Matrices. — Academic Press, 1973. — 160 с. — ISBN 0126856508 перевод: Тьюарсон Р. Разреженные матрицы = Sparse Matrices. — М .: Мир, 1977. — 191 с.
  • Писсанецки С. Технология разреженных матриц = Sparse Matrix Technology. — М .: Мир, 1988. — 410 с. — ISBN 5-03-000960-4
  • Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М .: Мир, 1984. — 333 с.
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
  • Комбинаторика
  • Типы матриц

Wikimedia Foundation . 2010 .

  • Разработка требований к ПО
  • Разрежённый файл

Полезное

Смотреть что такое «Разреженная матрица» в других словарях:

  • разреженная матрица — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN sparse matrix … Справочник технического переводчика
  • РАЗРЕЖЕННАЯ МАТРИЦА — матрица с малым числом ненулевых элементов. Системы линейных уравнений с такими матрицами возникают, в частности, при аппроксимации дифференциальных уравнений конечноразностными или вариационно разностными. Н. С. Бахвалов … Математическая энциклопедия
  • Матрица линейного оператора — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Квадратная матрица — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Список матриц — Структура матрицы Здесь собраны наиболее важные классы матриц, используемые в математике, науке (в целом) и прикладной науке (в частности). Под матрицей понимается прямоугольный массив чисел … Википедия
  • Перемножение матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Произведение матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Произведение матрицы на число — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Разница матриц — Матрица математический объект, записываемый в виде прямоугольной таблицы чисел (или элементов кольца) и допускающий алгебраические операции (сложение, вычитание, умножение и др.) между ним и другими подобными объектами. Правила выполнения… … Википедия
  • Симплекс-метод — Не путать с «симплекс методом» методом оптимизации произвольной функции. См. Метод Нелдера Мида Симплекс метод алгоритм решения оптимизационной задачи линейного программирования путём перебора вершин выпуклого многогранника в… … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

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

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

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

Функции

Создание

spalloc Выделите место для разреженной матрицы
spdiags Извлеките ненулевые диагонали и создайте разреженную полосу и диагональные матрицы
speye Разреженная единичная матрица
sprand Разреженная равномерно распределенная случайная матрица
sprandn Разреженная нормально распределенная случайная матрица
sprandsym Разреженная симметричная случайная матрица
sparse Создайте разреженную матрицу
spconvert Импортируйте из внешнего формата разреженной матрицы

Манипуляция

issparse Определите, разреженно ли введенный
nnz Количество ненулевых элементов матрицы
nonzeros Ненулевые элементы матрицы
nzmax Сумма устройства хранения данных выделяется для ненулевых элементов матрицы
spfun Примените функцию к ненулевым элементам разреженной матрицы
spones Замените ненулевые элементы разреженной матрицы на единицы
spparms Установите параметры для стандартных программ разреженной матрицы
spy Визуализируйте шаблон разреженности матрицы
find Найдите индексы и значения ненулевых элементов
full Преобразуйте разреженную матрицу в полное устройство хранения данных

Переупорядочение алгоритмов

dissect Вложенное сочетание рассечения
amd Аппроксимируйте минимальное сочетание степени
colamd Столбец аппроксимированное минимальное сочетание степени
colperm Разреженное сочетание столбца на основе ненулевого количества
dmperm Разложение Дулмаге-Мендельсона
randperm Случайное сочетание целых чисел
symamd Симметричное аппроксимированное минимальное сочетание степени
symrcm Разреженное упорядоченное расположение обратного алгоритма Катхилла-Макки

Итеративные методы и предварительные формирователи

pcg Решите систему линейных уравнений — предобусловленный метод сопряженных градиентов
lsqr Решите систему линейных уравнений — метод наименьших квадратов
minres Решите систему линейных уравнений — метод минимальных невязок
symmlq Решите систему линейных уравнений — симметричный метод LQ
gmres Решите систему линейных уравнений — обобщенный метод минимальных невязок
bicg Решите систему линейных уравнений — бисопряженный метод градиентов
bicgstab Решите систему линейных уравнений — стабилизировал бисопряженный метод градиентов
bicgstabl Решите систему линейных уравнений — стабилизировал бисопряженные градиенты (l) метод
cgs Решите систему линейных уравнений — методы сопряженных градиентов придали методу квадратную форму
qmr Решите систему линейных уравнений — метод квази-минимальных невязок
tfqmr Решите систему линейных уравнений — метод квази-минимальных невязок без транспонирования
equilibrate Матрица, масштабирующаяся для улучшенного создания условий
ichol Неполная факторизация Холесского
ilu Неполная LU-факторизация

Разреженная матрица — Sparse matrix

Разреженная матрица, полученная при решении задачи конечных элементов в двух измерениях. Ненулевые элементы показаны черным.

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

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

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

  • 1 Сохранение разреженной матрицы
    • 1.1 Словарь ключей (DOK)
    • 1.2 Список списков (LIL)
    • 1.3 Список координат (COO)
    • 1.4 Сжатая разреженная строка (CSR, Формат CRS или Yale)
    • 1.5 Сжатый разреженный столбец (CSC или CCS)
    • 2.1 С полосами
    • 2.2 Диагональ
    • 2.3 Симметричная
    • 2.4 Диагональ блока

    Сохранение разреженной матрицы

    Матрица обычно хранится как двумерный массив. Каждая запись в массиве представляет собой элемент a i, j матрицы, и к нему обращаются два индекса i и j. Обычно i — это индекс строки, пронумерованный сверху вниз, а j — индекс столбца, пронумерованный слева направо. Для матрицы размера m × n объем памяти, необходимый для хранения матрицы в этом формате, пропорционален m × n (без учета того факта, что размеры матрицы также должны быть сохранены).

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

    Форматы можно разделить на две группы:

    • Форматы, поддерживающие эффективную модификацию, например DOK (Словарь ключей), LIL (Список списков) или COO (Список координат). Обычно они используются для построения матриц.
    • Те, которые поддерживают эффективный доступ и операции с матрицами, такие как CSR (сжатая разреженная строка) или CSC (сжатый разреженный столбец).

    Словарь ключей (DOK)

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

    Список списков (LIL)

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

    Список координат (COO)

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

    Сжатая разреженная строка (формат CSR, CRS или Йельского университета)

    Сжатая разреженная строка (CSR) или сжатое хранилище строк (CRS) или Йельский формат представляет собой матрицу M тремя (одномерными) массивами, которые соответственно содержат ненулевые значения, экстенты строк и индексы столбцов. Он похож на COO, но сжимает индексы строк, отсюда и название. Этот формат обеспечивает быстрый доступ к строке и умножение матрицы на вектор (M x). Формат CSR используется по крайней мере с середины 1960-х годов, первое полное описание появилось в 1967 году.

    Формат CSR хранит разреженную матрицу m × n M в виде строки с использованием трех (одномерных) массивов (V, COL_INDEX, ROW_INDEX). Пусть NNZ обозначает количество ненулевых записей в M . (Обратите внимание, что здесь должны использоваться отсчитываемые от нуля индексы.)

    • Массивы V и COL_INDEX имеют длину NNZ и содержат ненулевые значения и индексы столбцов этих значений соответственно.
    • Массив ROW_INDEX имеет по одному элементу на строку в матрице и кодирует индекс в V, с которого начинается данная строка. (Он может содержать дополнительный конечный элемент, для которого установлено значение NNZ).

    (0 0 0 0 5 8 0 0 0 0 3 0 0 6 0 0) 0 0 0 0 \\ 5 8 0 0 \\ 0 0 3 0 \\ 0 6 0 0 \\\ end >>

    — это матрица 4 × 4 с 4 ненулевыми элементами, поэтому

    V = [5 8 3 6 ] COL_INDEX = [0 1 2 1] ROW_INDEX = [0 0 2 3 4]

    при условии, что язык с нулевым индексом.

    Чтобы извлечь строку, мы сначала определяем:

    row_start = ROW_INDEX [row] row_end = ROW_INDEX [row + 1]

    Затем мы берем срезы из V и COL_INDEX, начиная с в row_start и заканчивая row_end.

    Чтобы извлечь строку 1 (вторая строка) этой матрицы, мы устанавливаем row_start = 0 и row_end = 2 . Затем мы делаем срезы V [0: 2] = [5, 8] и COL_INDEX [0: 2] = [0, 1] . Теперь мы знаем, что в строке 1 у нас есть два элемента в столбцах 0 и 1 со значениями 5 и 8.

    В этом случае представление CSR содержит 13 элементов по сравнению с 16 в исходной матрице. Формат CSR сохраняет память только тогда, когда NNZ (10 20 0 0 0 0 0 30 0 40 0 ​​0 0 0 50 60 70 0 0 0 0 0 0 80) 10 20 0 0 0 0 \\ 0 30 0 40 0 0 \\ 0 0 50 60 70 0 \\ 0 0 0 0 0 80 \\\ end >>

    — это матрица 4 × 6 (24 элемента) с 8 ненулевыми элементами, поэтому

    V = [10 20 30 40 50 60 70 80] COL_INDEX = [0 1 1 3 2 3 4 5] ROW_INDEX = [0 2 4 7 8]

    . Всего сохраняется как 21 запись.

    • ROW_INDEX разбивает массив V на строки: (10, 20) (30, 40) (50, 60, 70) (80) ;
    • COL_INDEX выравнивает значения в столбцах: (10, 20. ) (0, 30, 0, 40. ) (0, 0, 50, 60, 70, 0) (0, 0, 0, 0, 0, 80) .

    Обратите внимание, что в В этом формате первое значение ROW_INDEX всегда равно нулю, а последнее — всегда NNZ, поэтому они в некотором смысле избыточны (хотя в языках программирования, где длина массива должна быть явно сохранена, NNZ не будет избыточным). Тем не менее, это позволяет избежать необходимости обрабатывать исключительный случай при вычислении длины каждой строки, поскольку это гарантирует, что формула ROW_INDEX [i + 1] — ROW_INDEX [i] работает для любой строки i. Более того, стоимость памяти этого избыточного хранилища, вероятно, незначительна для достаточно большой матрицы.

    (старый и новый) форматы разреженных матриц Йельского университета являются экземплярами схемы CSR. Старый формат Йельского университета работает точно так же, как описано выше, с тремя массивами; новый формат объединяет ROW_INDEX и COL_INDEX в один массив и обрабатывает диагональ матрицы отдельно.

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

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

    Сжатый разреженный столбец (CSC или CCS)

    CSC аналогичен CSR, за исключением того, что значения считываются сначала по столбцу, индекс строки сохраняется для каждого значения, а указатели столбцов сохраняются. Например, CSC — это (val, row_ind, col_ptr), где val — это массив ненулевых значений матрицы (сверху вниз, затем слева направо); row_ind — это индексы строк, соответствующие значениям; и col_ptr — это список индексов val, с которых начинается каждый столбец. Название основано на том факте, что информация индекса столбца сжимается относительно формата COO. Обычно для построения используется другой формат (LIL, DOK, COO). Этот формат эффективен для арифметических операций, разделения столбцов и произведений матрица-вектор. См. scipy.sparse.csc_matrix. Это традиционный формат для указания разреженной матрицы в MATLAB (через функцию sparse ).

    Специальная структура

    с полосами

    Важным специальным типом разреженных матриц является матрица с полосами, определяемая следующим образом. Нижняя полоса матрицы A- это наименьшее число p, такое что запись a i, j исчезает всякий раз, когда i>j + p. Аналогично, верхняя полоса пропускания — это наименьшее число p, такое что a i, j = 0 всякий раз, когда i (XXX ⋅ ⋅ ⋅ ⋅ XX ⋅ XX ⋅ ⋅ X ⋅ X ⋅ X ⋅ ⋅ ⋅ X ⋅ X ⋅ X ⋅ ⋅ XX ⋅ XXX ⋅ ⋅ ⋅ XXX ⋅ ⋅ ⋅ X ⋅ X) X X X \ cdot \ cdot \ cdot \ cdot \\ X X \ cdot X X \ cdot \ cdot \\ X \ cdot X \ cdot X \ cdot \ cdot \\\ cdot X \ cdot X \ cdot X \ cdot \\\ cdot X X \ cdot X X X \\\ cdot \ cdot \ cdot X X X \ cdot \\\ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \ cdot \\\ end > \ right)>

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

    Посредством переупорядочивания строк и столбцов матрицы A можно получить матрицу A ‘с меньшей полосой пропускания. Для минимизации полосы пропускания разработан ряд алгоритмов.

    Диагональ

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

    Симметричная

    Симметричная разреженная матрица возникает как матрица смежности неориентированного графа ; его можно эффективно сохранить как список смежности.

    Диагональ блока

    A , блочно-диагональная матрица состоит из подматриц вдоль своих диагональных блоков. Блочно-диагональная матрица A имеет вид

    где Ak- квадратная матрица для всех k = 1. n.

    Уменьшение заполнения

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

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

    Решение уравнений с разреженными матрицами

    Для решения разреженных матриц существуют как итерационные, так и прямые методы.

    Итерационные методы, такие как метод сопряженного градиента и GMRES, используют быстрые вычисления произведений матрица-вектор A xi > , где матрица A является разреженной. Использование предобуславливателей может значительно ускорить сходимость таких итерационных методов.

    Программное обеспечение

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

    • SuiteSparse, набор алгоритмов разреженных матриц, ориентированных на прямое решение разреженных линейных систем.
    • PETSc, большая библиотека C, содержащая множество различных решателей матриц для различных форматов хранения матриц.
    • Trilinos, большая библиотека C ++ с подбиблиотеками, предназначенными для хранения плотных и разреженных матриц и решения соответствующих линейных систем.
    • Eigen3 — это Библиотека C ++, содержащая несколько решателей разреженных матриц. Однако ни один из них не является параллельным.
    • MUMPS (MUltifrontal M в целом P параллельным разреженным прямым S olver), написанным на Fortran90, — это фронтальный решатель.
    • DUNE, библиотека конечных элементов, которая также имеет подбиблиотеку для разреженных линейных систем и их решения.
    • PaStix.
    • SuperLU.
    • Armadillo предоставляет удобная оболочка C ++ для BLAS и LAPACK.
    • SciPy обеспечивает поддержку нескольких форматов разреженных матриц, линейной алгебры и решателей.
    • SPArse Matrix (спам) Пакет R для разреженных матриц. 302>Wolfram Language Обработка разреженных массивов с буквально астрономическим числом элементов.
    • ALGLIB — это библиотека C ++ и C # с поддержкой разреженной линейной алгебры
    • ARPACK Библиотека Fortran 77 для диагонализации разреженных матриц и манипуляции с использованием алгоритма Арнольди
    • SPARSE Справочный (старый) Пакет NIST для диагонализации (реальной или сложной) разреженной матрицы
    • SLEPc Библиотека для решения крупномасштабных линейных s системы и разреженные матрицы
    • Sympiler, генератор кода для конкретной предметной области и библиотека для решения линейных систем и задач квадратичного программирования.

    История

    Термин разреженная матрица, возможно, был придуман Гарри Марковиц, который инициировал некоторые новаторские работы, но затем покинул поле.

    См. Также

    • Матричное представление
    • Принцип Парето
    • Рваная матрица
    • Матрица с одним элементом
    • Skyline матрица
    • Код разреженного графа
    • Разреженный файл
    • Формат файла Harwell-Boeing
    • Форматы обмена Matrix Market

    Примечания

    Ссылки

    • Голуб, Джин Х. ; Ван Лоан, Чарльз Ф. (1996). Матричные вычисления (3-е изд.). Балтимор: Джонс Хопкинс. ISBN 978-0-8018-5414-9 . CS1 maint: ref = harv (ссылка )
    • Stoer, Josef; Bulirsch, Roland (2002). Введение в численный анализ (3-е изд.). Берлин, Нью-Йорк: Springer-Verlag. ISBN 978-0-387-95452-3 .
    • Тьюарсон, Реджинальд П. (май 1973 г.). Разреженные матрицы (часть серии «Математика в науке и технике»). Academic Press Inc. (Эта книга, написанная профессором Государственного университета Нью-Йорка в Stony Book, была первой книгой, посвященной исключительно разреженным матрицам. В начале 1980-х в этом университете были предложены курсы для аспирантов, использующие эту книгу в качестве учебника. (PDF).
    • Писсанецки, Серджио (1984). Технология разреженных матриц. Academic Press.
    • Сней, Ричард А. (1976). «Уменьшение профиля разреженных симметричных матрицы ». Bulletin Géodésique. 50 (4): 341. doi : 10.1007 / BF02521587. hdl : 2027 / uc1.3121002 4848523.Также Технический меморандум NOAA NOS NGS-4, Национальная геодезическая служба, Роквилл, Мэриленд.

    Дополнительная литература

    • Gibbs, Norman E.; Пул, Уильям Дж.; Штокмейер, Пол К. (1976). «Сравнение нескольких алгоритмов сокращения полосы пропускания и профиля». Транзакции ACM на математическом ПО. 2 (4): 322–330. doi : 10.1145 / 355705.355707.
    • Gilbert, John R.; Молер, Клив; Шрайбер, Роберт (1992). «Разреженные матрицы в MATLAB: проектирование и реализация». Журнал SIAM по матричному анализу и приложениям. 13 (1): 333–356. CiteSeerX10.1.1.470.1054. doi : 10.1137 / 0613024.
    • Исследование алгоритмов разреженной матрицы в Техасском университете AM
    • Коллекция SuiteSparse Matrix
    • МАЛЕНЬКИЙ проект Проект, финансируемый ЕС разреженные модели, алгоритмы и изучение словаря для крупномасштабных данных.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *