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

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

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

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

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

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

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

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

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

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

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

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

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

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

создает разреженную матрицу размером (n+1)×(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 определена, то диагонали этой матрицы заменяются. В противном случае создается матрица размером m×n с диагоналями, заданными столбцами 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) ¶

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

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

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

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

: r = spones (S) ¶

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

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

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

: s = sprand (m, n, d) ¶

: s = sprand (m, n, d, rc) ¶

: s = sprand (s) ¶

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

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

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

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

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

: s = sprandn (m, n, d) ¶

: s = sprandn (m, n, d, rc) ¶

: s = sprandn (s) ¶

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

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

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

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

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

: S = sprandsym (n, d) ¶

: S = sprandsym (s) ¶

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

Размер матрицы будет n×n, с плотностью значений 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);

создает разреженную матрицу r×c со случайным распределением 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) ¶

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