Re: Re: Mathematica, ARPACK and implicit matrices

*To*: mathgroup at smc.vnet.net*Subject*: [mg96606] Re: [mg96592] Re: Mathematica, ARPACK and implicit matrices*From*: DrMajorBob <btreat1 at austin.rr.com>*Date*: Tue, 17 Feb 2009 06:25:03 -0500 (EST)*References*: <20090214221813.9l7ub5g1cs8c4g44@www.icfo.es>*Reply-to*: drmajorbob at longhorns.com

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 > >> > > > -- DrMajorBob at longhorns.com