Using MATLAB (779505), страница 68
Текст из файла (страница 68)
It is a tridiagonal matrix with -2s on the diagonal and 1s onthe super- and subdiagonal. There are many ways to generate it – here’s onepossibility.D = sparse(1:n,1:n,-2∗ones(1,n),n,n);E = sparse(2:n,1:n-1,ones(1,n-1),n,n);S = E+D+E'For n = 5, MATLAB responds withS =(1,1)(2,1)(1,2)(2,2)(3,2)(2,3)(3,3)(4,3)(3,4)(4,4)-211-211-211-216-916Sparse Matrices(5,4)(4,5)(5,5)11-2Now F = full(S) displays the corresponding full matrix.F = full(S)F =-210001-210001-210001-210001-2Creating Sparse Matrices from Their Diagonal ElementsCreating sparse matrices based on their diagonal elements is a commonoperation, so the function spdiags handles this task.
Its syntax isS = spdiags(B,d,m,n)To create an output matrix S of size m-by-n with elements on p diagonals:• B is a matrix of size min(m,n)-by-p. The columns of B are the values topopulate the diagonals of S.• d is a vector of length p whose integer elements specify which diagonals of Sto populate.That is, the elements in column j of B fill the diagonal specified by element jof d.Note If a column of B is longer than the diagonal it’s replacing,super-diagonals are taken from the lower part of the column of B, andsub-diagonals are taken from the upper part of the column of B.16-10IntroductionAs an example, consider the matrix B and the vector d.B = [ 4152637411223344001324 ];d = [-302];Use these matrices to create a 7-by-4 sparse matrix A.A = spdiags(B,d,7,4)A =(1,1)(4,1)(2,2)(5,2)(1,3)(3,3)(6,3)(2,4)(4,4)(7,4)11412252133363244474In its full form, A looks like this.full(A)ans =1100410000220052001303300630024044007416-1116Sparse Matricesspdiags can also extract diagonal elements from a sparse matrix, or replacematrix diagonal elements with new values.
Type help spdiags for details.Importing Sparse Matrices from Outside MATLABYou can import sparse matrices from computations outside MATLAB. Use thespconvert function in conjunction with the load command to import text filescontaining lists of indices and nonzero elements. For example, consider athree-column text file T.dat whose first column is a list of row indices, secondcolumn is a list of column indices, and third column is a list of nonzero values.These statements load T.dat into MATLAB and convert it into a sparsematrix S:load T.datS = spconvert(T)The save and load commands can also process sparse matrices stored as binarydata in MAT-files.16-12Viewing Sparse MatricesViewing Sparse MatricesMATLAB provides a number of functions that let you get quantitative orgraphical 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 elementsInformation About Nonzero ElementsThere are several commands that provide high-level information about thenonzero 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 asparse matrix.• nzmax returns the amount of storage space allocated for the nonzero entriesof a sparse matrix.To try some of these, load the supplied sparse matrix west0479, one of theHarwell-Boeing collection.load west0479whosNamewest0479SizeBytesClass479x47924576sparse arrayThis matrix models an eight-stage chemical distillation column.Try these commands.nnz(west0479)ans =1887format short e16-1316Sparse Matriceswest0479west0479 =(25,1)(31,1)(87,1)(26,2)(31,2)(88,2)(27,3)(31,3)(89,3)(28,4)...1.0000e+00-3.7648e-02-3.4424e-011.0000e+00-2.4523e-02-3.7371e-011.0000e+00-3.6613e-02-8.3694e-011.3000e+02nonzeros(west0479);ans =1.0000e+00-3.7648e-02-3.4424e-011.0000e+00-2.4523e-02-3.7371e-011.0000e+00-3.6613e-02-8.3694e-011.3000e+02...Note Use Ctrl+C to stop the nonzeros listing at any time.16-14Viewing Sparse MatricesNote that initially nnz has the same value as nzmax by default.
That is, thenumber of nonzero elements is equivalent to the number of storage locationsallocated for nonzeros. However, MATLAB does not dynamically releasememory if you zero out additional array elements. Changing the value of somematrix 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. Youare not constrained by the original value of nzmax.Viewing Sparse Matrices GraphicallyIt is often useful to use a graphical format to view the distribution of thenonzero elements within a sparse matrix. MATLAB’s spy function produces atemplate view of the sparsity structure, where each point on the graphrepresents the location of a nonzero array element.For example,spy(west0479)0501001502002503003504004500100200300nz = 188740016-1516Sparse MatricesThe find Function and Sparse MatricesFor any matrix, full or sparse, the find function returns the indices and valuesof nonzero elements.
Its syntax is[i,j,s] = find(S)find returns the row indices of nonzero values in vector i, the column indicesin vector j, and the nonzero values themselves in the vector s. The examplebelow uses find to locate the indices and values of the nonzeros in a sparsematrix.
The sparse function uses the find output, together with the size of thematrix, to recreate the matrix.[i,j,s] = find(S)[m,n] = size(S)S = sparse(i,j,s,m,n)16-16Example: Adjacency Matrices and GraphsExample: Adjacency Matrices and GraphsThis section includes:• An introduction to adjacency matrices• Instructions for graphing adjacency matrices with gplot• A Bucky ball example, including information about using spy plots toillustrate fill-in and distance• An airflow model exampleIntroduction to Adjacency MatricesThe formal mathematical definition of a graph is a set of points, or nodes, withspecified connections between them. An economic model, for example, is agraph with different industries as the nodes and direct economic ties as theconnections.
The computer software industry is connected to the computerhardware industry, which, in turn, is connected to the semiconductor industry,and so on.This definition of a graph lends itself to matrix representation. The adjacencymatrix of an undirected graph is a matrix whose (i,j)th and (j,i)th entriesare 1 if node i is connected to node j, and 0 otherwise.
For example, theadjacency matrix for a diamond-shaped graph looks like1A=0101101001011010423Since most graphs have relatively few connections per node, most adjacencymatrices are sparse. The actual locations of the nonzero elements depend onhow the nodes are numbered. A change in the numbering leads to permutation16-1716Sparse Matricesof the rows and columns of the adjacency matrix, which can have a significanteffect on both the time and storage requirements for sparse matrixcomputations.Graphing Using Adjacency MatricesMATLAB’s gplot function creates a graph based on an adjacency matrix and arelated array of coordinates. To try gplot, create the adjacency matrix shownabove by enteringA = [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 forthe corresponding node.
For the diamond example, create the array by enteringxy = [1 3; 2 1; 3 3; 2 5];This places the first node at location (1,3), the second at location (2,1), thethird at location (3,3), and the fourth at location (2,5). To view the resultinggraph, entergplot(A,xy)The Bucky BallOne interesting construction for graph analysis is the Bucky ball. This iscomposed of 60 points distributed on the surface of a sphere in such a way thatthe distance from any point to its nearest neighbors is the same for all thepoints. Each point has exactly three neighbors. The Bucky ball models fourdifferent physical objects:• The geodesic dome popularized by Buckminster Fuller• The C60 molecule, a form of pure carbon with 60 atoms in a nearly sphericalconfiguration• In geometry, the truncated icosahedron• In sports, the seams in a soccer ballThe Bucky ball adjacency matrix is a 60-by-60 symmetric matrix B.
B has threenonzero elements in each row and column, for a total of 180 nonzero values.This matrix has important applications related to the physical objects listedearlier. For example, the eigenvalues of B are involved in studying the chemicalproperties of C60.16-18Example: Adjacency Matrices and GraphsTo obtain the Bucky ball adjacency matrix, enterB = bucky;At order 60, and with a density of 5%, this matrix does not require sparsetechniques, but it does provide an interesting example.You can also obtain the coordinates of the Bucky ball graph using[B,v] = bucky;This statement generates v, a list of xyz-coordinates of the 60 points in 3-spaceequidistributed on the unit sphere.
The function gplot uses these points to plotthe Bucky ball graph.gplot(B,v)axis equal0.80.60.40.20−0.2−0.4−0.6−0.8−1−0.500.51It is not obvious how to number the nodes in the Bucky ball so that theresulting adjacency matrix reflects the spherical and combinatorialsymmetries of the graph.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
