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

Существует несколько способов создания разреженных матриц.

Возвращаемое значение функции

Существует много функций, которые напрямую возвращают разреженные матрицы. К ним относятся speye, sprand, diag и т. д.

Созданные из матриц или векторов

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

Созданные и затем заполненные

Функции sparse или spalloc могут использоваться для создания пустой матрицы, которая затем заполняется пользователем.

Из пользовательской двоичной программы

Пользователь может напрямую создать разреженную матрицу в файле oct.

Существует несколько основных функций для возвращения конкретных разреженных матриц. Например, часто необходима единичная разреженная матрица. Поэтому для ее создания есть собственная функция speye (n) или speye (r, c), которая создает разреженную единичную матрицу размером nxn или rxc.

Другой типичной разреженной матрицей, которая часто необходима, является случайное распределение случайных элементов. Функции sprand и sprandn выполняют это для равномерного и нормального распределения элементов. У них одинаковая схема вызова, где sprand (r, c, d), создает разреженную матрицу размером rxc с плотностью заполненных элементов d.

Другие интересные функции, которые напрямую создают разреженные матрицы, — это diag или ее обобщение spdiags, которые могут принять определение диагоналей матрицы и создать разреженную матрицу, соответствующую этому. Например,

s = diag (sparse (randn (1,n)), -1);

создает разреженную матрицу размером (n+1)x(n+1) с одной определенной диагональю.

B = spdiags (A)

[B, d] = spdiags (A)

B = spdiags (A, d)

A = spdiags (v, d, A)

A = spdiags (v, d, m, n)

Обобщение функции diag.

При вызове с одним входным аргументом извлекаются ненулевые диагонали d матрицы A.

При вызове с двумя аргументами диагонали для извлечения задаются вектором d.

Другие две формы spdiags модифицируют входную матрицу, заменяя диагонали. Они используют столбцы v для замены диагоналей, представленных вектором d. Если разреженная матрица A определена, то диагонали этой матрицы заменяются. В противном случае создается матрица mxn с диагоналями, заданными столбцами v.

Отрицательные значения d представляют диагонали ниже главной диагонали, а положительные значения d — диагонали выше главной диагонали.

Например:

spdiags (reshape (1:12, 4, 3), [-1 0 1], 5, 4)
   ⇒ 5 10  0  0
      1  6 11  0
      0  2  7 12
      0  0  3  8
      0  0  0  4

См. также: diag.

s = speye (m, n)

s = speye (m)

s = speye (sz)

Возвращает единичную разреженную матрицу размера mxn.

Реализация значительно эффективнее, чем sparse (eye (m)), так как полная матрица не создается.

При вызове с одним аргументом создается квадратная матрица размера mxm. Если вызывается с одним векторным аргументом sz, этот аргумент используется для определения размера создаваемой матрицы.

См. также: sparse, spdiags, eye.

r = spones (S)

Заменяет ненулевые элементы S на единицы.

Это создает разреженную матрицу с такой же структурой, что и S.

См. также: sparse, sprand, sprandn, sprandsym, spfun, spy.

sprand (m, n, d)

sprand (m, n, d, rc)

sprand (s)

Генерирует разреженную матрицу со случайными значениями, равномерно распределенными.

Размер матрицы mxn с плотностью значений d. d должна быть в диапазоне от 0 до 1. Значения будут равномерно распределены в интервале (0, 1).

Если вызывается с одной матрицей в качестве аргумента, то генерируется разреженная матрица со случайными значениями, где матрица s ненулевая.

Если вызывается со скалярным четвертым аргументом rc, то генерируется случайная разреженная матрица с обратной условной числом rc. Если rc является вектором, то он определяет первые сингулярные значения генерируемой матрицы (length (rc) <= min (m, n)).

См. также: sprandn, sprandsym, rand.

sprandn (m, n, d)

sprandn (m, n, d, rc)

sprandn (s)

Генерирует разреженную матрицу со случайными значениями, имеющими нормальное распределение.

Размер матрицы mxn с плотностью значений d. d должна быть в диапазоне от 0 до 1. Значения будут иметь нормальное распределение со средним значением 0 и дисперсией 1.

Если вызывается с одной матрицей в качестве аргумента, то генерируется разреженная матрица со случайными значениями, где матрица s ненулевая.

Если вызывается со скалярным четвертым аргументом rc, то генерируется случайная разреженная матрица с обратной условной числом rc. Если rc является вектором, то он определяет первые сингулярные значения генерируемой матрицы (length (rc) <= min (m, n)).

См. также: sprand, sprandsym, randn.

sprandsym (n, d)

sprandsym (s)

Генерирует симметричную случайную разреженную матрицу.

Размер матрицы будет nxn с плотностью значений, заданной d. d должна быть в диапазоне от 0 до 1 включительно. Значения будут иметь нормальное распределение со средним значением 0 и дисперсией 1.

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

См. также: sprand, sprandn, spones, sparse.

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

ri = ci = d = [];
  for j = 1:c
    ri = [ri; randperm(r,n)'];
    ci = [ci; j*ones(n,1)];
    d = [d; rand(n,1)];
  endfor
  s = sparse (ri, ci, d, r, c);

создает разреженную матрицу rxc со случайным распределением n (<r) элементов на столбец. Элементы векторов не обязательно должны быть отсортированы в каком-либо определенном порядке, так как Octave отсортирует их перед сохранением данных. Однако предварительная сортировка данных ускорит создание разреженной матрицы.

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

s = spconvert ([1 2 3 4; 1 3 4 4; 1 2 3 0]')
⇒ Compressed Column Sparse (rows=4, cols=4, nnz=3)
      (1 , 1) -> 1
      (2 , 3) -> 2
      (3 , 4) -> 3

Пример создания и заполнения матрицы может быть:

k = 5;
nz = r * k;
s = spalloc (r, c, nz)
for j = 1:c
  idx = randperm (r);
  s (:, j) = [zeros(r - k, 1); ...
        rand(k, 1)] (idx);
endfor

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

FM = full (SM)

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

См. также: sparse, issparse.

s = spalloc (m, n, nz)

Создает разреженную матрицу размером mxn с предварительно выделенной памятью для не более чем nz ненулевых элементов.

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

• s(I:J) = x
• s(:,I:J) = x
• s(K:L,I:J) = x

и что выполняются следующие условия:

• присваивание не уменьшает nnz (S).
• после присваивания nnz (S) не превышает nz.
• никакой индекс не выходит за пределы.

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

Количество предварительно выделенной памяти для данной матрицы можно запросить с помощью функции nzmax.

Примечание по программированию: Octave всегда выделяет память для хотя бы одного значения, даже если nz равно 0.

См. также: nzmax, sparse.

s = sparse (a)

s = sparse (i, j, sv, m, n)

s = sparse (i, j, sv)

s = sparse (m, n)

s = sparse (i, j, s, m, n, "unique")

s = sparse (i, j, sv, m, n, nzmax)

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

Если a является полной матрицей, преобразовать её в представление разреженной матрицы, удалив все нулевые значения в процессе.

Исходя из целочисленных векторов индексов i и j, и вектора размером 1xnnz действительных или комплексных значений sv, построить разреженную матрицу S(i(k),j(k)) = sv(k) с общими размерами m и n. Если какой-либо из sv, i или j являются скалярами, они расширяются до общего размера.

Если m или n не указаны, их значения выводятся из максимального индекса в векторах i и j, как задано в m = max (i), n = max (j).

Примечание: если несколько значений заданы с одинаковыми индексами i и j, соответствующее значение в s будет суммой значений в повторяющейся позиции. См. accumarray для примера того, как получить другое поведение, например, взять минимум вместо суммы.

Если задан параметр "unique", и более одного значения заданы с одинаковыми индексами i и j, то будет использовано последнее заданное значение.

sparse (m, n) создаст пустую разреженную матрицу mxn и эквивалентна sparse ([], [], [], m, n)

Аргумент nzmax игнорируется, но принимается для совместимости с MATLAB.

Пример 1 (сумма в повторяющихся индексах):

i = [1 1 2]; j = [1 1 2]; sv = [3 4 5];
sparse (i, j, sv, 3, 4)
⇒
   Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

     (1, 1) ->  7
     (2, 2) ->  5

Пример 2 (параметр "unique"):

i = [1 1 2]; j = [1 1 2]; sv = [3 4 5];
sparse (i, j, sv, 3, 4, "unique")
⇒
   Compressed Column Sparse (rows = 3, cols = 4, nnz = 2 [17%])

     (1, 1) ->  4
     (2, 2) ->  5

См. также: full, accumarray, spalloc, spdiags, speye, spones, sprand, sprandn, sprandsym, spconvert, spfun.

x = spconvert (m)

Преобразовать простой формат разреженной матрицы, легко сгенерированный другими программами, во внутренний формат Octave.

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

См. также: sparse.

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