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 ([m, n]) ¶

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

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

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

См. также: 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) ¶

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

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

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

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

Создать симметричную разреженную случайную матрицу.

Размер матрицы будет nxn, с плотностью значений, заданной d. d должно быть от 0 до 1 включительно. Значения будут распределены нормально со средним значением ноль и дисперсией 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 (m, n) ¶

: S = sparse (i, j, sv) ¶

: S = sparse (i, j, sv, m, n) ¶

: S = sparse (i, j, sv, m, n, "unique") ¶

: S = sparse (i, j, sv, m, n, nzmax) ¶

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

Если A — полная матрица, преобразовать её в разреженное представление матрицы, удалив при этом все нулевые значения. Матрица A должна быть логического или вещественного типа.

Если указаны два входных параметра m (строки) и n (столбцы), то создать пустую разреженную матрицу с указанными размерами.

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

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

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

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

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

Необязательный заключительный аргумент резервирует место для nzmax значений в разреженном массиве и полезен, если окончательное количество ненулевых значений будет больше, чем количество значений в sv, используемых при первоначальном создании массива. См. spalloc для получения дополнительной информации и инструкций по использованию.

Пример 1 (преобразование полной матрицы в разреженную для экономии памяти):

x = full (diag (1:1000));
sizeof (x)
⇒  8000000
s = sparse (x);
sizeof (xs)
⇒  24008

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

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

Пример 3 (параметр "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 представляет собой трёх- или четырёхстолбцовую вещественную матрицу, содержащую строку, столбец, вещественную и мнимую части элементов разреженной матрицы. Элемент с нулевой вещественной и мнимой частью может использоваться для принудительного задания определённого размера матрицы.

См. также: sparse.

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