Sparse matrix formats
Implementations of selected sparse matrix formats for linear algebra supporting scientific and machine learning applications. Compatible with the APIs in the Gonum package and interoperable with Gonum dense matrix types.
Overview
Machine learning applications typically model entities as vectors of numerical features so that they may be compared and analysed quantitively. Typically the majority of the elements in these vectors are zeros. In the case of text mining applications, each document within a corpus is represented as a vector and its features represent the vocabulary of unique words. A corpus of several thousand documents might utilise a vocabulary of hundreds of thousands (or perhaps even millions) of unique words but each document will typically only contain a couple of hundred unique words. This means the number of non-zero values in the matrix might only be around 1%.
Sparse matrix formats capitalise on this premise by only storing the non-zero values thereby reducing both storage/memory requirements and processing effort for manipulating the data.
Features
- Implementations of Sparse BLAS standard routines.
- Compatible with Gonum's APIs and interoperable with Gonum's dense matrix types.
- Implemented Formats:
- Sparse Matrix Formats:
- Other Formats:
- Matrix multiplication, addition and subtraction and vector dot products.
Usage
The sparse matrices in this package implement the Gonum Matrix
interface and so are fully interoperable and mutually compatible with the Gonum APIs and dense matrix types.
dokMatrix := sparse.NewDOK(3, 2)
dokMatrix.Set(0, 0, 5)
dokMatrix.Set(2, 1, 7)
m, n := dokMatrix.Dims()
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
fmt.Printf("%.0f,", dokMatrix.At(i, j))
}
fmt.Printf("\n")
}
csrMatrix := dokMatrix.ToCSR()
cooMatrix := sparse.Random(sparse.COOFormat, 2, 3, 0.5)
denseMatrix := csrMatrix.ToDense().T()
var csrProduct sparse.CSR
csrProduct.Mul(csrMatrix, cooMatrix)
denseProduct := sparse.MulMatMat(false, 1, csrMatrix, denseMatrix, nil)
Installation
With Go installed, package installation is performed using go get.
go get -u github.com/james-bowman/sparse/...
Acknowledgements
- Gonum
- Netlib. BLAS. Chapter 3: Sparse BLAS
- J.R. Gilbert, C. Moler, and R. Schreiber. Sparse matrices in
MATLAB: Design and implementation. SIAM Journal on Matrix Analysis and
Applications, 13:333–356, 1992.
- F.G. Gustavson. Some basic techniques for solving sparse systems
of linear equations. In D.J. Rose and R.A. Willoughby, eds., Sparse Matrices and
Their Applications, 41–52, New York: Plenum Press, 1972.
- F.G. Gustavson. Efficient algorithm to perform sparse matrix
multiplication. IBM Technical Disclosure Bulletin, 20:1262–1264, 1977.
- Wikipedia. Sparse Matrix
- A. Fog. 2. Optimizing subroutines in assembly language An optimization guide for x86 platforms, 1996.
See Also
License
MIT