Using MATLAB (779505), страница 69
Текст из файла (страница 69)
The numbering used by bucky.m is based on thepentagons inherent in the ball’s structure.16-1916Sparse MatricesThe vertices of one pentagon are numbered 1 through 5, the vertices of anadjacent pentagon are numbered 6 through 10, and so on. The picture on thefollowing page shows the numbering of half of the nodes (one hemisphere); thenumbering of the other hemisphere is obtained by a reflection about theequator. Use gplot to produce a graph showing half the nodes.
You can add thenode numbers using a for loop.k = 1:30;gplot(B(k,k),v);axis squarefor j = 1:30, text(v(j,1),v(j,2), int2str(j)); end11415130.8181711120.60.419162200.2103901−0.2226485−0.423721−0.626243025−0.827−1−1−0.8−0.6−0.4−0.2029280.20.40.60.81To view a template of the nonzero locations in the Bucky ball’s adjacencymatrix, use the spy function:spy(B)16-20Example: Adjacency Matrices and Graphs01020304050600102030nz = 180405060The node numbering that this model uses generates a spy plot with 12 groupsof five elements, corresponding to the 12 pentagons in the structure. Each nodeis connected to two other nodes within its pentagon and one node in some otherpentagon.
Since the nodes within each pentagon have consecutive numbers,most of the elements in the first super- and sub-diagonals of B are nonzero. Inaddition, the symmetry of the numbering about the equator is apparent in thesymmetry of the spy plot about the antidiagonal.Graphs and Characteristics of Sparse MatricesSpy plots of the matrix powers of B illustrate two important concepts related tosparse matrix operations, fill-in and distance.
spy plots help illustrate theseconcepts.spy(B^2)spy(B^3)spy(B^4)spy(B^8)16-2116Sparse Matrices0010102020303040405050606002040nz = 4206000101020203030404050506002040nz = 7806002040nz = 3540606002040nz = 138060Fill-in is generated by operations like matrix multiplication. The product oftwo or more matrices usually has more nonzero entries than the individualterms, and so requires more storage. As p increases, B^p fills in and spy(B^p)gets more dense.The distance between two nodes in a graph is the number of steps on the graphnecessary to get from one node to the other.
The spy plot of the p-th power of Bshows the nodes that are a distance p apart. As p increases, it is possible to getto more and more nodes in p steps. For the Bucky ball, B^8 is almost completelyfull. Only the antidiagonal is zero, indicating that it is possible to get from anynode to any other node, except the one directly opposite it on the sphere, ineight steps.16-22Example: Adjacency Matrices and GraphsAn Airflow ModelA calculation performed at NASA’s Research Institute for Applications ofComputer Science involves modeling the flow over an airplane wing with twotrailing flaps.10.90.80.70.60.50.40.30.20.1000.10.20.30.40.50.60.70.80.91In a two-dimensional model, a triangular grid surrounds a cross section of thewing and flaps.
The partial differential equations are nonlinear and involveseveral unknowns, including hydrodynamic pressure and two components ofvelocity. Each step of the nonlinear iteration requires the solution of a sparselinear system of equations. Since both the connectivity and the geometriclocation of the grid points are known, the gplot function can produce the graphshown above.In this example, there are 4253 grid points, each of which is connected tobetween 3 and 9 others, for a total of 28831 nonzeros in the matrix, and adensity equal to 0.0016.
This spy plot shows that the node numbering yields adefinite band structure.16-2316Sparse MatricesThe Laplacian of the mesh.0 ........................................5001000150020002500300035004000.. ............................................... .............. . .
... . ..................................................................................... .. ..... . .... .... ............ ......................................... . ...... . .............................................................. .. ... ...
. . .......................... ... .. ... .... . ........................ .. . . .............. . ....................................... .. ... ........ ............................................ ... . ... .. .. ....... ................................... .... . . ........................... ...... .. ... ..................................................... . .... ........................................
........ ............................................. .. ....................... ............................................................... .................................... .. .. ............................... . ....... .... . . .. . ..... ................................................... ...... . .. ... .............................................. .. .
... .. ................................................ . . . . ... . .. ..... ... .. ................................................ .. ....... .. . . .. . ... .. ....................................................... ............. .... . ... ......................... ........................................................................... . . .. . .. .. .. .. ........................ .. .
.. . . . .. .. .. . . ................................................................. . ... . ........................................................... .. ...................................................... .. . .... . ............. .... ... .. . .. .
. ... .............................................. ........ .. .. . .. .. . .. ..... ... ... . .... ......................................................... . .. . . .. .................................................. .. . .................. ... ... ................................ . . .. . ....
. .. . . ....................................................... ...... ..... .............................................. .. .............. .... . .. .. ............................................................. . ................................ . . ................................................................ .
........................... . .................. ....010002000nz = 2883116-2430004000Sparse Matrix OperationsSparse Matrix OperationsMost of MATLAB’s standard mathematical functions work on sparse matricesjust as they do on full matrices. In addition, MATLAB provides a number offunctions that perform operations specific to sparse matrices.
This sectiondiscusses:• Computational considerations• Standard mathematical operations• Permutation and reordering• Factorization• Simultaneous linear equations• Eigenvalues and singular valuesComputational ConsiderationsThe computational complexity of sparse operations is proportional to nnz, thenumber of nonzero elements in the matrix. Computational complexity alsodepends linearly on the row size m and column size n of the matrix, but isindependent of the product m*n, the total number of zero and nonzero elements.The complexity of fairly complicated operations, such as the solution of sparselinear equations, involves factors like ordering and fill-in, which are discussedin the previous section.
In general, however, the computer time required for asparse matrix operation is proportional to the number of arithmetic operationson nonzero quantities.Standard Mathematical OperationsSparse matrices propagate through computations according to these rules:• Functions that accept a matrix and return a scalar or vector always produceoutput in full storage format. For example, the size function always returnsa full vector, whether its input is full or sparse.• Functions that accept scalars or vectors and return matrices, such as zeros,ones, rand, and eye, always return full results.
This is necessary to avoidintroducing sparsity unexpectedly. The sparse analog of zeros(m,n) issimply sparse(m,n). The sparse analogs of rand and eye are sprand andspeye, respectively. There is no sparse analog for the function ones.16-2516Sparse Matrices• Unary functions that accept a matrix and return a matrix or vector preservethe storage class of the operand.
If S is a sparse matrix, then chol(S) is alsoa sparse matrix, and diag(S) is a sparse vector. Columnwise functions suchas max and sum also return sparse vectors, even though these vectors may beentirely nonzero. Important exceptions to this rule are the sparse and fullfunctions.• Binary operators yield sparse results if both operands are sparse, and fullresults if both are full. For mixed operands, the result is full unless theoperation preserves sparsity. If S is sparse and F is full, then S+F, S*F, andF\S are full, while S.*F and S&F are sparse. In some cases, the result mightbe sparse even though the matrix has few zero elements.• Matrix concatenation using either the cat function or square bracketsproduces sparse results for mixed operands.• Submatrix indexing on the right side of an assignment preserves the storageformat of the operand unless the result is a scalar.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
