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.