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.

: sprand (m, n, d) ¶

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

: sprand (s) ¶

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

Размер матрицы — m×n, плотность значений — 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) ¶

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

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

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

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

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

: sprandsym (n, d) ¶

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