MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Re: Mathematica, ARPACK and implicit matrices

  • To: mathgroup at smc.vnet.net
  • Subject: [mg96614] Re: [mg96592] Re: Mathematica, ARPACK and implicit matrices
  • From: dh <dh at metrohm.com>
  • Date: Tue, 17 Feb 2009 06:26:31 -0500 (EST)
  • References: <20090214221813.9l7ub5g1cs8c4g44@www.icfo.es> <4997A3D9.3060801@gmail.com> <gnbkea$3g2$1@smc.vnet.net> <200902162141.QAA16086@smc.vnet.net> <op.upgzwby5tgfoz2@bobbys-imac.local>

Well, for some people one need to spell out all the details. If the 
vector gets bigger no harm is done, one simply has to normalize it.
Daniel

DrMajorBob wrote:
> No... Unless the eigenvalue is +/-1, the "Power method" you describe 
> will diverge (if the eigenvalue has absolute value > 1) or converge to 0 
> (if the absolute value < 1). If the eigenvalue is -1, your method (and 
> mine below) will cycle between +/- the sought-for eigenvector. So... 
> simple convergence won't occur unless the eigenvalue is 1.
> 
> Here's a method similar to yours:
> 
> m = RandomReal[{1}, {4, 4}]
> 
> {{0.79066, 0.509111, 0.318938, 0.652391}, {0.828933, 0.790204,
>   0.714706, 0.132932}, {0.947251, 0.490976, 0.669439,
>   0.919992}, {0.03295, 0.0828506, 0.868529, 0.950574}}
> 
> normalize = #/Norm@# &;
> Through[{Length, Last} at FixedPointList[normalize[m.#] &, {1, 0, 0, 0}]]
> 
> {37, {0.445853, 0.527469, 0.602979, 0.399259}}
> 
> eigen = Eigenvectors@m
> 
> {{-0.445853, -0.527469, -0.602979, -0.399259}, {-0.164867, -0.78803,
>   0.013613, 0.592994}, {-0.487356 - 0.0761477 I,
>   0.667546 + 0. I, -0.244788 + 0.357903 I,
>   0.2391 - 0.256679 I}, {-0.487356 + 0.0761477 I,
>   0.667546 + 0. I, -0.244788 - 0.357903 I, 0.2391 + 0.256679 I}}
> 
> We got convergence to (a scalar times) the first eigenvector, as you see.
> 
> The same occurs even if we start with the second eigenvector (due to 
> numerical inaccuracies):
> 
> second = eigen[[2]]
> Through[{Length, Last} at FixedPointList[normalize[m.#] &, second]]
> 
> {-0.164867, -0.78803, 0.013613, 0.592994}
> 
> {72, {-0.445853, -0.527469, -0.602979, -0.399259}}
> 
> The same would probably occur if we started with a non-zero vector 
> perpendicular to the desired eigenvector, for the same numerical 
> inaccuracy reasons.
> 
> If the matrix is exact, however, starting with the second eigenvector 
> we'd converge to the second eigenvector... IN THEORY.
> 
> Actually, an exact matrix might lead to HUGE complexity in the 
> intermediate results and precision errors in the test for convergence.
> 
> Bobby
> 
> On Mon, 16 Feb 2009 15:41:53 -0600, dh <dh at metrohm.com> wrote:
> 
>>
>>
>> Hi Fernando,
>>
>> if the searched for eigenvalue is the largest in magnitude, your problem
>>
>> is easily solved by the "Power method".
>>
>> Take an arbitrary vector, keep on multiplying it by your matrix until it
>>
>> cnoverges. This gives the eigenvector (provided you did not pick a start
>>
>> vector perpendicular to the eigenvector).
>>
>>
>>
>> hope this helps, Daniel
>>
>>
>>
>> Fernando Cucchietti wrote:
>>
>>> I am trying to find the largest eigenvalue and associated eigenvector
>>
>>> of a very large matrix, mildly sparse but without a simple structure
>>
>>> -- that is, zero elements are arranged in a seemingly random way.
>>
>>>
>>
>>> Mathematica uses ARPACK routines for this task. However, it appears
>>
>>> that it wants to construct the matrix explicitly before starting. This
>>
>>> is strange when compared to how ARPACK works, and in fact it is the
>>
>>> one thing I was trying to avoid doing: Writing down the matrix takes
>>
>>> too much memory and time, even if it is sparse.
>>
>>>
>>
>>> ARPACK is designed to require not the matrix, but just a function that
>>
>>> gives the result of multiplying the matrix with an arbitrary vector. I
>>
>>> call this an implicit definition of the matrix, hence the subject of
>>
>>> the email. This would work very well with me since I have a compact
>>
>>> expression of the matrix in the form of a function that returns the
>>
>>> product with a vector, and I would not need to define the array
>>
>>> explicitly.
>>
>>>
>>
>>> I have been looking but I cannot find an option or a way to make
>>
>>> Mathematica give me the eigenvalues without writing the matrix
>>
>>> explicitly, any suggestions?
>>
>>>
>>
>>> Fernando Cucchietti
>>
>>>
>>
>>
>>
> 
> 
> 


-- 

Daniel Huber
Metrohm Ltd.
Oberdorfstr. 68
CH-9100 Herisau
Tel. +41 71 353 8585, Fax +41 71 353 8907
E-Mail:<mailto:dh at metrohm.com>
Internet:<http://www.metrohm.com>



  • Prev by Date: Re: Re: Mathematica, ARPACK and implicit matrices
  • Next by Date: Re: Select All Lists Where Any Element is a Given Value
  • Previous by thread: Re: Re: Mathematica, ARPACK and implicit matrices
  • Next by thread: Re: Mathematica, ARPACK and implicit matrices