You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@systemml.apache.org by Nakul Jindal <na...@gmail.com> on 2017/06/20 19:06:19 UTC
Sparsity estimates for Matrix Multiplication
Hi,
There is code in systemml to “estimate” the output sparsity of a matrix
multiplication operation between two sparse matrices.
Is there a citation for this? If not, have we done any tests to figure out
how good these estimates are?
https://github.com/nakul02/systemml/blob/df8d4a63d8d09cae94b6ca2634e31da554302c72/src/main/java/org/apache/sysml/hops/OptimizerUtils.java#L944-L953
Thanks,
Nakul
Re: Sparsity estimates for Matrix Multiplication
Posted by Dylan Hutchison <dh...@cs.washington.edu>.
Hi Nakul,
The paper I referenced uses the term "Boolean matrix", but really it
applies to any matrix product in which two properties hold:
1. Zero product property. a * b = 0 ==> a = 0 or b = 0
2. Few, if any, "sums to zero". There should be few cases of nonzero
partial products summing to zero.
Property #1 holds for standard arithmetic * over the reals. If we multiply
matrices with positive entries, then there are no sums to zero. Otherwise,
if there are many positive and negative entries, the number of nonzero
entries in the result may be fewer than the paper's algorithm would predict.
Specifically, under these two properties, nnz( A * B ) = nnz( ||A||_0 *
||B||_0 ), where ||A||_0 is the "zero norm", which maps nonzero entries to
1 and zero entries to 0.
I don't know about the origin of the current heuristic for SystemML.
Cheers, Dylan
On Tue, Jun 20, 2017 at 2:00 PM, Nakul Jindal <na...@gmail.com> wrote:
> Thank you Dylan. The paper seems interesting. The abstract reads as follows
> : "We consider the problem of doing fast and reliable estimation of the
> number z of non-zero entries in a sparse boolean matrix product"...
> I think they maybe doing this for boolean matrices. The code that I pointed
> to in SystemML is used for all matrices.
> I am not sure if and how their technique translates to non-boolean
> matrices.
>
> Also, I am asking for an explanation of what is implemented as opposed to
> what can be.
> I was wondering if the neat looking formula has been gotten from some
> literature somewhere?
>
> -Nakul
>
>
>
>
> On Tue, Jun 20, 2017 at 1:42 PM, Dylan Hutchison <
> dhutchis@cs.washington.edu
> > wrote:
>
> > In case it is helpful, this 2010 paper
> > <https://www.semanticscholar.org/paper/Better-Size-
> > Estimation-for-Sparse-Matrix-Products-Amossen-Campagna/
> > 52f70406bb4d887e1b79af81a746184c5723848a>
> > is my favorite for estimating the nnz of a matrix product with high
> > confidence. The algorithm is much more involved than the simple SystemML
> > calculation, because it looks at samples from the actual data.
> >
> > Here are some notes I have on the paper:
> >
> > There is a sketch algorithm [2] that gives a (1 + ε) approximation z̃ to
> z
> > for any ε > 4 / (z^.25) in O(m)
> > time and with a bound on the number of I/Os. In relational algebra, this
> is
> > estimating
> > |π_{ik}( A(i, j) ⋈ B(j, k) )|. The idea behind the algorithm is finding,
> > for some tuning parameter
> > k that varies with z, the k-smallest value of a hash function h(i; k).
> The
> > larger this value is, the more
> > is and ks that match for a given j. Repeat this for all js. Different (i,
> > k)s contribute to different entries
> > in the result matrix and have different hash values. A sketch for this
> > algorithm can be incrementally
> > maintained via independent samples on is and ks. Computing the z̃
> estimate
> > from the sample takes o(n)
> > time for large enough z. The larger z is, the smaller a sample size we
> > need. (Need large samples for
> > small z.) (Everything above assumes the zero product property and
> > zero-sum-free).
> >
> >
> >
> > On Tue, Jun 20, 2017 at 12:06 PM, Nakul Jindal <na...@gmail.com>
> wrote:
> >
> > > Hi,
> > >
> > > There is code in systemml to “estimate” the output sparsity of a matrix
> > > multiplication operation between two sparse matrices.
> > > Is there a citation for this? If not, have we done any tests to figure
> > out
> > > how good these estimates are?
> > > https://github.com/nakul02/systemml/blob/df8d4a63d8d09cae94b
> > > 6ca2634e31da554302c72/src/main/java/org/apache/sysml/
> > > hops/OptimizerUtils.java#L944-L953
> > >
> > > Thanks,
> > > Nakul
> > >
> >
>
Re: Sparsity estimates for Matrix Multiplication
Posted by Nakul Jindal <na...@gmail.com>.
Thank you Dylan. The paper seems interesting. The abstract reads as follows
: "We consider the problem of doing fast and reliable estimation of the
number z of non-zero entries in a sparse boolean matrix product"...
I think they maybe doing this for boolean matrices. The code that I pointed
to in SystemML is used for all matrices.
I am not sure if and how their technique translates to non-boolean matrices.
Also, I am asking for an explanation of what is implemented as opposed to
what can be.
I was wondering if the neat looking formula has been gotten from some
literature somewhere?
-Nakul
On Tue, Jun 20, 2017 at 1:42 PM, Dylan Hutchison <dhutchis@cs.washington.edu
> wrote:
> In case it is helpful, this 2010 paper
> <https://www.semanticscholar.org/paper/Better-Size-
> Estimation-for-Sparse-Matrix-Products-Amossen-Campagna/
> 52f70406bb4d887e1b79af81a746184c5723848a>
> is my favorite for estimating the nnz of a matrix product with high
> confidence. The algorithm is much more involved than the simple SystemML
> calculation, because it looks at samples from the actual data.
>
> Here are some notes I have on the paper:
>
> There is a sketch algorithm [2] that gives a (1 + ε) approximation z̃ to z
> for any ε > 4 / (z^.25) in O(m)
> time and with a bound on the number of I/Os. In relational algebra, this is
> estimating
> |π_{ik}( A(i, j) ⋈ B(j, k) )|. The idea behind the algorithm is finding,
> for some tuning parameter
> k that varies with z, the k-smallest value of a hash function h(i; k). The
> larger this value is, the more
> is and ks that match for a given j. Repeat this for all js. Different (i,
> k)s contribute to different entries
> in the result matrix and have different hash values. A sketch for this
> algorithm can be incrementally
> maintained via independent samples on is and ks. Computing the z̃ estimate
> from the sample takes o(n)
> time for large enough z. The larger z is, the smaller a sample size we
> need. (Need large samples for
> small z.) (Everything above assumes the zero product property and
> zero-sum-free).
>
>
>
> On Tue, Jun 20, 2017 at 12:06 PM, Nakul Jindal <na...@gmail.com> wrote:
>
> > Hi,
> >
> > There is code in systemml to “estimate” the output sparsity of a matrix
> > multiplication operation between two sparse matrices.
> > Is there a citation for this? If not, have we done any tests to figure
> out
> > how good these estimates are?
> > https://github.com/nakul02/systemml/blob/df8d4a63d8d09cae94b
> > 6ca2634e31da554302c72/src/main/java/org/apache/sysml/
> > hops/OptimizerUtils.java#L944-L953
> >
> > Thanks,
> > Nakul
> >
>
Re: Sparsity estimates for Matrix Multiplication
Posted by Dylan Hutchison <dh...@cs.washington.edu>.
In case it is helpful, this 2010 paper
<https://www.semanticscholar.org/paper/Better-Size-Estimation-for-Sparse-Matrix-Products-Amossen-Campagna/52f70406bb4d887e1b79af81a746184c5723848a>
is my favorite for estimating the nnz of a matrix product with high
confidence. The algorithm is much more involved than the simple SystemML
calculation, because it looks at samples from the actual data.
Here are some notes I have on the paper:
There is a sketch algorithm [2] that gives a (1 + ε) approximation z̃ to z
for any ε > 4 / (z^.25) in O(m)
time and with a bound on the number of I/Os. In relational algebra, this is
estimating
|π_{ik}( A(i, j) ⋈ B(j, k) )|. The idea behind the algorithm is finding,
for some tuning parameter
k that varies with z, the k-smallest value of a hash function h(i; k). The
larger this value is, the more
is and ks that match for a given j. Repeat this for all js. Different (i,
k)s contribute to different entries
in the result matrix and have different hash values. A sketch for this
algorithm can be incrementally
maintained via independent samples on is and ks. Computing the z̃ estimate
from the sample takes o(n)
time for large enough z. The larger z is, the smaller a sample size we
need. (Need large samples for
small z.) (Everything above assumes the zero product property and
zero-sum-free).
On Tue, Jun 20, 2017 at 12:06 PM, Nakul Jindal <na...@gmail.com> wrote:
> Hi,
>
> There is code in systemml to “estimate” the output sparsity of a matrix
> multiplication operation between two sparse matrices.
> Is there a citation for this? If not, have we done any tests to figure out
> how good these estimates are?
> https://github.com/nakul02/systemml/blob/df8d4a63d8d09cae94b
> 6ca2634e31da554302c72/src/main/java/org/apache/sysml/
> hops/OptimizerUtils.java#L944-L953
>
> Thanks,
> Nakul
>