FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups 
 ProfileProfile   PreferencesPreferences   Log in to check your private messagesLog in to check your private messages   Log inLog in 
Forum index » Science and Technology » Math » num-analysis
Bound on nnz for sparse matrix product
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
Author Message
Scott Kilpatrick
science forum beginner


Joined: 12 Jul 2006
Posts: 2

PostPosted: Thu Jul 13, 2006 12:58 am    Post subject: Re: Bound on nnz for sparse matrix product Reply with quote

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
Peter Spellucci
science forum Guru


Joined: 29 Apr 2005
Posts: 702

PostPosted: Wed Jul 12, 2006 9:15 pm    Post subject: Re: Bound on nnz for sparse matrix product Reply with quote

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
Robert B. Israel
science forum Guru


Joined: 24 Mar 2005
Posts: 2151

PostPosted: Wed Jul 12, 2006 9:09 pm    Post subject: Re: Bound on nnz for sparse matrix product Reply with quote

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
Scott Kilpatrick
science forum beginner


Joined: 12 Jul 2006
Posts: 2

PostPosted: Wed Jul 12, 2006 4:24 pm    Post subject: Bound on nnz for sparse matrix product Reply with 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
Back to top
Google

Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [4 Posts] View previous topic :: View next topic
The time now is Thu Oct 30, 2014 3:38 am | All times are GMT
Forum index » Science and Technology » Math » num-analysis
Jump to:  

Similar Topics
Topic Author Forum Replies Last Post
No new posts Diagonalizable matrix aline Math 0 Wed Nov 29, 2006 3:08 am
No new posts sign of the determinant of an augmented matrix? Mark Math 4 Thu Jul 20, 2006 1:30 am
No new posts spectrum of a symmetric tridiagonal random matrix pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Research 0 Mon Jul 17, 2006 2:24 pm
No new posts Complexity of Sparse Cholesky Factorization crazyFritz Math 5 Mon Jul 17, 2006 1:31 pm

Copyright © 2004-2005 DeniX Solutions SRL
Other DeniX Solutions sites: Electronics forum |  Medicine forum |  Unix/Linux blog |  Unix/Linux documentation |  Unix/Linux forums  |  send newsletters
 


Powered by phpBB © 2001, 2005 phpBB Group
[ Time: 0.0701s ][ Queries: 20 (0.0381s) ][ GZIP on - Debug on ]