[Trilinos-Users] [EXTERNAL] compute eigenvalues of an ill-conditioned matrix

[Klinvex, Alicia Marie]

Hello Da,

You may be interested in the following paper: www.sandia.gov/~rblehou/anasazi-ug-public.pdf  It talks a bit about the various eigensolvers in Anasazi and which ones may be useful for certain types of graph problems.

Best wishes,
Alicia

-----Original Message-----
From: Da Zheng [mailto:zhengda1936 at gmail.com] 
Sent: Tuesday, March 14, 2017 9:10 AM
To: Klinvex, Alicia Marie <amklinv at sandia.gov>
Cc: trilinos-users at trilinos.org; Carey E Priebe <cep at jhu.edu>
Subject: Re: [EXTERNAL] [Trilinos-Users] compute eigenvalues of an ill-conditioned matrix

Hello Alicia,

Thank you for your reply.

On Tue, Mar 14, 2017 at 8:37 AM, Klinvex, Alicia Marie <amklinv at sandia.gov> wrote:
> Hello Da,
>
> Can you tell us more about your problem?  For instance, is your graph undirected, i.e. is your matrix symmetric?  Are you looking for the largest eigenpairs or the smallest?  How many are you computing?  How accurate do they need to be?  Are you explicitly forming the matrix whose eigenvalues are being computed?  How high is a very high condition number?

We are computing eigenvalues of an undirected graph right now. For a directed graph A, we compute the eigenvalues of A^TA, i.e., we compute SVD of A.
We are looking for 10s ~ 100s largest eigenpairs. We don't need to have very high precision. I think right now the precision we need is about 10e-5 ~ 10e-6.
For an undirected graph, we have its adjacency matrix. For a directed graph, we don't physically have A^TA. We compute A^T * (A * v) every time in the Anasazi eigensolver. I wonder how this will affect the accuracy?
We don't know how large the condition number is. We don't even know if the graph is full rank.

I'm also interested in the case that a graph is directed. For example, I'd like to use the eigensolver to compute PageRank of our giant graph. In this case, I need to the eigenvector for the largest eigenvalue and I only need one eigenvector.

Thanks,
Da

>
> Best wishes,
> Alicia
>
> -----Original Message-----
> From: Trilinos-Users [mailto:trilinos-users-bounces at trilinos.org] On 
> Behalf Of Da Zheng
> Sent: Saturday, March 11, 2017 10:26 AM
> To: trilinos-users at trilinos.org
> Cc: Carey E Priebe <cep at jhu.edu>
> Subject: [EXTERNAL] [Trilinos-Users] compute eigenvalues of an 
> ill-conditioned matrix
>
> Hello,
>
> I'm trying to use the Anasazi eigensolvers to compute spectral embedding of a very large graph (|V| ~ 4 billion and |E| ~ 129 billion). I'm just curious if the eigensolvers such as Krylov Schur can compute eigenvalues with a high precision even if the sparse matrix has a very high condition number?
>
> Thanks,
> Da
> _______________________________________________
> Trilinos-Users mailing list
> Trilinos-Users at trilinos.org
> https://trilinos.org/mailman/listinfo/trilinos-users