Eigenvalue Power Iteration Fails Randomly

[markrogoyski]

The eigenvalue power iteration method uses a random matrix to start its process. Sometimes this random matrix does not allow it to converge to the correct dominant eigenvalue.

I've added new tests in the develop branch so it happens more frequently when you run the unit tests.

I tried changing the random matrix to all ones using this code:

$b = [];
for ($i = 0; $i < $A->getM(); $i++) {
    $b[] = [1];
}
$b = MatrixFactory::create($b);

It seemed to work. However, it failed on this test case, coming up with 1 instead of 5:

            [
                [
                    [4, -1, -1, -1],
                    [-1, 4, -1, -1],
                    [-1, -1, 4, -1],
                    [-1, -1, -1, 4],
                ],
                [5, 5, 5, 1],
                5,
            ],

@Beakerboy
Do you have any thoughts on how to make this more stable and deterministic?

[markrogoyski]

I tried having the algorithm compute the dominant eigenvalue twice using two different random initial guesses and comparing the result. If they did not match, then to try again. This greatly improved the likelihood that it would get the right answer, but it only took running the unit test cases a couple hundred times for the randomness to strike and it computed the same wrong answer twice with two bad initial guesses.

Is there a way choose an initial guess in a more intelligent way to ensure that the algorithm always converges to the correct dominant eigenvalue?

[Beakerboy]

My research suggested a random matrix “to reduce the likelihood of choosing a Vector orthogonal to an Eigen Vector”. I don't Know a better method. I can see what R does.

[Beakerboy]

I think we can close this one.