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.

Рисунок 22.1: Структура простой разреженной матрицы.

Одно из применений разреженных матриц — в теории графов, где взаимосвязи между узлами представлены как матрица смежности. То есть, если 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.

Рисунок 22.2: Простой пример использования команды gplot.

Зависимости между узлами факторизации Холецкого могут быть вычислены за линейное время без явного вычисления факторизации Холецкого командой 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 — матрица размером nx2, содержащая координаты узлов графа.

Необязательный параметр 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.