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

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

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

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

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

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

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

Примечание

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

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

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

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

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

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

find возвращает индексы строк ненулевых значений в векторе i, индексы столбцов в векторных j, и самих ненулевых значений в векторе s. В приведенном ниже примере используются find для определения местоположения индексов и значений nonzeros в разреженной матрице. 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.

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

Например, предположим, что вам нужна разреженная форма матрицы координат 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 хранит разреженные матрицы, см. John R. Gilbert, Cleve Moler, и Robert Schreiber's Sparse Matrices In MATLAB: Проект и Реализация, (SIAM Journal по матричному анализу и приложениям, 13:1, 333-356 (1992))).

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

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

Для примера:

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

load west0479

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

spy(west0479)

Figure contains an axes. The axes contains an object of type line.

См. также

Похожие темы

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