资源描述
Sparse Matricessparse many elements are zerodense few elements are zero1Example Of Sparse Matricesdiagonaltridiagonallower triangular(?)These are structured sparse matrices.May be mapped into a 1D array so that a mapping function can be used to locate an element.2Unstructured Sparse MatricesAirline flight matrix.1.airports are numbered 1 through n2.flight(i,j)=list of nonstop flights from airport i to airport j3.n=1000(say)4.n x n array of list references=4 million bytes5.total number of flights=20,000(say)6.need at most 20,000 list references=at most 80,000 bytes3Unstructured Sparse MatricesWeb page matrix.web pages are numbered 1 through nweb(i,j)=number of links from page i to page jWeb analysis.authority page page that has many links to ithub page links to many authority pages4Web Page Matrix1.n=2 billion(and growing by 1 million a day)2.n x n array of ints=16*1018 bytes(16*109 GB)3.each page links to 10(say)other pages on average4.on average there are 10 nonzero entries per row5.space needed for nonzero elements is approximately 20 billion x 4 bytes=80 billion bytes(80 GB)5Representation Of Unstructured Sparse MatricesSingle linear list in row-major order.scan the nonzero elements of the sparse matrix in row-major ordereach nonzero element is represented by a triple(row,column,value)the list of triples may be an array list or a linked list(chain)6Single Linear List Example0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0list=row 1 1 2 2 4 4column 3 5 3 4 2 3value 3 4 5 7 2 67Array Linear List Representation row 1 1 2 2 4 4list=column 3 5 3 4 2 3 value 3 4 5 7 2 6 element 0 1 2 3 4 5 row 1 1 2 2 4 4 column 3 5 3 4 2 3 value 3 4 5 7 2 68Chain RepresentationNode structure.rowcolnextvalue9Single Chain row 1 1 2 2 4 4list =column 3 5 3 4 2 3 value 3 4 5 7 2 61 331 5425274246343nullfirstNode210One Linear List Per Row 0 0 3 0 4 0 0 5 7 00 0 0 0 0 0 2 6 0 0 row1=(3,3),(5,4)row2=(3,5),(4,7)row3=row4=(2,2),(3,6)11Array Of Row ChainsNode structure.nextvaluecol12Array Of Row Chains0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0row33null4553null7422null63null13Orthogonal List RepresentationBoth row and column lists.Node structure.rowcolnextdownvalue14Row Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0null1 331 542 352 474 224 36nnn15Column Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 01 331 542 352 474 224 36nnn16Orthogonal Lists0 0 3 0 4 0 0 5 7 00 0 0 0 00 2 6 0 0nullrow1 331 542 352 474 224 36n nnnnn17VariationsMay use circular lists instead of chains.18Approximate Memory Requirements 500 x 500 matrix with 1994 nonzero elements2D array 500 x 500 x 4=1million bytesSingle Array List 3 x 1994 x 4=23,928 bytesOne Chain Per Row 23928+500 x 4=25,92819Runtime Performance Matrix Transpose500 x 500 matrix with 1994 nonzero elements2D array 210 msSingle Array List 6 msOne Chain Per Row 12 ms20PerformanceMatrix Addition.500 x 500 matrices with 1994 and 999 nonzero elements2D array 880 msSingle Array List 18 msOne Chain Per Row 29 ms21
展开阅读全文