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>
- References:
- Re: Mathematica, ARPACK and implicit matrices
- From: dh <dh@metrohm.com>
- Re: Mathematica, ARPACK and implicit matrices