[Trilinos-Users] Sparse matrix and Anasazi Solvers,

Alicia Klinvex aklinvex at purdue.edu
Tue Feb 10 10:07:49 MST 2015 

I don't personally deal with complex Hermitian matrices, but I think it
would still work.  Your shift won't always be 5, but you can obtain it
using the Gershgorin circle theorem (
http://en.wikipedia.org/wiki/Gershgorin_circle_theorem); let me know if
that needs explanation.

If you want the smallest real rather than largest real, you can compute the
largest magnitude eigenvalues of C=(SHIFT I-A), where C is SPD and
\lambda_i = SHIFT - \sigma_i.

Best wishes,
Alicia

On Tue, Feb 10, 2015 at 10:59 AM, Mike Atambo <mikeat4999 at gmail.com> wrote:

> Alicia,
> Our matrices will include complex entries (i sent  one case),   but will
> always  be  Hermitian,  and we will only need the smallest real,
> will the suggestion extend to   complex hermitian matrices?  What do you
> think?
> Mike.
>
> On Tue, Feb 10, 2015 at 4:49 PM, Alicia Klinvex <aklinvex at purdue.edu>
> wrote:
>
>> Hello Mike,
>>
>> First, I'd like to supply some information about your problem to the
>> others on the mailing list.  The matrix you sent is order 100 million, with
>> 400 nonzeros.  The matrix is stored as complex general in the file, but it
>> is real symmetric indefinite, and we seek the smallest real or largest real.
>>
>> The eigenvalues of largest magnitude are (according to MATLAB)
>> >> eigs(A)
>>
>> ans =
>>
>>    -4.0000
>>     4.0000
>>    -3.6180
>>     3.6180
>>     3.2361
>>    -3.2361
>>
>> I misread your original email and thought you were trying to compute the
>> eigenvalues of smallest MAGNITUDE rather than smallest real, in which case
>> it would have made sense to use shift-and-invert.  Here's what I would do
>> if I were you:
>> Work with C=(A + 5 I).  That matrix is symmetric positive definite, and
>> if the eigenvalues of C are represented by sigma (and the eigenvalues of A
>> by lambda), then \lambda_i = \sigma_i - 5.  The eigenvectors will be the
>> same.  See if that works any better.  (That transformation also means that
>> asking for the eigenvalues of largest magnitude is the same as asking for
>> the largest real eigenvalues.)
>>
>> Let me know how it goes!
>>
>> - Alicia
>>
>> On Tue, Feb 10, 2015 at 8:48 AM, Mike Atambo <mikeat4999 at gmail.com>
>> wrote:
>>
>>> Alicia,
>>> i looked at the examples you suggested,  but im not sure i understand
>>> the shit-invert
>>> procedure,  is there and example  using the tpetra as opposed to Epetra
>>> objects?
>>> I have reduced the problem im having to a simple case, and a matrix
>>> sample that reproduces
>>> the convergence issue.  The matrix itself is quite small (sparse with
>>> 400 non zeros) in matrix market
>>> format.
>>> Convergence is not achieved with this matrix, using both the Block
>>> Davidson  and the Krylov-Shur solvers,
>>> i decided to attempt to find the largest real as opposed to the
>>> smallest,  but the behaviour seems
>>> the same,  therefore im inclined to think that it may not be that a
>>> shift-invert is not performed.
>>> Since the matrix is small, and these solvers should be able to work,
>>>  maybe there is something else going on,  id appreciate
>>> if an experienced eye took a look at my attempt,  as its likely there is
>>> something im unable to see.
>>>
>>> Regards
>>> Mike
>>>
>>> On Tue, Feb 10, 2015 at 2:14 PM, Mike Atambo <mikeat4999 at gmail.com>
>>> wrote:
>>>
>>>>
>>>>
>>>> On Thu, Feb 5, 2015 at 8:27 PM, Mike Atambo <mikeat4999 at gmail.com>
>>>> wrote:
>>>>
>>>>> Alicia,
>>>>> I will take a look at that  try it on my problem
>>>>> thanks,
>>>>> Mike
>>>>>
>>>>> On Thu, Feb 5, 2015 at 8:22 PM, Alicia Klinvex <aklinvex at purdue.edu>
>>>>> wrote:
>>>>>
>>>>>> Hello Mike,
>>>>>>
>>>>>> I'm pretty sure your Trilinos code is NOT using shift-and-invert with
>>>>>> BKS.  (Shift-and-invert is the spectral transformation I described before.)
>>>>>>  If you want to use shift-and-invert, you must construct the linear solver
>>>>>> yourself and give it to the BKS solver manager.  Some examples of that can
>>>>>> be found on this page:
>>>>>> http://trilinos.org/docs/r11.12/packages/anasazi/doc/html/examples.html
>>>>>>
>>>>>> If you want to use a sparse factorization, then the Amesos example
>>>>>> should be of interest to you.  If you want to use a preconditioned Krylov
>>>>>> method to solve the linear systems that arise at each iteration of BKS,
>>>>>> then look at the Belos example.  Let me know if those examples don't make
>>>>>> sense to you.
>>>>>>
>>>>>> Best wishes,
>>>>>> Alicia
>>>>>>
>>>>>> Disclaimer: I am an external collaborator at Sandia, and I did not
>>>>>> write the BKS code.  I can help you with the mechanics of getting things to
>>>>>> run, but Heidi Thornquist and Rich Lehoucq (who are also on the user
>>>>>> mailing list) would probably know more about how to get good performance
>>>>>> out of BKS and block Davidson.
>>>>>>
>>>>>> On Thu, Feb 5, 2015 at 1:50 PM, Mike Atambo <mikeat4999 at gmail.com>
>>>>>> wrote:
>>>>>>
>>>>>>> Alicia,
>>>>>>> Im still trying to figure  out what exactly im facing. Maybe what
>>>>>>> you described be the issue, but  at this
>>>>>>> point i would prefer to try out what you have suggested, if it
>>>>>>> works, then it would be certain thats what im facing,
>>>>>>> if not, then i can rule that out.
>>>>>>> Please let me know how to  set the krylov-shur  solver   as you
>>>>>>> suggested,
>>>>>>> here are the parameters i pass to  the anasaziPL   for Krylov-Shur
>>>>>>> at the moment:
>>>>>>>
>>>>>>>   const double tol = 1.0e-8;
>>>>>>>   const int maxIters = 500;
>>>>>>>   anasaziPL.set ("Which", "SR");
>>>>>>>   anasaziPL.set ("Block Size",1 );
>>>>>>>   //anasaziPL.set ("Maximum Iterations", maxIters);
>>>>>>>   anasaziPL.set ("Convergence Tolerance", tol);
>>>>>>>   anasaziPL.set ("Full Ortho", true);
>>>>>>>   anasaziPL.set ("Use Locking", true);
>>>>>>>
>>>>>>> Mike.
>>>>>>>
>>>>>>>
>>>>>>> On Thu, Feb 5, 2015 at 5:47 PM, Alicia Klinvex <aklinvex at purdue.edu>
>>>>>>> wrote:
>>>>>>>
>>>>>>>> Hi Mike,
>>>>>>>>
>>>>>>>> If ARPACK is working for you and block Krylov-Schur is not, I
>>>>>>>> suspect that one is using a spectral transformation and the other is not.
>>>>>>>>
>>>>>>>> I don't know much about scipy's eigs, but I assume it is similar to
>>>>>>>> Matlab's eigs (which also uses ARPACK).  When you ask Matlab's eigs to find
>>>>>>>> the smallest eigenvalues of a matrix, it will automatically transform the
>>>>>>>> problem of finding the smallest eigenpairs of A x = \lambda x into the
>>>>>>>> equivalent problem of finding the largest eigenpairs of A^{-1} x =
>>>>>>>> \lambda^{-1}x.  Anasazi's Krylov Schur does not do that unless you
>>>>>>>> explicitly tell it to.  Could that be the problem you're having?  If so, we
>>>>>>>> can discuss how to tell Krylov-Schur that's what you want to do.
>>>>>>>>
>>>>>>>> Best wishes,
>>>>>>>> Alicia Klinvex
>>>>>>>>
>>>>>>>> On Thu, Feb 5, 2015 at 11:21 AM, Mike Atambo <mikeat4999 at gmail.com>
>>>>>>>> wrote:
>>>>>>>>
>>>>>>>>> Hi,
>>>>>>>>> Im unable to get matrices,  ( say a sparse matrix with
>>>>>>>>> 885500 non zeros  out of  about  2822796900 )   to converge
>>>>>>>>> with the block davison or the krylov solver,
>>>>>>>>>
>>>>>>>>> I had a look at the condition number reported by the 'ILUT'
>>>>>>>>> preconditioner and it seems to grow rather quickly for my  problems,  ( 9x9
>>>>>>>>>  with 39 non zeros has  condition number= 10,   and at    25*25 and 100 non
>>>>>>>>> zeros the condition number is at 250).
>>>>>>>>>
>>>>>>>>> Im able to solve all these examples here using scipy.sparse.eigs
>>>>>>>>>  (it uses ARPACK),  so there is probably something that im not doing right.
>>>>>>>>>
>>>>>>>>> The block-davidson solver with 'ILUT' pre-conditioner   work for
>>>>>>>>> the small systems above,   but  beyond  300*300 matrix size,  this is not
>>>>>>>>> longer true.
>>>>>>>>>
>>>>>>>>> At the moment im  following these steps.
>>>>>>>>>
>>>>>>>>> 1.  Create and initialize a matrix,
>>>>>>>>> 2.  Create an anasazi basic eigenproblem,
>>>>>>>>> 3.  Create a  solver (either block davidson or krylov-shur)
>>>>>>>>> 4.   Get solution,
>>>>>>>>>
>>>>>>>>> Id like to find out whether there is a way to tell why the system
>>>>>>>>>  im working on seems
>>>>>>>>> to be  unable to converge.  Any help would be appreciated.
>>>>>>>>>
>>>>>>>>> Mike
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> --
>>>>>>>>> M. O. Atambo
>>>>>>>>> mikeat4999 at gmail.com
>>>>>>>>> matambo at ictp.it
>>>>>>>>> Ext .139
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> _______________________________________________
>>>>>>>>> Trilinos-Users mailing list
>>>>>>>>> Trilinos-Users at software.sandia.gov
>>>>>>>>> https://software.sandia.gov/mailman/listinfo/trilinos-users
>>>>>>>>>
>>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> --
>>>>>>> M. O. Atambo
>>>>>>> mikeat4999 at gmail.com
>>>>>>> matambo at ictp.it
>>>>>>> Ext .139
>>>>>>> Room 209.
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> --
>>>>> M. O. Atambo
>>>>> mikeat4999 at gmail.com
>>>>> matambo at ictp.it
>>>>> Ext .139
>>>>> Room 209.
>>>>>
>>>>>
>>>>
>>>>
>>>> --
>>>> M. O. Atambo
>>>> mikeat4999 at gmail.com
>>>> matambo at ictp.it
>>>> Ext .139
>>>> Room 209.
>>>>
>>>>
>>>
>>>
>>> --
>>> M. O. Atambo
>>> mikeat4999 at gmail.com
>>> matambo at ictp.it
>>> Ext .139
>>> Room 209.
>>>
>>>
>>
>
>
> --
> M. O. Atambo
> mikeat4999 at gmail.com
> matambo at ictp.it
> Ext .139
> Room 209.
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://software.sandia.gov/pipermail/trilinos-users/attachments/20150210/05dc3fe8/attachment.html>

More information about the Trilinos-Users mailing list