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, которая отображает структуру ненулевых элементов матрицы. Пример использования команды spy см. на рисунке 22.1. Более подробную графическую информацию можно получить с помощью команд 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 — матрица размера 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.