22.1.3 Получение информации о разреженных матрицах ¶

Существует ряд функций, позволяющих получить информацию о разреженных матрицах. Наиболее базовая из них — issparse, которая определяет, является ли конкретный объект Octave разреженной матрицей.

Ещё одна очень базовая функция — nnz, которая возвращает количество ненулевых элементов в разреженной матрице, а функция nzmax возвращает количество выделенной памяти для хранения разреженной матрицы. Обратите внимание, что Octave обычно освобождает неиспользуемую память при первой же возможности для разреженных объектов. В некоторых случаях, при создании разреженных объектов пользователем, значение, возвращаемое nzmax, может отличаться от значения nnz, но в общем случае они дадут одинаковый результат. Функция spstats возвращает некоторые базовые статистические данные по столбцам разреженной матрицы, включая количество элементов, среднее значение и дисперсию каждого столбца.

: tf = issparse (x) ¶

Возвращает true, если x является разреженной матрицей.

См. также: ismatrix.

: n = nnz (A) ¶

Возвращает количество ненулевых элементов в A.

См. также: nzmax, nonzeros, find.

: v = nonzeros (A) ¶

Возвращает столбец ненулевых значений матрицы A.

См. также: find, nnz.

: n = nzmax (SM) ¶

Возвращает количество выделенной памяти для хранения разреженной матрицы SM.

Примечание по программированию: Octave стремится освободить неиспользуемую память при первой же возможности для разреженных объектов. Таким образом, в общем случае значение nzmax будет таким же, как nnz, за исключением некоторых случаев создания разреженных объектов пользователем.

Также обратите внимание, что Octave всегда резервирует память как минимум для одного значения. Таким образом, для пустых матриц nnz будет возвращать 0, но nzmax вернёт 1.

См. также: nnz, spalloc, sparse.

: [count, mean, var] = spstats (S) ¶

: [count, mean, var] = spstats (S, j) ¶

Возвращает статистические данные для ненулевых элементов разреженной матрицы S.

count — количество ненулевых элементов в каждом столбце, mean — среднее значение ненулевых элементов в каждом столбце, а var — дисперсия ненулевых элементов в каждом столбце.

При вызове с двумя входными аргументами, если S — данные, а j — номер интервала данных, вычисляются статистические данные для каждого интервала. В этом случае интервалы могут содержать нулевые значения, в то время как с spstats (S) нули могут быть исключены.

При решении линейных уравнений, включающих разреженные матрицы, Octave определяет способ решения уравнения на основе типа матрицы (см. Линейная алгебра для разреженных матриц). Octave исследует тип матрицы при первом использовании операторов div (/) или ldiv (\) с матрицей и затем кэширует тип. Однако функцию matrix_type можно использовать для определения типа разреженной матрицы до использования операторов div или ldiv. Например,

a = tril (sprandn (1024, 1024, 0.02), -1) ...
    + speye (1024);
matrix_type (a);
ans = Lower

показывает, что Octave правильно определяет тип матрицы для нижних треугольных матриц. matrix_type также можно использовать для принудительного задания типа матрицы.

a = matrix_type (tril (sprandn (1024, ...
   1024, 0.02), -1) + speye (1024), "Lower");

Это позволяет избежать затрат на определение типа матрицы. Однако неправильное определение типа матрицы приведёт к неверным результатам при решении линейных уравнений, поэтому пользователь несёт полную ответственность за правильное определение типа матрицы.

Существует несколько графических способов получения информации о разреженных матрицах. Первый — команда spy, которая отображает структуру ненулевых элементов матрицы. Смотрите Рисунок 22.1 для примера использования spy. Более сложную графическую информацию можно получить с помощью команд treeplot, etreeplot и gplot.

Одно из применений разреженных матриц — в теории графов, где связи между узлами представлены в виде матрицы смежности. То есть, если i-й узел в графе соединён с j-м узлом, то ij-й элемент (и, в случае неориентированных графов, ji-й элемент) разреженной матрицы смежности ненулевой. Если каждому узлу присвоен набор координат, то команда gplot может быть использована для графического отображения связей между узлами.

В качестве тривиального примера использования gplot рассмотрим пример:

A = sparse ([2,6,1,3,2,4,3,5,4,6,1,5],
    [1,1,2,2,3,3,4,4,5,5,6,6],1,6,6);
xy = [0,4,8,6,4,2;5,0,5,7,5,7]';
gplot (A,xy)

который создаёт матрицу смежности A, где узел 1 соединён с узлами 2 и 6, узел 2 с узлами 1 и 3 и так далее. Координаты узлов заданы в матрице n×2 xy. См. Рисунок 22.2.

Зависимости между узлами разложения Холецкого могут быть рассчитаны за линейное время без явного расчёта разложения Холецкого с помощью команды etree. Эта команда возвращает дерево устранения матрицы и может быть визуализирована с помощью команды treeplot (etree (A)), если A является симметричной, или treeplot (etree (A+A')) в противном случае.

: spy (x) ¶

: spy (…, markersize) ¶

: spy (…, line_spec) ¶

Строит график структуры разреженности разреженной матрицы x.

Если указан необязательный числовой аргумент markersize, он определяет размер маркеров на графике.

Если указана необязательная строка line_spec, она передаётся в plot и определяет внешний вид графика.

См. также: plot, gplot.

: p = etree (S) ¶

: p = etree (S, typ) ¶

: [p, q] = etree (S, typ) ¶

Возвращает дерево устранения для матрицы S.

По умолчанию S предполагается симметричной и возвращается симметричное дерево устранения. Аргумент typ управляет тем, симметричное или столбцовое дерево устранения возвращается. Допустимые значения typ — "sym" или "col", соответственно для симметричного и столбцового деревьев устранения.

При вызове с вторым аргументом, etree возвращает также постфиксные перестановки на дереве.

: etreeplot (A) ¶

: etreeplot (A, node_style, edge_style) ¶

Постройте дерево исключения матрицы A или A+A' если A несимметрична.

Необязательные параметры node_style и edge_style определяют стиль вывода.

См. также: treeplot, gplot.

: gplot (A, xy) ¶

: gplot (A, xy, line_style) ¶

: [x, y] = gplot (A, xy) ¶

Построить график, определённый A и xy в смысле теории графов.

A — матрица смежности отображаемого массива, а xy — матрица n×2, содержащая координаты узлов графика.

Необязательный параметр line_style определяет стиль вывода графика. При вызове без выходных аргументов график отображается непосредственно. В противном случае возвращает координаты графика в x и y.

См. также: treeplot, etreeplot, spy.

: treeplot (tree) ¶

: treeplot (tree, node_style, edge_style) ¶

Построение графика дерева или леса.

Первый аргумент — вектор предшественников.

Необязательные параметры node_style и edge_style определяют стиль вывода графика.

Сложность алгоритма — O(n) по времени и памяти.

См. также: etreeplot, gplot.

: [x, y] = treelayout (tree) ¶

: [x, y] = treelayout (tree, permutation) ¶

: [x, y, h, s] = treelayout (…) ¶

treelayout выстраивает дерево или лес.

Первый аргумент tree — вектор предшественников.

Необязательный параметр permutation — постфиксная перестановка.

Сложность алгоритма — O(n) по времени и памяти.

См. также: etreeplot, gplot, treeplot.