Доступ к разреженным матрицам

Ненулевые элементы

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

  • nnz возвращает количество ненулевых элементов в разреженной матрице.

  • nonzeros возвращает вектор-столбец, содержащий все ненулевые элементы разреженной матрицы.

  • nzmax возвращает количество пространства памяти, выделенного для ненулевых записей разреженной матрицы.

Чтобы попробовать некоторые из них, загрузите предоставленную разреженную матрицу west0479, один из набора Харуэлла-Boeing.

load west0479
whos
  Name            Size             Bytes  Class     Attributes

  west0479      479x479            34032  double    sparse   

Это матричные модели восьмиэтапный химический столбец дистилляции.

Попробуйте эти команды.

nnz(west0479)
ans =

        1887
format short e
west0479
west0479 =

  (25,1)      1.0000e+00
  (31,1)     -3.7648e-02
  (87,1)     -3.4424e-01
  (26,2)      1.0000e+00
  (31,2)     -2.4523e-02
  (88,2)     -3.7371e-01
  (27,3)      1.0000e+00
  (31,3)     -3.6613e-02
  (89,3)     -8.3694e-01
  (28,4)      1.3000e+02
     .
     .
     .
nonzeros(west0479)
ans =

   1.0000e+00
  -3.7648e-02
  -3.4424e-01
   1.0000e+00
  -2.4523e-02
  -3.7371e-01
   1.0000e+00
  -3.6613e-02
  -8.3694e-01
   1.3000e+02
    .
    .
    .

Примечание

Используйте Ctrl+C, чтобы остановить nonzeros, перечисляющий в любое время.

Обратите внимание на то, что первоначально nnz имеет то же значение как nzmax по умолчанию. Таким образом, количество ненулевых элементов эквивалентно количеству мест хранения, выделенных для ненулей. However, MATLAB® динамически не выпускает память, если вы обнуляете дополнительные элементы массива. Изменение значения некоторых элементов матрицы, чтобы обнулить изменяет значение nnz, но не тот из nzmax.

Однако можно добавить столько ненулевых элементов в матрицу сколько желаемый. Вы не ограничиваетесь исходным значением nzmax.

Индексы и значения

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

[i,j,s] = find(S);

find возвращает индексы строки ненулевых значений в векторном i, индексов столбца в векторном j и самих ненулевых значений в векторном s. Пример ниже использует find, чтобы определить местоположение индексов и значений ненулей в разреженной матрице. Функция sparse использует find вывод, вместе с размером матрицы, чтобы воссоздать матрицу.

S1 = west0479;
[i,j,s] = find(S1);
[m,n] = size(S1);
S2 = sparse(i,j,s,m,n);

Индексация в операциях разреженной матрицы

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

B = speye(4);
[i,j,s] = find(B);
[i,j,s]
ans =

     1     1     1
     2     2     1
     3     3     1
     4     4     1
B(3,1) = 42;
[i,j,s] = find(B);
[i,j,s]
ans =

     1     1     1
     3     1    42
     2     2     1
     3     3     1
     4     4     1
В порядке сохранить новую матрицу 42 в (3,1), MATLAB вставляет дополнительную строку в ненулевые значения векторные и нижние векторы, затем переключает все матричные значения после (3,1).

Использование линейной индексации, чтобы получить доступ или присвоить элемент в большой разреженной матрице перестанет работать, если линейный индекс превысит 2^48-1, который является текущей верхней границей для числа элементов, позволенного в матрице.

S = spalloc(2^30,2^30,2);
S(end) = 1
Maximum variable size allowed by the program is exceeded.

Чтобы получить доступ к элементу, линейный индекс которого больше, чем intmax, используйте индексацию массива:

S(2^30,2^30) = 1
S =

         (1073741824,1073741824)              1

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

n = 10000;
A = 4*speye(n);
Изменение элементов A в цикле берет, медленнее, чем подобная векторизованная операция:
tic
A(1:n-1,n) = -1; 
A(n,1:n-1) = -1; 
toc
Elapsed time is 0.003344 seconds.
tic
for k = 1:n-1
  C(k,n) = -1; 
  C(n,k) = -1; 
end
toc
Elapsed time is 0.448069 seconds.
Поскольку MATLAB хранит разреженные матрицы в сжатом разреженном формате столбца, он должен переключить многократные въезды в A во время каждого, проходят через цикл.

Предварительное выделение памяти для разреженной матрицы и затем заполнение ее поэлементным способом так же вызывают существенное количество издержек в индексации в разреженный массив:

S1 = spalloc(1000,1000,100000);
tic;
for n = 1:100000
    i = ceil(1000*rand(1,1));
    j = ceil(1000*rand(1,1));
    S1(i,j) = rand(1,1);
end
toc
Elapsed time is 2.577527 seconds.

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

i = ceil(1000*rand(100000,1));
j = ceil(1000*rand(100000,1));
v = zeros(size(i));
for n = 1:100000
    v(n) = rand(1,1);
end

tic;
S2 = sparse(i,j,v,1000,1000);
toc
Elapsed time is 0.017676 seconds.

По этой причине, лучше создавать разреженные матрицы целиком с помощью функции конструкции, как функции spdiags или sparse.

Например, предположите, что вы хотели разреженную форму координатного матричного C:

C     =   (4000104001004010101014114)

Создайте матрицу с пятью столбцами непосредственно с функцией sparse использование пар триплета для индексов строки, индексов столбца и значений:

i = [1 5 2 5 3 5 4 5 1 2 3 4 5]';
j = [1 1 2 2 3 3 4 4 5 5 5 5 5]';
s = [4 1 4 1 4 1 4 1 -1 -1 -1 -1 4]';
C = sparse(i,j,s)
C =

   (1,1)        4
   (5,1)        1
   (2,2)        4
   (5,2)        1
   (3,3)        4
   (5,3)        1
   (4,4)        4
   (5,4)        1
   (1,5)       -1
   (2,5)       -1
   (3,5)       -1
   (4,5)       -1
   (5,5)        4
Упорядоченное расположение значений в выводе отражает базовую систему хранения столбцами. Для получения дополнительной информации о том, как MATLAB хранит разреженные матрицы, смотрите Джона Р. Гильберта, Клив Молер и Разреженные матрицы Роберта Шрайбера В MATLAB: Разработка и реализация, (SIAM Journal на Анализе матрицы и Приложения, 13:1, 333–356 (1992)).

Визуализация разреженных матриц

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

Например:

Загрузите предоставленную разреженную матрицу west0479, один из набора Харуэлла-Boeing.

load west0479

Просмотрите структуру разреженности.

spy(west0479)

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

Похожие темы

Для просмотра документации необходимо авторизоваться на сайте