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 изменяют входную матрицу, заменяя диагонали. Для замены диагоналей, заданных вектором d, используются столбцы v. Если разреженная матрица 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])

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

Реализация значительно эффективнее, чем 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)

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

Размер матрицы — 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 (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 должна иметь логический тип или тип double.

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