This effort is still a "work in progress". Please feel free to add comments. BRBut please make the content less visible by using smaller fonts. – Edward J. Yoon
Sparse Matrix
NOTE:
- Sparse matrix operations cannot be optimized.
- Sparse structures which are growable can exceed the initial bandwidth allocation, while those which are not growable are fixed, and over-allocation will cause an error
- Matrices which are column major typically perform better with column-oriented operations, and likewise for row major matrices. Matrix/vector multiplication is row-major, while transpose multiplication is column-major.
Why sparse matrices?
- Many classes of problems result in matrices with a large number of zeros
- A sparse matrix is a special class of matrix that allows only the non-zero terms to be stored
- Reduction in the storage requirements for sparse matrices
- Significant speed improvement as many calculations involving zero elements are neglected
Storage of sparse matrices
I choosed HBase(sparse matrix storage) to reduce storage and complexity.
- Hama use column-oriented storage of matrices (HBase) , and so compressed column format is a natural choice of sparse storage
- Hama forces the elements of each column to be stored in increasing order of their row index
1 0 0 (1,1) = 1 0 3 1 (2,2) = 3 0 0 0 (2,3) = 1
See also: [http://labs.google.com/papers/bigtable-osdi06.pdf Bigtable], A Distributed Storage System for Structured Data
Sparse Functions
Manipulate sparse matrices
Function |
Explanation |
nnz |
returns number of non zero elements in SM |
nonzeros |
Returns a vector of the non-zero values of the sparse matrix S |
Linear Algebra
Function |
Explanation |
spdetermin |
Compute the determinant of sparse matrix A |
spcholesky |
Compute the Cholesky factor, R, of the symmetric positive definite |
splcholesky |
Compute the Cholesky factor, L, of the symmetric positive definite |
splu |
Compute the LU decomposition of the sparse matrix A |