GNU Octave Manual Version 3 by John W. Eaton, David Bateman, Søren Hauberg Paperback (6"x9"), 568 pages ISBN 095461206X RRP £24.95 ($39.95) Get a printed copy>>>

GNU Octave Manual Version 3 Buy the book here >>> learn more

20.1.5 Graphical Representations of Sparse Matrices

The functions described in this section display sparse matrices graphically. The spy command displays the structure of the non-zero elements of the matrix. More advanced graphical information can be obtained with the treeplot, etreeplot and gplot commands.

Function File: spy (x)

Function File: spy (..., markersize)

Function File: spy (..., LineSpec)

Plot the sparsity pattern of the sparse matrix x. If the argument markersize is given as an scalar value, it is used to determine the point size in the plot. If the string LineSpec is given it is passed to plot and determines the appearance of the plot.

See also plot

Figure 20-1: Structure of simple sparse matrix displayed with spy.

One use of sparse matrices is in graph theory, where the interconnections between nodes are represented as an adjacency matrix. That is, if the i-th node in a graph is connected to the j-th node. Then the ij-th node (and in the case of undirected graphs the ji-th node) of the sparse adjacency matrix is non-zero. If each node is then associated with a set of co-ordinates, then the gplot command can be used to graphically display the interconnections between nodes.

Function File: gplot (a, xy)

Function File: gplot (a, xy, line_style)

Function File: [x, y] = gplot (a, xy)

Plot a graph defined by A and xy in the graph theory sense. A is the adjacency matrix of the array to be plotted and xy is an n-by-2 matrix containing the coordinates of the nodes of the graph.

The optional parameter line_style defines the output style for the plot. Called with no output arguments the graph is plotted directly. Otherwise, return the coordinates of the plot in x and y.

See also treeplot, etreeplot, spy

As a trivial example of the use of gplot, consider the example

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)

which creates an adjacency matrix A where node 1 is connected to nodes 2 and 6, node 2 with nodes 1 and 3, etc. The co-ordinates of the nodes are given in the n-by-2 matrix xy.

The dependencies between the nodes of a Cholesky factorization can be calculated in linear time without explicitly needing to calculate the Cholesky factorization. The etree command returns the elimination tree of the matrix. It can be displayed graphically with treeplot(etree(A)) if A is symmetric or treeplot(etree(A+A')) otherwise.

Loadable Function: p = etree (s)

Loadable Function: p = etree (s, typ)

Loadable Function: [p, q] = etree (s, typ)

Returns the elimination tree for the matrix s. By default s is assumed to be symmetric and the symmetric elimination tree is returned. The argument typ controls whether a symmetric or column elimination tree is returned. Valid values of typ are 'sym' or 'col', for symmetric or column elimination tree respectively

Called with a second argument, etree also returns the postorder permutations on the tree.

Function File: etreeplot (tree)

Function File: etreeplot (tree, node_style, edge_style)

Plot the elimination tree of the matrix s or s+s' if s in non-symmetric. The optional parameters line_style and edge_style define the output style.

See also treeplot, gplot

Function File: treeplot (tree)

Function File: treeplot (tree, line_style, edge_style)

Produces a graph of a tree (or forest). The first argument is a vector of predecessors, optional parameters line_style and edge_style define the output style. The vector tree is constructed by regarding each element of the vector as a node, and storing the index of the parent node in the element. For example, if node i is the parent of j, set tree(j) = i. The complexity of the algorithm is O(n) in terms of time and memory requirements.

See also etreeplot, gplot