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