Author 
Message 
Scott Kilpatrick science forum beginner
Joined: 12 Jul 2006
Posts: 2

Posted: Wed Jul 12, 2006 4:24 pm Post subject:
Bound on nnz for sparse matrix product



I have been searching around but haven't seen an answer to this
question. Is there a bound on the number of nonzero elements in the
product of two sparse matrices? For example,
C = A*B
nnza = # nonzero elements in A
nnzb = # nonzero elements in B
nnzc = f(nnza, nnzb) ?
My intuition tells me no, but it would be nice to know how much storage
to allocate for the product. Right now in my tests, I'm using nnzcmax =
4*(nnza+nnzb) and it's not enough for large matrices ((4000 x 100000) *
(100000 x 100000)). I have a subroutine to extend the allocated storage
capacity, but it's extremely slow when it's allocating 415999992
doubles and 415999992 ints, plus copying over the 207999996 original
elements (this is in Fortran 90 btw).
Scott 

Back to top 


Robert B. Israel science forum Guru
Joined: 24 Mar 2005
Posts: 2151

Posted: Wed Jul 12, 2006 9:09 pm Post subject:
Re: Bound on nnz for sparse matrix product



In article <1152721486.898194.94110@b28g2000cwb.googlegroups.com>,
Scott Kilpatrick <skilpat@gmail.com> wrote:
Quote:  I have been searching around but haven't seen an answer to this
question. Is there a bound on the number of nonzero elements in the
product of two sparse matrices? For example,
C = A*B
nnza = # nonzero elements in A
nnzb = # nonzero elements in B
nnzc = f(nnza, nnzb) ?

In terms of nnza and nnzb, the optimal bound is nnza nnzb, which
is attained if for some k, all nonzeros of A are in the k'th column and
all nonzeros of B are in the k'th row.
However, you might do better if you have more detailed information.
Let nzrb be the maximum number of nonzeros in a row of B, and
nzca the maximum number of nonzeros in a column of A. Then
nnzc <= min(nnza nzrb, nzca nnzb).
If A and B are m x n and n x p and the nonzeros occur randomly
in both (i.e. the nonzeros of A are a random selection of
nnza out of the mn entries of A, and similarly for B), the
expected number of nonzeros in C is at most nnza nnzb/n.
Robert Israel israel@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada 

Back to top 


Peter Spellucci science forum Guru
Joined: 29 Apr 2005
Posts: 702

Posted: Wed Jul 12, 2006 9:15 pm Post subject:
Re: Bound on nnz for sparse matrix product



In article <1152721486.898194.94110@b28g2000cwb.googlegroups.com>,
"Scott Kilpatrick" <skilpat@gmail.com> writes:
Quote:  I have been searching around but haven't seen an answer to this
question. Is there a bound on the number of nonzero elements in the
product of two sparse matrices? For example,
C = A*B
nnza = # nonzero elements in A
nnzb = # nonzero elements in B
nnzc = f(nnza, nnzb) ?
My intuition tells me no, but it would be nice to know how much storage
to allocate for the product. Right now in my tests, I'm using nnzcmax =
4*(nnza+nnzb) and it's not enough for large matrices ((4000 x 100000) *
(100000 x 100000)). I have a subroutine to extend the allocated storage
capacity, but it's extremely slow when it's allocating 415999992
doubles and 415999992 ints, plus copying over the 207999996 original
elements (this is in Fortran 90 btw).
Scott

with no additional information on the matrix there can be no reasonable bound
on this:
take
A= [ e , O , O , ... , O , O ]
B= [ e' ; O' ; O' ...... O']
O a n by 1 vector of zeros, e a vector of ones
then
nnza=n nnzb=n but nnz(A*B) = n^2 .
hth
peter 

Back to top 


Scott Kilpatrick science forum beginner
Joined: 12 Jul 2006
Posts: 2

Posted: Thu Jul 13, 2006 12:58 am Post subject:
Re: Bound on nnz for sparse matrix product



Peter Spellucci wrote:
Quote: 
with no additional information on the matrix there can be no reasonable bound
on this:
take
A= [ e , O , O , ... , O , O ]
B= [ e' ; O' ; O' ...... O']
O a n by 1 vector of zeros, e a vector of ones
then
nnza=n nnzb=n but nnz(A*B) = n^2 .
hth
peter

Robert and Peter, thank you very much for your responses. This helps a
bunch!
Scott 

Back to top 


Google


Back to top 



The time now is Fri Aug 17, 2018 6:12 am  All times are GMT

