Search   Memberlist   Usergroups
 Page 1 of 1 [4 Posts]
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
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

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
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

"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
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

 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
 Page 1 of 1 [4 Posts]
 The time now is Tue Mar 26, 2019 3:52 am | All times are GMT
 Jump to: Select a forum-------------------Forum index|___Science and Technology    |___Math    |   |___Research    |   |___num-analysis    |   |___Symbolic    |   |___Combinatorics    |   |___Probability    |   |   |___Prediction    |   |       |   |___Undergraduate    |   |___Recreational    |       |___Physics    |   |___Research    |   |___New Theories    |   |___Acoustics    |   |___Electromagnetics    |   |___Strings    |   |___Particle    |   |___Fusion    |   |___Relativity    |       |___Chem    |   |___Analytical    |   |___Electrochem    |   |   |___Battery    |   |       |   |___Coatings    |       |___Engineering        |___Control        |___Mechanics        |___Chemical

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