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