22.1.3 Поиск информации о разреженных матрицах

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

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

: 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.

: treelayout (tree) ¶

: treelayout (tree, permutation) ¶

treelayout выполняет компоновку дерева или леса.

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

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

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

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