wszyscy myślą, że to dno. ale na dnie tak nie wieje...
16-12
Viewing Sparse Matrices
Viewing Sparse Matrices
MATLAB provides a number of functions that let you get quantitative or
graphical information about sparse matrices.
This section provides information about:
• Obtaining information about nonzero elements
• Viewing graphs of sparse matrices
• Finding indices and values of nonzero elements
Information About Nonzero Elements
There are several commands that provide high-level information about the
nonzero elements of a sparse matrix:
• nnz returns the number of nonzero elements in a sparse matrix.
• nonzeros returns a column vector containing all the nonzero elements of a
sparse matrix.
• nzmax returns the amount of storage space allocated for the nonzero entries
of a sparse matrix.
To try some of these, load the supplied sparse matrix west0479, one of the
Harwell-Boeing collection.
load west0479
whos
Name Size Bytes Class
west0479 479x479 24576 sparse array
This matrix models an eight-stage chemical distillation column.
Try these commands.
nnz(west0479)
ans =
1887
format short e
16-13
16 Sparse Matrices
west0479
west0479 =
(25,1) 1.0000e+00
(31,1) -3.7648e-02
(87,1) -3.4424e-01
(26,2) 1.0000e+00
(31,2) -2.4523e-02
(88,2) -3.7371e-01
(27,3) 1.0000e+00
(31,3) -3.6613e-02
(89,3) -8.3694e-01
(28,4) 1.3000e+02
.
.
.
nonzeros(west0479);
ans =
1.0000e+00
-3.7648e-02
-3.4424e-01
1.0000e+00
-2.4523e-02
-3.7371e-01
1.0000e+00
-3.6613e-02
-8.3694e-01
1.3000e+02
.
.
.
Note Use Ctrl+C to stop the nonzeros listing at any time.
16-14
Viewing Sparse Matrices
Note that initially nnz has the same value as nzmax by default. That is, the
number of nonzero elements is equivalent to the number of storage locations
allocated for nonzeros. However, MATLAB does not dynamically release
memory if you zero out additional array elements. Changing the value of some
matrix elements to zero changes the value of nnz, but not that of nzmax.
However, you can add as many nonzero elements to the matrix as desired. You
are not constrained by the original value of nzmax.
Viewing Sparse Matrices Graphically
It is often useful to use a graphical format to view the distribution of the
nonzero elements within a sparse matrix. MATLAB’s spy function produces a
template view of the sparsity structure, where each point on the graph
represents the location of a nonzero array element.
For example,
spy(west0479)
0
50
100
150
200
250
300
350
400
450
0
100
200
300
400
nz = 1887
16-15
16 Sparse Matrices
The find Function and Sparse Matrices
For any matrix, full or sparse, the find function returns the indices and values
of nonzero elements. Its syntax is
[i,j,s] = find(S)
find returns the row indices of nonzero values in vector i, the column indices
in vector j, and the nonzero values themselves in the vector s. The example
below uses find to locate the indices and values of the nonzeros in a sparse
matrix. The sparse function uses the find output, together with the size of the
matrix, to recreate the matrix.
[i,j,s] = find(S)
[m,n] = size(S)
S = sparse(i,j,s,m,n)
16-16
Example: Adjacency Matrices and Graphs
Example: Adjacency Matrices and Graphs
This section includes:
• An introduction to adjacency matrices
• Instructions for graphing adjacency matrices with gplot
• A Bucky ball example, including information about using spy plots to
illustrate fill-in and distance
• An airflow model example
Introduction to Adjacency Matrices
The formal mathematical definition of a graph is a set of points, or nodes, with
specified connections between them. An economic model, for example, is a
graph with different industries as the nodes and direct economic ties as the
connections. The computer software industry is connected to the computer
hardware industry, which, in turn, is connected to the semiconductor industry,
and so on.
This definition of a graph lends itself to matrix representation. The adjacency
matrix of an undirected graph is a matrix whose (i,j)th and (j,i)th entries
are 1 if node i is connected to node j, and 0 otherwise. For example, the
adjacency matrix for a diamond-shaped graph looks like
1
A =
0 1 0 1
1 0 1 0
2
4
0 1 0 1
1 0 1 0
3
Since most graphs have relatively few connections per node, most adjacency
matrices are sparse. The actual locations of the nonzero elements depend on
how the nodes are numbered. A change in the numbering leads to permutation
16-17
16 Sparse Matrices
of the rows and columns of the adjacency matrix, which can have a significant
effect on both the time and storage requirements for sparse matrix
computations.
Graphing Using Adjacency Matrices
MATLAB’s gplot function creates a graph based on an adjacency matrix and a
related array of coordinates. To try gplot, create the adjacency matrix shown
above by entering
A = [0 1 0 1; 1 0 1 0; 0 1 0 1; 1 0 1 0];
The columns of gplot’s coordinate array contain the Cartesian coordinates for
the corresponding node. For the diamond example, create the array by entering
xy = [1 3; 2 1; 3 3; 2 5];
This places the first node at location (1,3), the second at location (2,1), the
third at location (3,3), and the fourth at location (2,5). To view the resulting
graph, enter
gplot(A,xy)
The Bucky Ball
One interesting construction for graph analysis is the Bucky ball. This is
composed of 60 points distributed on the surface of a sphere in such a way that
the distance from any point to its nearest neighbors is the same for all the
points. Each point has exactly three neighbors. The Bucky ball models four
different physical objects:
• The geodesic dome popularized by Buckminster Fuller
• The C60 molecule, a form of pure carbon with 60 atoms in a nearly spherical
configuration
• In geometry, the truncated icosahedron
• In sports, the seams in a soccer ball