You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@mahout.apache.org by "Ted Dunning (JIRA)" <ji...@apache.org> on 2008/02/22 04:56:19 UTC
[jira] Commented: (MAHOUT-6) Need a matrix implementation
[ https://issues.apache.org/jira/browse/MAHOUT-6?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12571273#action_12571273 ]
Ted Dunning commented on MAHOUT-6:
----------------------------------
My own, non-portable, non-releasable matrix package uses a class structure something like Colt, but with a simpler extension structure:
interface Matrix1D -- the basic interface including numerous convenience functions
abstract class AbstractMatrix1D implements Matrix1D -- implementations of generic capabilities like sum of elements and dot products
class DenseMatrix1D extends AbstractMatrix1D -- implements vector as an array of doubles with an offset and stride. used for vectors and views of sub-vectors and row or column views of dense matrices.
class SparseBinaryVector extends AbstractMatrix1D -- implements vector that only "stores" 0 or 1, but only stores the 1's, but doesn't store them because it knows what their value is. This is really a bit-vector implemented as a closed hash table that only holds integers.
class SparseDoubleVector extends AbstractMatrix1D -- implements vector that only stores non-zero doubles
interface Matrix2D -- the basic interface including convenience functions
abstract class AbstractMatrix2D implements Matrix1D -- a few universal implementations of convenience functions mostly in terms of BLAS ops
abstract class AbstractSparseMatrix2D extends AbstractMatrix2D -- efficient implementations of BLAS ops for generic sparse matrices
abstract class AbstractDenseMatrix2D extends AbstractMatrix2D -- reasonably efficient implementations of BLAS ops for dense matrices
class DenseMatrix2D extends ADM2D -- matrix of doubles implemented using a single 1D array with generic stride and offset. Also used to hold transposed views and some kinds of sub-matrix views.
class DoublyIndexedSparseBinary2D -- sparse matrix whose non-zero elements are all 1. Fast row and column views are available through redundant storage.
class SparseRowDouble2D -- sparse matrix with general element values whose rows are accessible quickly. Implemented as an array of SparseDouble1D vectors.
class SparseColumnDouble2D -- sparse matrix with general elements values whose columns are accessible quickly.
Functions --- Matrices support updates using functional objects so that generic in-place updates can be done very efficiently. I stole this idea from Colt. In fact, my matrix package uses the Colt Functions object for my own matrix implementations which is one reason I can't distribute my own matrices very easily.
Any comments on this general structure? For machine learning, I have had very little call for complex numbers. Some might take issue with my assumption that float's pretty much just don't exist, but for large problems, I find it imperative to retain precision more than save memory.
> Need a matrix implementation
> ----------------------------
>
> Key: MAHOUT-6
> URL: https://issues.apache.org/jira/browse/MAHOUT-6
> Project: Mahout
> Issue Type: New Feature
> Reporter: Ted Dunning
>
> We need matrices for Mahout.
> An initial set of basic requirements includes:
> a) sparse and dense support are required
> b) row and column labels are important
> c) serialization for hadoop use is required
> d) reasonable floating point performance is required, but awesome FP is not
> e) the API should be simple enough to understand
> f) it should be easy to carve out sub-matrices for sending to different reducers
> g) a reasonable set of matrix operations should be supported, these should eventually include:
> simple matrix-matrix and matrix-vector and matrix-scalar linear algebra operations, A B, A + B, A v, A + x, v + x, u + v, dot(u, v)
> row and column sums
> generalized level 2 and 3 BLAS primitives, alpha A B + beta C and A u + beta v
> h) easy and efficient iteration constructs, especially for sparse matrices
> i) easy to extend with new implementations
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
Re: [jira] Commented: (MAHOUT-6) Need a matrix implementation
Posted by Grant Ingersoll <gs...@apache.org>.
Any thoughts about where support belongs for things like calculating
eigenvalues/vectors and/or *Rank algorithms that rely on an iterative
operations on a matrix/graph, etc.? Seems like they can be
generalized, but not sure if they are first class citizens on a Matrix
implementation or not.
-Grant
On Feb 21, 2008, at 10:56 PM, Ted Dunning (JIRA) wrote:
>
> [ https://issues.apache.org/jira/browse/MAHOUT-6?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12571273
> #action_12571273 ]
>
> Ted Dunning commented on MAHOUT-6:
> ----------------------------------
>
>
> My own, non-portable, non-releasable matrix package uses a class
> structure something like Colt, but with a simpler extension structure:
>
> interface Matrix1D -- the basic interface including numerous
> convenience functions
>
> abstract class AbstractMatrix1D implements Matrix1D --
> implementations of generic capabilities like sum of elements and dot
> products
>
> class DenseMatrix1D extends AbstractMatrix1D -- implements vector as
> an array of doubles with an offset and stride. used for vectors and
> views of sub-vectors and row or column views of dense matrices.
>
> class SparseBinaryVector extends AbstractMatrix1D -- implements
> vector that only "stores" 0 or 1, but only stores the 1's, but
> doesn't store them because it knows what their value is. This is
> really a bit-vector implemented as a closed hash table that only
> holds integers.
>
> class SparseDoubleVector extends AbstractMatrix1D -- implements
> vector that only stores non-zero doubles
>
>
>
> interface Matrix2D -- the basic interface including convenience
> functions
>
> abstract class AbstractMatrix2D implements Matrix1D -- a few
> universal implementations of convenience functions mostly in terms
> of BLAS ops
>
> abstract class AbstractSparseMatrix2D extends AbstractMatrix2D --
> efficient implementations of BLAS ops for generic sparse matrices
>
> abstract class AbstractDenseMatrix2D extends AbstractMatrix2D --
> reasonably efficient implementations of BLAS ops for dense matrices
>
> class DenseMatrix2D extends ADM2D -- matrix of doubles implemented
> using a single 1D array with generic stride and offset. Also used
> to hold transposed views and some kinds of sub-matrix views.
>
> class DoublyIndexedSparseBinary2D -- sparse matrix whose non-zero
> elements are all 1. Fast row and column views are available through
> redundant storage.
>
> class SparseRowDouble2D -- sparse matrix with general element values
> whose rows are accessible quickly. Implemented as an array of
> SparseDouble1D vectors.
>
> class SparseColumnDouble2D -- sparse matrix with general elements
> values whose columns are accessible quickly.
>
>
> Functions --- Matrices support updates using functional objects so
> that generic in-place updates can be done very efficiently. I stole
> this idea from Colt. In fact, my matrix package uses the Colt
> Functions object for my own matrix implementations which is one
> reason I can't distribute my own matrices very easily.
>
> Any comments on this general structure? For machine learning, I
> have had very little call for complex numbers. Some might take
> issue with my assumption that float's pretty much just don't exist,
> but for large problems, I find it imperative to retain precision
> more than save memory.
>
>
>> Need a matrix implementation
>> ----------------------------
>>
>> Key: MAHOUT-6
>> URL: https://issues.apache.org/jira/browse/MAHOUT-6
>> Project: Mahout
>> Issue Type: New Feature
>> Reporter: Ted Dunning
>>
>> We need matrices for Mahout.
>> An initial set of basic requirements includes:
>> a) sparse and dense support are required
>> b) row and column labels are important
>> c) serialization for hadoop use is required
>> d) reasonable floating point performance is required, but awesome
>> FP is not
>> e) the API should be simple enough to understand
>> f) it should be easy to carve out sub-matrices for sending to
>> different reducers
>> g) a reasonable set of matrix operations should be supported, these
>> should eventually include:
>> simple matrix-matrix and matrix-vector and matrix-scalar linear
>> algebra operations, A B, A + B, A v, A + x, v + x, u + v, dot(u, v)
>> row and column sums
>> generalized level 2 and 3 BLAS primitives, alpha A B + beta C
>> and A u + beta v
>> h) easy and efficient iteration constructs, especially for sparse
>> matrices
>> i) easy to extend with new implementations
>
> --
> This message is automatically generated by JIRA.
> -
> You can reply to this email to add a comment to the issue online.
>
--------------------------
Grant Ingersoll
http://www.lucenebootcamp.com
Next Training: April 7, 2008 at ApacheCon Europe in Amsterdam
Lucene Helpful Hints:
http://wiki.apache.org/lucene-java/BasicsOfPerformance
http://wiki.apache.org/lucene-java/LuceneFAQ