Question? Leave a message!




Sparse matrix formats

Sparse matrix formats
ECE 250 Algorithms and Data Structures Sparse matrix formats Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Sparse matrix formats 2 Outline In this topic, we will cover: – Sparse matrices – A rowcolumnvalue representation – The old Yale sparse matrix data structure – Examples – Appropriate useSparse matrix formats 3 Dense versus sparse matrices A dense N × M matrix is one where most elements are nonzero A dense matrix data structure is one that has a memory location allocated for each possible matrix entry – These require Q(NM) memory A sparse matrix is where 90 or more of the entries are zero – If m is the number of nonzero entries, • The density is m/MN • The row density is m/N – Operations and storage should depend on m – For sparse matrices, m = o(MN)Sparse matrix formats 4 Example A dense 1 585 478 square matrix of doubles would occupy 18 TiB The matrix representation of the AMD G3 processor has only 7 660 826 nonzero entries – The density is 0.000003 – The matrix is used for circuit simulation – Simulations requires solving a system of 1,585,478 equations in that many unknowns http://www.cise.ufl.edu/research/sparse/matrices/AMD/G3circuit.htmlSparse matrix formats 5 Dense square matrix data structure 2 2 This class stores N × N matrices with 8 + 4N + 8N = Q(N ) bytes class Matrix private: int N; double matrix; Matrix::Matrix( int n ): public: N( std::max(1, n) ), Matrix( int n ); matrix( new double N ) // ... matrix0 = new doubleNN; ; for ( int i = 1; i N; ++i ) matrixi = matrix0 + iN; pointer arithmeticSparse matrix formats 6 RowColumnValue Representation As an example: 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0  matrix  0 0 1.9 0 0 0 4.9 0   00000003.6  1.5 0 0 0 0 0 0 0 0 2.3 0 1.4 0 0 0 0 0 0 3.7 0 0 2.7 0 0 0 1.6 0 2.3Sparse matrix formats 7 RowColumnValue Representation Suppose we store triplets for each nonzero value: – We would have (0, 0, 1.5), (1, 1, 2.3), (1, 3, 1.4), (2, 2, 3.7), … 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0   0 0 1.9 0 0 0 4.9 0   00000003.6 – The class would be  class Triplet int row; int column; double value; ;Sparse matrix formats 8 RowColumnValue Representation Now the memory requirements are Q(m) class Sparsematrix private: int matrixsize; int N; int arraycapacity; Triplet entries; public: Sparsematrix( int n, int c = 128 ); ; Sparsematrix( int n, int c ): matrixsize( 0 ), N( std::max(1, n) ), arraycapacity( std::max(1, c) ), entries( new Tripletarraycapacity ) // does nothing Sparse matrix formats 9 RowColumnValue Representation For the same example, we have: 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0   entries 0 0 1.9 0 0 0 4.9 0   00000003.6  0 1 1 2 2 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –2.7 –1.6 2.3 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 10 RowColumnValue Representation We fill in the entries in rowmajor order 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0   entries 0 0 1.9 0 0 0 4.9 0   00000003.6  0 1 1 2 2 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –2.7 –1.6 2.3 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 11 RowColumnValue Representation The AMD G3 circuit now requires 117 MiB versus 18 TiB http://www.cise.ufl.edu/research/sparse/matrices/AMD/G3circuit.htmlSparse matrix formats 12 Accessing Entries Adding and erasing entries (setting to 0) requires a lot of work – They are require O(m) copies 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0  entries  0 0 1.9 0 0 0 4.9 0   00000003.6  0 1 1 2 2 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –2.7 –1.6 2.3 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 13 Accessing Entries By using rowmajor order, the indices are lexicographically ordered – We may search using a binary search: O(ln(m)) 1.5 0 0 0 0 0 0 0   0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 02.7 0 0  01.6 0 2.3 0 0 0 0  A  0 0 0 0 5.8 0 0 0  0 0 0 0 0 7.4 0 0  entries  0 0 1.9 0 0 0 4.9 0   00000003.6  0 1 1 2 2 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –2.7 –1.6 2.3 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 14 Old Yale Sparse Matrix Format Storing the row, column, and value of each entry has some undesirable characteristics – Accessing an entry is O(ln(m)) • For the AMD G3, lg(7,660,826) = 23 – If each row has approximately the same number of entries, we can use an interpolation search: O(ln(ln(m))) • For the AMD G3, ln(ln(7,660,826)) = 3Sparse matrix formats 15 Old Yale Sparse Matrix Format The original (old) Yale sparse matrix format: – Reduces access time to lg(m/N) and uses less memory – For circuits, it is seldom that m/N 10 • For the AMD G3 circuits, m/N 5 It was developed by Eisenstat et al. in the late 1970sSparse matrix formats 16 Old Yale Sparse Matrix Format Note that the arrays have redundancy – Any row which contains more than one entry is stored in successive entries1.5 0 0 0 0 0 0 0  0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 0 0 0 0   01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  entries entries 0 1 2 3 4 5 6 7 8 9 10 11 0 1 1 2 3 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 17 Old Yale Sparse Matrix Format Suppose we store only the location of the first entry of each row: – The first entry in Row 0 is in entry 0 1.5 0 0 0 0 0 0 0 – The first entry in Row 3 is in entry 4  0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 0 0 0 0   01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  entries 0 1 2 3 4 5 6 7 8 9 10 11 0 1 1 2 3 3 3 4 5 6 6 7 0 1 3 2 5 1 3 4 5 2 6 7 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 18 Old Yale Sparse Matrix Format Let us remove that redundancy by creating a new array IA where IA(i) stores the location in JA and A of the first nonzero entry in th the i row1.5 0 0 0 0 0 0 0  0 2.3 0 1.4 0 0 0 0  – Rename the column and value  0 0 3.7 0 0 0 0 0  arrays to JA and A, respectively  01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  IA 0 1 2 3 4 5 6 7 8 0 1 3 4 7 8 9 11 12 0 1 2 3 4 5 6 7 8 9 10 11 JA 0 1 3 2 5 1 3 4 5 2 6 7 A 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 19 Old Yale Sparse Matrix Format rd For example, the first entry of the 3 row is located at position IA(3) 1.5 0 0 0 0 0 0 0  0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 0 0 0 0   01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  IA 0 1 2 3 4 5 6 7 8 0 1 3 4 7 8 9 11 12 0 1 2 3 4 5 6 7 8 9 10 11 JA 0 1 3 2 5 1 3 4 5 2 6 7 A 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 20 Old Yale Sparse Matrix Format th Also, the first entry of the 4 row is located at position IA(4) – The entries of Row 4 are in 4, 5, 6 1.5 0 0 0 0 0 0 0  0 2.3 0 1.4 0 0 0 0   0 0 3.7 0 0 0 0 0   01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  IA 0 1 2 3 4 5 6 7 8 0 1 3 4 7 8 9 11 12 0 1 2 3 4 5 6 7 8 9 10 11 JA 0 1 3 2 5 1 3 4 5 2 6 7 A 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 21 Old Yale Sparse Matrix Format Searching for entry a now only requires you to search i,j double a = 0.0; for ( int k = IAi; k IAi + 1; ++k ) 1.5 0 0 0 0 0 0 0  if ( JAk == j ) 0 2.3 0 1.4 0 0 0 0   a = Ak; 0 0 3.7 0 0 0 0 0   01.6 0 2.3 9.9 0 0 0 A  0 0 0 0 5.8 0 0 0   0 0 0 0 0 7.4 0 0 – For larger row densities, use binary search  0 0 1.9 0 0 0 4.9 0   0 0 0 0 0 0 0 3.6  IA 0 1 2 3 4 5 6 7 8 0 1 3 4 7 8 9 11 12 0 1 2 3 4 5 6 7 8 9 10 11 JA 0 1 3 2 5 1 3 4 5 2 6 7 A 1.5 2.3 1.4 3.7 –1.6 2.3 9.9 5.8 7.4 1.9 4.9 3.6Sparse matrix formats 22 Old Yale Sparse Matrix Format Our class could look something like requring 28 + 4N + 12m bytes: class Oldyalesparsematrix private: int matrixsize, N, arraycapacity; int IA, JA double A; public: Oldyalesparsematrix( int n, int c = 128 ); // other member functions ; Oldyalesparsematrix::Oldyalesparsematrix( int n, int c ): matrixsize( 0 ), N( std::max(1, n) ), arraycapacity( std::max(1,c) ), IA = new intN + 1; JA = new intarraycapacity; A = new doublearraycapacity for ( int i = 0; i = N; ++i ) IAi = 0; Sparse matrix formats 23 Old Yale Format: The Zero Matrix We initialize the matrix to the zero matrix 0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0  A  0 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 IA 0 1 2 3 4 5 6 7 8   0 0 0 0 0 0 0 0  0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 JA ASparse matrix formats 24 Old Yale Format: Access To demonstrate accessing on the AMD G3 circuit, let us determine the weights of the connections to element 1001 – Looking up the array IA1001, we note that the results are stored starting at locations 2500, 2501, and 2502 in JA and A IA 996 2488 997 2490 998 2493 999 2495 1000 2498 1001 2500 1002 2503 1003 2505 1004 2508 1005 2510 1006 2513Sparse matrix formats 25 Old Yale Format: Access JA A 2491 998 0.548426E+00 2492 156375 0.200000E+01 Viewing these two arrays, we have: 2493 998 0.109685E+01 a = 3.09685 1001,1001 2494 999 0.548426E+00 a = –0.54826 1001,1002 2495 999 0.309685E+01 a = –2.0 1001,157003 2496 1000 0.548426E+00 2597 156689 0.200000E+01 2598 1000 0.109685E+01 996 2488 2599 1001 0.548426E+00 997 2490 2500 1001 0.309685E+01 998 2493 2501 1002 0.548426E+00 999 2495 2502 157003 0.200000E+01 1000 2498 2503 1002 0.109685E+01 1001 2500 2504 1003 0.548426E+00 1002 2503 2505 1003 0.309685E+01 1003 2505 2506 1004 0.548426E+00 1004 2508 2507 157317 0.200000E+01 1005 2510 2508 1004 0.109685E+01 1006 2513 2509 1005 0.548426E+00 2510 1005 0.309685E+01Sparse matrix formats 26 Old Yale Format: Memory Use Storing a sparse 8× 8 matrix with 12 nonzero entries: 2 – Full matrix: 8 + 4N + 8N = 552 bytes – Rowcolumnvalue: 24 + 16m = 216 bytes – Old Yale format: 28 + 4N + 12m = 204 bytes For the AMD G3 circuit where N = 1585478 and m = 7660826 2 – Full matrix: 8 + 4N + 8N = 19 178 324 MiB – Rowcolumnvalue: 24 + 16m = 117 MiB – Old Yale format: 28 + 4N + 12m = 94 MiBSparse matrix formats 27 Old Yale Sparse Matrix Format This format is the basis for: – the HarwellBoeing matrix format, and – the internal representation by Matlab – the new Yale sparse matrix format The first two swap rows and columns... – Old Yale format is row major – Matlab and the HarwellBoeing are column majorSparse matrix formats 28 New Yale Sparse Matrix Format The new Yale format makes use of: – diagonal entries are almost always nonzero – the diagonal entries are mostoften accessed Thus, store diagonal entries separately:Sparse matrix formats 29 New Yale Sparse Matrix Format The benefits are quite clear: – Memory usage is less: 28 + 12m bytes – Access to diagonal entries is now Q(1)Sparse matrix formats 30 New Yale Sparse Matrix Format An implementation of the new Yale sparse matrix format is at http://ece.uwaterloo.ca/dwharder/aads/Algorithms/Sparsesystems/ This includes: – Constructors, etc. – Matrix and vector functions: norms, trace, etc. – Matrixmatrix and matrixvector operations – Various solvers: • Jacobi, GaussSeidel, forward and backward substitution • Steepest descent, minimal residual, and residual norm steepest descent methodsSparse matrix formats 31 Operations Suppose that N × N matrices have m = Q(N) nonzero entries – At most a fixed number of entries per row 2 Many Q(N ) are reduced to Q(N) run times, including: – Matrix addition—similar to merging – Matrix scalar multiplication – Matrixvector multiplication – Forward and backward substitution 2 3 Even finding the M = PLU decomposition is now O(N ) and not Q(N ) Sparse matrix formats 32 Operations 3 The M = PLU decomposition, however, may still be Q(N ) – The worst case is where the first row and column are dense – A matrix which has most entries around the diagonal is said to be a band diagonal matrix – If all entries are Q(1) of the diagonal, Gaussian elimination and PLU decomposition are Q(N)Sparse matrix formats 33 Memory Allocation Matlab recognizes this and therefore allows you to specify the initial capacity: M = spalloc( N, N, m ); After that, if the array is full, it only assigns room for 10 more entries in the array – This will result in quadratic behaviour if used improperlySparse matrix formats 34 Memory Allocation As an experiment, start with an empty 1000 × 1000 sparse matrix and begin assigning entries – After every 10 insertions, the array must be resized, and therefore we expect quadratic behaviour – The next plot shows the time required to assign 100 000, 200 000, etc. of those entries Sparse matrix formats 35 Memory Allocation The leastsquares bestfitting quadratic function is a good fitSparse matrix formats 36 Memory Allocation Thus, in the previous example, if we preallocate one million entries: A = spalloc( 1000, 1000, 1000000 ); and then fill them, we get linear (blue) behaviour:Sparse matrix formats 37 Memory Allocation Because the copies are made only every 10 assignments, the effect th is not that significant, the number of copies made is only 1/10 of those made if with each assignment: n n 10 1 n 2 1 n 2 10k n  10k n  2 2 k0 20 2 k0Sparse matrix formats 38 Sample Test Runs Matlab must maintain the compressedcolumn shape of the matrix, thus, inserting objects to the left of the rightmost nonzero column must consequently require copying all entries over – recall: Matlab’s representation is columnfirstSparse matrix formats 39 Sample Test Runs Thus, this code which assigns m entries: n = 1024; m = nn; A = spalloc( n, n, m ); for j = 1:n for ( j = 1; j = n; ++j ) for i = 1:n for ( i = 1; i = n; ++i ) A(i, j) = 1 + i + j; end end 0 0 0 0 0 0   runs in O(m) time 0 0 0 0 0 0   0 0 0 0 0 0  A It took 5 s when I tried it 0 0 0 0 0 0   0 0 0 0 0 0   0 0 0 0 0 0 Sparse matrix formats 40 Sample Test Runs While this code, which assigns m entries: n = 1024; m = nn; A = spalloc( n, n, m ); for i = n:1:1 for ( i = n; i = 1; i ) for j = n:1:1 for ( j = n; j = 1; j ) A(i, j) = 1 + i + j; end end 0 0 0 0 0 0   2 runs in O(m ) time 0 0 0 0 0 0   0 0 0 0 0 0  A This took 7 min 0 0 0 0 0 0   0 0 0 0 0 0   0 0 0 0 0 0 Sparse matrix formats 41 Sample Test Runs Even this code which assigns m entries: n = 1024; m = nn; A = spalloc( n, n, m ); for i = 1:n for ( j = 1; j = n; ++j ) for j = 1:n for ( i = 1; i = n; ++i ) A(i, j) = 1 + i + j; end end 0 0 0 0 0 0   2 also runs in O(m ) time 0 0 0 0 0 0   0 0 0 0 0 0  A Only half the copies as with the 0 0 0 0 0 0   previous case—just a little less time 0 0 0 0 0 0   0 0 0 0 0 0 Sparse matrix formats 42 Sample Test Runs This is the worstcase order n = 1024; m = nn; A = spalloc( n, n, m ); for j = n:1:1 for i = n:1:1 A(i, j) = 1 + i + j; end end 0 0 0 0 0 0   0 0 0 0 0 0   0 0 0 0 0 0  A I halted the computer after 30 min 0 0 0 0 0 0   0 0 0 0 0 0   0 0 0 0 0 0 Sparse matrix formats 43 Sample Test Runs Consequently, it is your responsibility to use this data structure correctly: – It is designed to allow exceptionally fast accesses, including: • Fast matrixmatrix addition • Fast matrixvector multiplication • Fast Gaussian elimination and backward substitutionSparse matrix formats 44 Example Consider the following circuit with resistors and operational amplifies This is from an example in Vlach and Singhal, p.143.Sparse matrix formats 45 Example The modified nodal representation of the circuit I 0 is represented by this sparse matrix: recover the original matrix 0 1 2 3 4 5 6 7 IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 46 Example It is a conductance matrix with op amps and is therefore square and not symmetric – The IA matrix has size 7 = N + 1 entries • The matrix is 7 × 7 – The last entry of IA is 19 • There are 19 nonzero entries 0 1 2 3 4 5 6 7 IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 47 Example We will build the matrix rowbyrow 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0  G 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 48 Example Row 0 is stored in entries 0 and 1 IA0 throughIA1 – 1 with entries 0 0 0 0 0 0 0   0.1 in column 0 0 0 0 0 0 0 0  0.1 in column 1  0 0 0 0 0 0 0  G 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 49 Example Row 0 is stored in entries 0 and 1 IA0 throughIA1 – 1 with entries 0.1 0.1 0 0 0 0 0   0.1 in column 0 0 0 0 0 0 0 0  –0.1 in column 1  0 0 0 0 0 0 0  G 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 50 Example Row 1 is stored in entries 2 through 5 IA1 throughIA2 – 1 with entries 0.1 0.1 0 0 0 0 0   0.1 in column 0 0 0 0 0 0 0 0  0.6 in column 1  0 0 0 0 0 0 0  0.5 in column 2 G 0 0 0 0 0 0 0   1.0 in column 6 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 51 Example Row 1 is stored in entries 2 through 5 IA1 throughIA2 – 1 with entries 0.1 0.1 0 0 0 0 0   0.1 in column 0  0.1 0.6 0.5 0 0 0 1.0  0.6 in column 1  0 0 0 0 0 0 0  0.5 in column 2 G 0 0 0 0 0 0 0   1.0 in column 6 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 52 Example Row 2 is stored in entries 6, 7, and 8 IA2 throughIA3 – 1 with entries 0.1 0.1 0 0 0 0 0   0.5 in column 1  0.1 0.6 0.5 0 0 0 1.0  0.9 in column 2  0 0 0 0 0 0 0  0.4 in column 3 G 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 53 Example Row 2 is stored in entries 6, 7, and 8 IA2 throughIA3 – 1 with entries 0.1 0.1 0 0 0 0 0   0.5 in column 1  0.1 0.6 0.5 0 0 0 1.0  0.9 in column 2  0 0.5 0.9 0.4 0 0 0  0.4 in column 3 G 0 0 0 0 0 0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 54 Example Row 3 is stored in entries 9 through 12 IA3 throughIA4 – 1 with entries 0.1 0.1 0 0 0 0 0   0.4 in column 2  0.1 0.6 0.5 0 0 0 1.0  0.7 in column 3  0 0.5 0.9 0.4 0 0 0  0.3 in column 4 G 0 0 0 0 0 0 0   1.0 in column 5 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 55 Example Row 3 is stored in entries 9 through 12 IA3 throughIA4 – 1 with entries 0.1 0.1 0 0 0 0 0   0.4 in column 2  0.1 0.6 0.5 0 0 0 1.0  0.7 in column 3  0 0.5 0.9 0.4 0 0 0  0.3 in column 4 G 0 0 0.4 0.7 0.3 1.0 0   1.0 in column 5 0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 56 Example Row 4 is stored in entries 13 and 14 IA4 throughIA5 – 1 with entries 0.1 0.1 0 0 0 0 0   0.3 in column 2  0.1 0.6 0.5 0 0 0 1.0  0.5 in column 3  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0 0 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 57 Example Row 4 is stored in entries 13 and 14 IA4 throughIA5 – 1 with entries 0.1 0.1 0 0 0 0 0   0.3 in column 2  0.1 0.6 0.5 0 0 0 1.0  0.5 in column 3  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 58 Example Row 5 is stored in entries 15 and 16 IA5 throughIA6 – 1 with entries 0.1 0.1 0 0 0 0 0   1.0 in column 0  0.1 0.6 0.5 0 0 0 1.0  1.0 in column 2  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   0 0 0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 59 Example Row 5 is stored in entries 15 and 16 IA5 throughIA6 – 1 with entries 0.1 0.1 0 0 0 0 0   1.0 in column 0  0.1 0.6 0.5 0 0 0 1.0  1.0 in column 2  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   1.0 01.0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 60 Example Row 6 is stored in entries 17 and 18 IA6 throughIA7 – 1 with entries 0.1 0.1 0 0 0 0 0   1.0 in column 2  0.1 0.6 0.5 0 0 0 1.0  1.0 in column 4  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   1.0 01.0 0 0 0 0 0 1 2 3 4 5 6 7  0 0 0 0 0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 61 Example Row 6 is stored in entries 17 and 18 IA6 throughIA7 – 1 with entries 0.1 0.1 0 0 0 0 0   1.0 in column 2  0.1 0.6 0.5 0 0 0 1.0  1.0 in column 4  0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   1.0 01.0 0 0 0 0 0 1 2 3 4 5 6 7  0 01.0 0 1.0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 62 Example Consequently, we have recovered the modified nodal representation: 0.1 0.1 0 0 0 0 0    0.1 0.6 0.5 0 0 0 1.0   0 0.5 0.9 0.4 0 0 0  G 0 0 0.4 0.7 0.3 1.0 0   0 0 0 0.3 0.5 0 0   1.0 01.0 0 0 0 0 0 1 2 3 4 5 6 7  0 01.0 0 1.0 0 0  IA 0 2 6 9 13 15 17 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 JA 0 1 0 1 2 6 1 2 3 2 3 4 5 3 4 0 2 2 4 A 0.1 0.1 0.1 0.6 0.5 1.0 0.5 0.9 0.4 0.4 0.7 0.3 1.0 0.3 0.5 1.0 1.0 1.0 1.0Sparse matrix formats 63 Example If I = 400 mA, then the system 0 0.1 0.1 0 0 0 0 0 v 0.4  0   0.1 0.6 0.5 0 0 0 1.0 v 0  1  v 0 0.5 0.9 0.4 0 0 0 0 2  0 0 0.4 0.7 0.3 1.0 0 v 0  3  0 0 0 0.3 0.5 0 0 v 0 4   1.0 01.0 0 0 0 0 i 0 1  0 01.0 0 1.0 0 0 i 0  2 yields the solution v 7.5  0  v 3.5  1  v 7.5 2  v  12.5 3  v 7.5 4    i 3.5 1  i 2.4  2Sparse matrix formats 64 Example At this point, we can simply use Ohms law to determine the remaining currentsSparse matrix formats 65 Summary In this topic, we have looked at the old Yale sparse matrix representation – Both memory usage and many operations 2 for N × N matrices with m nonzero entries are reduced from Q(N ) to Q(m) – Accessing entries is reduced to O(m/N) – Incorrect usage, however, leads to serious runtime slow downs...Sparse matrix formats 66 ReferencesSparse matrix formats 67 References Wikipedia, http://en.wikipedia.org/wiki/SparsematrixYaleformat rd 1 Donald E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3 Ed., Addison Wesley, 1997, §2.2.1, p.238. 2 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, §11.1, p.200. rd 3 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §3.6, p.94. 4 Randolph E. Bank, Craig C. Douglas Sparse Matrix Multiplication Package (SMMP), April 23, 2001. nd 5 Jiri Vlach and Kishore Singhal, Computer Methods for Circuit Analysis and Design, 2 Ed., Chapman and Hall, 1994. 6 Iain Duff, Roger Grimes, John Lewis, User's Guide for the HarwellBoeing Sparse Matrix Collection, Technical Report TR/PA/92/86, CERFACS, October 1992. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017