FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 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
nnz in convariance of a sparse matrix
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
Author Message
H. S.
science forum beginner


Joined: 02 May 2005
Posts: 23

PostPosted: Mon May 02, 2005 8:33 pm    Post subject: nnz in convariance of a sparse matrix Reply with quote
If a sparse matrix A has n nnz (number of non-zero elements), how many
nnz does A'A have, where A' is the transpose of A?

I am tring to allocate space (in a C++ program) for the covariance of A,
where A is sparse. A is real, square and it's each column has exactly r
non-zero elements. So, if A is NxN, it has rxN non-zero elements, where
r is a positive integer: r << N.

Is there a relationship which gives the max nnz in A'A? Or if you can
give me references or URLs where I can read about this, it would be
great too.

thanks,
->HS
--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)
Back to top
Fred Krogh
science forum beginner


Joined: 02 May 2005
Posts: 24

PostPosted: Mon May 02, 2005 9:04 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
H. S. wrote:
Quote:

If a sparse matrix A has n nnz (number of non-zero elements), how many
nnz does A'A have, where A' is the transpose of A?

I am tring to allocate space (in a C++ program) for the covariance of A,
where A is sparse. A is real, square and it's each column has exactly r
non-zero elements. So, if A is NxN, it has rxN non-zero elements, where
r is a positive integer: r << N.

Is there a relationship which gives the max nnz in A'A? Or if you can
give me references or URLs where I can read about this, it would be
great too.

You are probably not going to get much useful unless you can provide
more information about your matrix. If A has n nonzeros and all of them
are in one row, then A'A will have n^2 nonzeros.
Regards,
Fred
Back to top
H. S.
science forum beginner


Joined: 02 May 2005
Posts: 23

PostPosted: Tue May 03, 2005 1:24 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
Apparently, _Fred Krogh_, on 05/02/2005 07:04 PM,typed:
Quote:
H. S. wrote:


If a sparse matrix A has n nnz (number of non-zero elements), how many
nnz does A'A have, where A' is the transpose of A?

I am tring to allocate space (in a C++ program) for the covariance of
A, where A is sparse. A is real, square and it's each column has
exactly r non-zero elements. So, if A is NxN, it has rxN non-zero
elements, where r is a positive integer: r << N.

Is there a relationship which gives the max nnz in A'A? Or if you can
give me references or URLs where I can read about this, it would be
great too.


You are probably not going to get much useful unless you can provide
more information about your matrix. If A has n nonzeros and all of them
are in one row, then A'A will have n^2 nonzeros.
Regards,
Fred

The only contraint is that there are r non-zeros in each column. And
those nnz can be in different rows in different columns.

->HS

--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)
Back to top
Hiu Chung Law
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Tue May 03, 2005 3:59 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
H. S. <g_reate_xcalibur@yahoo.com> wrote:

Quote:
If a sparse matrix A has n nnz (number of non-zero elements), how many
nnz does A'A have, where A' is the transpose of A?

I am tring to allocate space (in a C++ program) for the covariance of A,
where A is sparse. A is real, square and it's each column has exactly r
non-zero elements. So, if A is NxN, it has rxN non-zero elements, where
r is a positive integer: r << N.

Is there a relationship which gives the max nnz in A'A? Or if you can
give me references or URLs where I can read about this, it would be
great too.

thanks,
->HS
--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)

What is the use of the covariance matrix? If, for example, you want
to find the eigenvectors of the covariance matrix, you do not need to
form A' A explicitly.
Back to top
H. S.
science forum beginner


Joined: 02 May 2005
Posts: 23

PostPosted: Tue May 03, 2005 4:58 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
Apparently, _Hiu Chung Law_, on 05/03/2005 01:59 PM,typed:

Quote:

What is the use of the covariance matrix? If, for example, you want
to find the eigenvectors of the covariance matrix, you do not need to
form A' A explicitly.


Yes, I am trying to find eigenvectors of the covariance matrix. To be
more precide, I am trying to find eigenvectors of (I-A)'(I-A) where I is
an identity matrix, A is a square sparse matrix and X' denotes transpose
of matrix X. Could you elaborate on your comment above?

thanks,
->HS

--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)
Back to top
Hiu Chung Law
science forum beginner


Joined: 03 May 2005
Posts: 18

PostPosted: Wed May 04, 2005 1:34 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
H. S. <g_reate_xcalibur@yahoo.com> wrote:
Quote:
Apparently, _Hiu Chung Law_, on 05/03/2005 01:59 PM,typed:


What is the use of the covariance matrix? If, for example, you want
to find the eigenvectors of the covariance matrix, you do not need to
form A' A explicitly.


Yes, I am trying to find eigenvectors of the covariance matrix. To be
more precide, I am trying to find eigenvectors of (I-A)'(I-A) where I is
an identity matrix, A is a square sparse matrix and X' denotes transpose
of matrix X. Could you elaborate on your comment above?

thanks,
->HS

--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)

You should use an eigen-solver which uses a function for matrix multiplication.
Let M = (I-A)'(I-A). Instead of forming M explicitly, you can write a function
which computes M x for any vector x. In other words,

function y = fun(x,A)
y = (I-A) * x ;
y = (I-A)' * y ;
return;

Note that the multiplication is fast because I-A is a sparse matrix.

Some eigensolvers allow you to specify the function "fun" instead
of the matrix M. For example, the matlab command "eigs" allows you to
do this.

The simplest way to find eigenvectors which uses only matrix
multiplication is the power method, assuming that the largest
eigenvalue of M is simple.

Alternatively, you can check out various versions of Lanczos method.
Back to top
H. S.
science forum beginner


Joined: 02 May 2005
Posts: 23

PostPosted: Wed May 04, 2005 6:21 pm    Post subject: Re: nnz in convariance of a sparse matrix Reply with quote
Apparently, _Hiu Chung Law_, on 05/04/2005 11:34 AM,typed:
Quote:
H. S. <g_reate_xcalibur@yahoo.com> wrote:

Apparently, _Hiu Chung Law_, on 05/03/2005 01:59 PM,typed:


What is the use of the covariance matrix? If, for example, you want
to find the eigenvectors of the covariance matrix, you do not need to
form A' A explicitly.



Yes, I am trying to find eigenvectors of the covariance matrix. To be
more precide, I am trying to find eigenvectors of (I-A)'(I-A) where I is
an identity matrix, A is a square sparse matrix and X' denotes transpose
of matrix X. Could you elaborate on your comment above?


thanks,
->HS


--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)


You should use an eigen-solver which uses a function for matrix multiplication.
Let M = (I-A)'(I-A). Instead of forming M explicitly, you can write a function
which computes M x for any vector x. In other words,

function y = fun(x,A)
y = (I-A) * x ;
y = (I-A)' * y ;
return;

Note that the multiplication is fast because I-A is a sparse matrix.

Some eigensolvers allow you to specify the function "fun" instead
of the matrix M. For example, the matlab command "eigs" allows you to
do this.

The simplest way to find eigenvectors which uses only matrix
multiplication is the power method, assuming that the largest
eigenvalue of M is simple.

Alternatively, you can check out various versions of Lanczos method.


I have ARPACK in mind to compute eigenvectors. I can see how what you
explained above can be useful. Since I am want the eigenvalues of
M=(I-A)'(I-A), and since ARPACK library just needs the product y= Mx =
(I-A)'(I-A)x = (I-A)'z, I don't need the cov matrix at all.

And I am looking at spblas library to get A*x where A is a sparse matrix.

Thanks for the explanation and help.

regards,
->HS
--
(Remove all underscores,if any, from my email address to get the correct
one. Apologies for the inconvenience but this is to reduce spam.)
Back to top
Google
Back to top
Display posts from previous:   
Post new topic   Reply to topic Page 1 of 1 [7 Posts] View previous topic :: View next topic
The time now is Fri Jul 30, 2010 5:42 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 augment... Mark Math 4 Thu Jul 20, 2006 1:30 am
No new posts spectrum of a symmetric tridiagonal r... pf.buonsante@gmail.com Math 0 Wed Jul 19, 2006 9:45 am
No new posts Complexity of Sparse Cholesky Factori... crazyFritz Research 0 Mon Jul 17, 2006 2:24 pm
No new posts Complexity of Sparse Cholesky Factori... 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


Powered by phpBB © 2001, 2005 phpBB Group

[ Time: 0.0409s ][ Queries: 14 (0.0077s) ][ GZIP on - Debug on ]