commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Ted Dunning <ted.dunn...@gmail.com>
Subject Re: [Math] "iterator" and "sparseIterator" in "RealVector" hierarchy
Date Wed, 17 Aug 2011 18:46:03 GMT
I would think neither.

I think it should mean that the sparseIterator will be enough faster than
the dense iterator to make it worth using.  The indication doesn't have to
be be crisp or even always quite correct.  Thus, a densely filled
OpenMapReal might just return true because that usage is out of the
ordinary.

Regarding what the sparseIterator returns, skipping zeroes is a fine idea,
but the contract should really be that all non-zeros will be returned rather
than no zeros will be returned.  There should be flexibility to return zero
values if that is much more convenient, but there should be no case where a
non-zero is missed.

Regarding the additional indicators, these are occasionally useful in
particular cases, but many of those special cases actually work out just as
well if you simply treat them as sparse.  As an example, multiplication by a
diagonal matrix can be special cased, but simply iterating over the
non-zeros (i.e. the diagonal) is just as good.  Matrix power is a
counter-example where the computation can be reduced to element-wise power
for diagonal, but not for sparse.  Even so, the sparse implementation is
surprisingly competitive even there especially for small powers if you have
a special sparse-sparse multiply.  Mahout has an additional indicator
function that tells whether sparseIterator returns items in a sequential
order which can reduce many of these cases to a merge.

For banded arrays, the economies available beyond simple sparse algorithms
are even more limited.

Symmetric and triangular matrices also have special properties but it is
hard to decide what is really important there.  Many of the special
operations for these kinds of matrix are subject to solving by overloads
instead of indicators since we aren't dealing with binary operations.  For
example, left and right inverse multiplication with triangular matrices is
handled by normal single dispatch and qualifying an argument for real
Cholesky decomposition is specific to the Cholesky decomposition itself.

On Wed, Aug 17, 2011 at 11:28 AM, Arne Ploese <aploese@gmx.de> wrote:

> So what exactly is the meaning of isSparse?
>
> * the vector at hand implements some kind of sparse storage? I.E:
> OpenMapRealVector
>
> or
>
> * the vector is actually sparsely filled (then what is sparse anyway
> 10%, 50%, 90%?) in this case a SparserelVector interface is useless for
> the compiler.
>
> My suggestion is: ArrayRealVector implements a sparse iterator which
> returns only values != 0?
>
> Having the backing storage implementation open, one could think of:
>
> * isArray
> * isBanded
> * isSymetrical
> * isDiagonal
>
> as additional markers or put the whole thing in an enum or EnumSet?
>
> Am Mittwoch, den 17.08.2011, 08:51 -0700 schrieb Ted Dunning:
> > I think that all vectors and matrices should be able to answer the
> question
> > about whether they are sparse and they should support sparse iterators,
> > defaulting to the normal iterators in the general case.  So yes to the
> first
> > question.  This allows the application programmer to be much less
> concerned
> > about whether they are using a sparse or dense matrix without losing much
> > performance, if any.
> >
> > The second question I think is much less clear.  It might well be a good
> > idea to keep the interface to help the compiler in cases where the
> > programmer knows which general class of matrix they have.
> >
> > On Wed, Aug 17, 2011 at 8:29 AM, Arne Ploese <aploese@gmx.de> wrote:
> >
> > > Am Mittwoch, den 17.08.2011, 07:25 -0700 schrieb Ted Dunning:
> > > > Arne,
> > > >
> > > > Please read the thread again.  I am providing an example of how I
> think
> > > > things *should* be.
> > > OK.
> > > if I understand you right: isSparse() should be added to RealVector and
> > > the interface SparseRealVector can be dropped?
> > >
> > > >
> > > > The point of doing so is that things are not that way now.  Telling
> me
> > > that
> > > > they are not that way is pretty redundant.
> > > >
> > > > On Wed, Aug 17, 2011 at 2:37 AM, Arne Ploese <aploese@gmx.de> wrote:
> > > >
> > > > > Currently sparseIterator is only used in RealVector, no matrix
> class
> > > > > will be affected, because there is no sparseIterator.
> > > > > Search you sources for "sparseIterator" ?
> > > > >
> > > > > Arne
> > > > > Am Dienstag, den 16.08.2011, 14:09 -0700 schrieb Ted Dunning:
> > > > > > Here is an example from the perspective of somebody adding a
new
> kind
> > > of
> > > > > > matrix.
> > > > > >
> > > > > > Take the two kinds of matrix as RandomTrinaryMatrix(rows,
> columns, p)
> > > > > that
> > > > > > has elements that are -1, 0 or 1.  1 and -1 have equal
> probabilities
> > > of
> > > > > p/2.
> > > > > >  The value of p should be in [0,1].
> > > > > >
> > > > > > It would be very nice if the implementor of this matrix could
> extend
> > > an
> > > > > > abstract matrix and over-ride get() to generate a value and
set()
> to
> > > > > throw
> > > > > > an unsupported operation exception.  If p < 0.1, then the
matrix
> > > should
> > > > > be
> > > > > > marked as sparse, else as dense.
> > > > > >
> > > > > > All operations against other matrices, sparse or dense should
> work
> > > well
> > > > > > without any special handling by the implementor of this matrix.
> > > > > >
> > > > > > This works in Mahout for instance by having the default
> operations in
> > > > > > AbstractMatrix test for sparseness of left or right operands
and
> do
> > > the
> > > > > > right thing.  Obviously, a type test will not tell you whether
> this
> > > > > matrix
> > > > > > is sparse or not.
> > > > > >
> > > > > > This matrix and siblings is very important in compressed sensing
> and
> > > > > > stochastic projection algorithms.
> > > > > >
> > > > > > On Tue, Aug 16, 2011 at 1:55 PM, Phil Steitz <
> phil.steitz@gmail.com>
> > > > > wrote:
> > > > > >
> > > > > > > On 8/16/11 4:46 AM, Gilles Sadowski wrote:
> > > > > > > > Hi.
> > > > > > > >
> > > > > > > >> I understood what he was suggesting.  I still
disagree.
>  Dynamic
> > > > > > > dispatch
> > > > > > > >> and non-lattice typing structure is still required
to make
> this
> > > all
> > > > > > > work.
> > > > > > > >>  Java doesn't really do that.  Pretending that
what Java
> does is
> > > > > > > sufficient
> > > > > > > >> is hammer-looking-for-a-nail, not solving the
problems at
> hand.
> > > > > > > > Maybe that *I* don't understand what you are hinting
at.
> Sorry
> > > for
> > > > > being
> > > > > > > > dense. [Although that seems appropriate in this discussion
> :-).]
> > > > > > > >
> > > > > > > > Polymorphism provides dynamic dispatch, overloading
does not;
> > > that's
> > > > > why
> > > > > > > my
> > > > > > > > proposition is that when you manipulate "unknown"
types,
> those
> > > should
> > > > > > > come
> > > > > > > > as "this", not as the argument of the method.
> > > > > > > >
> > > > > > > > What's wrong with that?
> > > > > > > >
> > > > > > > > As for "hammer-looking-for-a-nail", I also don't see
what you
> > > mean:
> > > > > What
> > > > > > > is
> > > > > > > > the problem? I guess that there are lots of applications
who
> > > never
> > > > > need
> > > > > > > to
> > > > > > > > know about sparse vectors/matrices. In those cases,
the added
> > > > > complexity
> > > > > > > is
> > > > > > > > not a "feature". The issue reported contends that
the current
> > > design
> > > > > in
> > > > > > > CM
> > > > > > > > can cause problems for dense implementations. I'm
not even
> sure
> > > that
> > > > > the
> > > > > > > > current design is usable for the type of applications
that
> make
> > > heavy
> > > > > use
> > > > > > > of
> > > > > > > > sparseness. Those are problems, IMHO.
> > > > > > >
> > > > > > > I have been out of pocket the last couple of days and may
not
> have
> > > > > > > time to dig into this until late tonight, but I agree with
> Gilles
> > > > > > > that we need to get the conversation here more concrete.
 I
> know we
> > > > > > > discussed this before and Ted and others had good examples
> > > > > > > justifying the current setup.  Can we revisit these, please?
> What
> > > > > > > would be great would be some examples both from the perspective
> of
> > > > > > > the [math] developer looking to add a new or specialized
class
> and
> > > > > > > [math] users writing code that leverages the setup.
> > > > > > >
> > > > > > > Phil
> > > > > > > >
> > > > > > > >
> > > > > > > > Gilles
> > > > > > > >
> > > > > > > >> On Mon, Aug 15, 2011 at 6:52 PM, Greg Sterijevski
<
> > > > > > > gsterijevski@gmail.com>wrote:
> > > > > > > >>
> > > > > > > >>> Forgive me for pushing my nose under the tent...
I couldn't
> > > resist.
> > > > > > > >>>
> > > > > > > >>> I think Gilles is saying that each specialization
of the
> > > > > matrix/vector
> > > > > > > >>> objects would need to support pre (and post)
multiplication
> > > with a
> > > > > > > dense.
> > > > > > > >>> So
> > > > > > > >>> the type issue would not be problematic.
> > > > > > > >>>
> > > > > > > >>> On Mon, Aug 15, 2011 at 6:34 PM, Ted Dunning
<
> > > > > ted.dunning@gmail.com>
> > > > > > > >>> wrote:
> > > > > > > >>>
> > > > > > > >>>> No.
> > > > > > > >>>>
> > > > > > > >>>> You can't.  This is because the type is
lost as you enter
> the
> > > > > generic
> > > > > > > >>>> library.
> > > > > > > >>>>
> > > > > > > >>>> On Mon, Aug 15, 2011 at 4:28 PM, Gilles
Sadowski <
> > > > > > > >>>> gilles@harfang.homelinux.org> wrote:
> > > > > > > >>>>
> > > > > > > >>>>>> They know that their own object
is dense, but they don't
> > > know
> > > > > what
> > > > > > > >>> kind
> > > > > > > >>>>> of
> > > > > > > >>>>>> input they were given.  They should
still run fast if
> the
> > > input
> > > > > is
> > > > > > > >>>>> sparse.
> > > > > > > >>>>>
> > > > > > > >>>>> Couldn't we still rely on polymorphism
by implementing
> > > > > "preTimes":
> > > > > > > >>>>>   unknown.preTimes(dense)
> > > > > > > >
> > > ---------------------------------------------------------------------
> > > > > > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > > > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > > > > > >
> > > > > > > >
> > > > > > >
> > > > > > >
> > > > > > >
> > > ---------------------------------------------------------------------
> > > > > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > > > > >
> > > > > > >
> > > > >
> > > > >
> > > > >
> > > > >
> ---------------------------------------------------------------------
> > > > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > > > For additional commands, e-mail: dev-help@commons.apache.org
> > > > >
> > > > >
> > >
> > >
> > >
> > > ---------------------------------------------------------------------
> > > To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> > > For additional commands, e-mail: dev-help@commons.apache.org
> > >
> > >
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message