Документация

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

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

Чтобы попробовать некоторые из них, загрузите предоставленную разреженную матрицу west0479, одна из коллекции Harwell-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
    .
    .
    .

Обратите внимание, что изначально nnz имеет то же значение, что и nzmax по умолчанию. То есть количество ненулевых элементов эквивалентно количеству складов, выделенных для ненулевых. Однако при обнулении дополнительных элементов массива 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

Использование линейного индексирования для доступа или назначения элемента в большой разреженной матрице приведет к сбою, если линейный индекс превысит 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);

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.

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

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.

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

Например, предположим, что требуется разреженная форма матрицы координат C:

Создайте матрицу из пяти столбцов непосредственно с помощью 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 spy функция создает шаблонное представление структуры разреженности, где каждая точка на графике представляет расположение ненулевого элемента массива.

Например:

Загрузить поставляемую разреженную матрицу west0479, одна из коллекции Harwell-Boeing.

load west0479

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

spy(west0479)