Using MATLAB (779505), страница 67
Текст из файла (страница 67)
. . . . . . .ImportingSparseInformationMatrices fromGeneral Storage. .Outside. . . MATLAB. . . .Information About Nonzero Elements . . . . .ViewingSparseMatrices. . . . . . . . .Viewing SparseMatricesGraphicallyInformationAboutandNonzeroElementsThe find FunctionSparseMatrices . . . . .Viewing Sparse Matrices Graphically . . .
. .Thefind Functionand SparseMatrices. . . .Example:AdjacencyMatricesand GraphsGraphing Using Adjacency Matrices . . . . . .Example:The Bucky AdjacencyBall . . .Matrices. . . . and. . Graphs. . . . .Introductionto AdjacencyAn Airflow Model. . . Matrices. . . . . . . .
. .Graphing Using Adjacency Matrices . . . . . .TheBuckyBall Operations. . . . . . . . . . . . . .SparseMatrixAnAirflow Model. . . . . . . . . . . . .ComputationalConsiderationsStandard Mathematical Operations . . . . . .SparseMatrixPermutationandOperationsReordering . . . . . . . . .ComputationalFactorization Considerations. . . . . . . . .
. . . . . .StandardMathematicalOperations. . . . . . .SimultaneousLinear EquationsPermutationand SingularReordering. . . . . . . . .Eigenvalues andValuesFactorization . . . . . . . . . . . . . . .Simultaneous Linear Equations . . . . . . .Eigenvalues and Singular Values . . . . . . .Selected Bibliography......................................................................................................... 16-39-5. 9-5. 16-69-6. 16-69-10. 16-716-7.
9-11.16-129-11. 9-11.16-139-13.16-139-1416-15.16-169-15. 9-15.16-179-16.16-179-2116-18.16-189-23.16-239-23. 9-23.16-259-24.16-259-27.16-259-33.16-269-3616-3016-3616-39. . . . . . . . . . . . . . 16-4216Sparse MatricesMATLAB supports sparse matrices, matrices that contain a small proportion ofnonzero elements. This characteristic provides advantages in both matrixstorage space and computation time.This chapter explains how to create sparse matrices in MATLAB, and how touse them in both specialized and general mathematical operations.
It includes:Function SummaryA summary of the sparse matrix functionsIntroductionAn introduction to sparse matrices in MATLABViewing Sparse MatricesHow to obtain quantitative and graphical information about sparse matricesExample: Adjacency Matrices and GraphsExamples that use adjacency matrices to demonstrate sparse matricesSparse Matrix OperationsA discussion of functions that perform operations specific to sparse matricesSelected BibliographyPublished materials that support concepts described in this chapter16-2Function SummaryFunction SummaryThe sparse matrix functions are located in the sparfun directory in theMATLAB toolbox directory.Function SummaryCategoryFunctionDescriptionElementary sparsematricesspeyeSparse identity matrix.sprandSparse uniformly distributed random matrix.sprandnSparse normally distributed random matrix.sprandsymSparse random symmetric matrix.spdiagsSparse matrix formed from diagonals.sparseCreate sparse matrix.fullConvert sparse matrix to full matrix.findFind indices of nonzero elements.spconvertImport from sparse matrix external format.nnzNumber of nonzero matrix elements.nonzerosNonzero matrix elements.nzmaxAmount of storage allocated for nonzero matrix elements.sponesReplace nonzero sparse matrix elements with ones.spallocAllocate space for sparse matrix.issparseTrue for sparse matrix.spfunApply function to nonzero matrix elements.spyVisualize sparsity pattern.Full to sparseconversionWorking withsparse matrices16-316Sparse MatricesFunction Summary (Continued)CategoryFunctionDescriptionGraph theorygplotPlot graph, as in “graph theory.”etreeElimination tree.etreeplotPlot elimination tree.treelayoutLay out tree or forest.treeplotPlot picture of tree.colamdColumn approximate minimum degree permutation.colmmdColumn minimum degree permutation.symamdSymmetric approximate minimum degree permutation.symmmdSymmetric minimum degree permutation.symrcmSymmetric reverse Cuthill-McKee permutation.colpermColumn permutation.randpermRandom permutation.dmpermDulmage-Mendelsohn permutation.eigsA few eigenvalues.svdsA few singular values.luincIncomplete LU factorization.cholincIncomplete Cholesky factorization.normestEstimate the matrix 2-norm.condest1-norm condition number estimate.sprankStructural rank.ReorderingalgorithmsLinear algebra16-4Function SummaryFunction Summary (Continued)CategoryFunctionDescriptionLinear equations(iterative methods)bicgBiConjugate Gradients Method.bicgstabBiConjugate Gradients Stabilized Method.cgsConjugate Gradients Squared Method.gmresGeneralized Minimum Residual Method.lsqrLSQR implementation of Conjugate Gradients on theNormal Equations.minresMinimum Residual Method.pcgPreconditioned Conjugate Gradients Method.qmrQuasi-Minimal Residual Method.symmlqSymmetric LQ methodspaugmentForm least squares augmented system.spparmsSet parameters for sparse matrix routines.symbfactSymbolic factorization analysis.Miscellaneous16-516Sparse MatricesIntroductionSparse matrices are a special class of matrices that contain a significantnumber of zero-valued elements.
This property allows MATLAB to:• Store only the nonzero elements of the matrix, together with their indices.• Reduce computation time by eliminating operations on zero elements.This section provides information about:• Sparse matrix storage• General storage information• Creating sparse matrices• Importing sparse matricesSparse Matrix StorageFor full matrices, MATLAB stores internally every matrix element.Zero-valued elements require the same amount of storage space as any othermatrix element.
For sparse matrices, however, MATLAB stores only thenonzero elements and their indices. For large matrices with a high percentageof zero-valued elements, this scheme significantly reduces the amount ofmemory required for data storage.MATLAB uses three arrays internally to store sparse matrices with realelements. Consider an m-by-n sparse matrix with nnz nonzero entries stored inarrays of length nzmax:• The first array contains all the nonzero elements of the array infloating-point format.
The length of this array is equal to nzmax.• The second array contains the corresponding integer row indices for thenonzero elements stored in the first nnz entries. This array also has lengthequal to nzmax.• The third array contains n integer pointers to the start of each column in theother arrays and an additional pointer that marks the end of those arrays.The length of the third array is n+1.This matrix requires storage for nzmax floating-point numbers and nzmax+n+1integers. At 8 bytes per floating-point number and 4 bytes per integer, the totalnumber of bytes required to store a sparse matrix is16-6Introduction8*nzmax + 4*(nzmax+n+1)Sparse matrices with complex elements are also possible.
In this case,MATLAB uses a fourth array with nnz elements to store the imaginary partsof the nonzero elements. An element is considered nonzero if either its real orimaginary part is nonzero.General Storage InformationThe whos command provides high-level information about matrix storage,including size and storage class. For example, this whos listing showsinformation about sparse and full versions of the same matrix.whosNameM_fullM_sparseSize1100x11001100x1100Bytes96800004404Classdouble arraysparse arrayGrand total is 1210000 elements using 9684404 bytesNotice that the number of bytes used is much less in the sparse case, becausezero-valued elements are not stored.
In this case, the density of the sparsematrix is 4404/9680000, or approximately .00045%.Creating Sparse MatricesMATLAB never creates sparse matrices automatically. Instead, you mustdetermine if a matrix contains a large enough percentage of zeros to benefitfrom sparse techniques.The density of a matrix is the number of non-zero elements divided by the totalnumber of matrix elements. Matrices with very low density are often goodcandidates for use of the sparse format.Converting Full to SparseYou can convert a full matrix to sparse storage using the sparse function witha single argument.S = sparse(A)16-716Sparse MatricesFor exampleA = [ 0010023000045000];S = sparse(A)producesS =(3,1)(2,2)(3,2)(4,3)(1,4)12345The printed output lists the nonzero elements of S, together with their row andcolumn indices.
The elements are sorted by columns, reflecting the internaldata structure.You can convert a sparse matrix to full storage using the full function,provided the matrix order is not too large. For example A = full(S) reversesthe example conversion.Converting a full matrix to sparse storage is not the most frequent way ofgenerating sparse matrices.
If the order of a matrix is small enough that fullstorage is possible, then conversion to sparse storage rarely offers significantsavings.Creating Sparse Matrices DirectlyYou can create a sparse matrix from a list of nonzero elements using the sparsefunction with five arguments.S = sparse(i,j,s,m,n)i and j are vectors of row and column indices, respectively, for the nonzeroelements of the matrix. s is a vector of nonzero values whose indices arespecified by the corresponding (i,j) pairs. m is the row dimension for theresulting matrix, and n is the column dimension.16-8IntroductionThe matrix S of the previous example can be generated directly withS = sparse([3 2 3 4 1],[1 2 2 3 4],[1 2 3 4 5],4,4)S =(3,1)(2,2)(3,2)(4,3)(1,4)12345The sparse command has a number of alternate forms.
The example aboveuses a form that sets the maximum number of nonzero elements in the matrixto length(s). If desired, you can append a sixth argument that specifies alarger maximum, allowing you to add nonzero elements later withoutreallocating the sparse matrix.Example: Generating a Second Difference OperatorThe matrix representation of the second difference operator is a good exampleof a sparse matrix.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
