- publishing free software manuals
 GNU Octave Manual Version 3 by John W. Eaton, David Bateman, Søren HaubergPaperback (6"x9"), 568 pagesISBN 095461206XRRP £24.95 (\$39.95)

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.

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.

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.

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.