How to effectively limit maxiter when using scipy eigs

Python Help
1

I am using scipy.sparse.linalg.eigs to compute the largest eigenpairs of a matrix. My current implementation results in 34 evaluations of the matrix-vector product function (mv()), which is higher than the maxiter I specified. I would like to reduce the number of matrix-vector products or the maximum number of iterations.

Here is my code:

import numpy as np
from scipy.sparse.linalg import LinearOperator, eigs

n = 256
i = 0
rand_vec = np.random.rand(n) 

def mv(v):
    global i 
    i += 1
    print('function call ', i)
    # return np.array([2*v[0], 3*v[1]])
    return np.array(2*v + rand_vec)

A = LinearOperator((n,n), matvec=mv)
print(A)

vals, vecs = eigs(A, k=16, maxiter=25, which='LM', tol=1e-2)

print('vals = ', vals.shape)
print('vecs = ', vecs.shape)
1 Like
2

Maybe it’s not possible to achieve tol=1e-2 in 25 iterations. Does it stop before hitting 25 if that tolerance is increased, or removed?

maxiter int, optional

Maximum number of Arnoldi update iterations allowed Default: n*10

tol float, optional

Relative accuracy for eigenvalues (stopping criterion) The default value of 0 implies machine precision.

https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.linalg.eigs.html#scipy.sparse.linalg.eigs

3

Thanks for your response @JamesParrott. Increasing the tolerance to as high value as tol=10 doesn’t change the number of function calls or iterations.

4

You’re welcome. The tolerance was only 1%, I shouldn’t be surprised.

Are you sure finding eigenvectors for mv(v) = 2*v + rand_vec is well defined? This is an affine mapping but strictly speakin, not a linear map as it doesn’t fix the 0 vector. Normally when solving Ax = lambda * x, x =0 is always a possibility that needs to be avoided.

Otherwise I’d try a simple example with a much smaller n, just to figure out how eigs is supposed to work.

5

The maxiter parameter does cause it to terminate earlier but does not directly correspond to the number of function calls so maxiter=25 does not mean that the function will only be called 25 times.

6

This is actually an example function to recreate the same problem as a more complex function. However, even when I reduce n, I do not seem to have control over the number of iterations, especially using maxiter.

In general, I am looking for a possible way to effectively reduce the number function calls while eigs stills produce the eigenpairs. I thought maxiter could be a way to control this but it doesn’t seem to be very helpful.

7

The obvious answer to me is that the function can be called more than once per iteration, so while there is a linear (or affine) relationship between function calls and maxiter, they aren’t the exact same. Do you have any evidence to contradict this?

1 Like
8

Great point. @Idrishab Have you tried lowering maxiter and seeing if the number of evaluations changes?

9

@MegaIng You are right, the function can be called more than once per iteration and I did not consider this fact when posting the question. However, my goal is reduce the computational cost by reducing the function calls.

@JamesParrott I have tried reducing the maxiter but it doesn’t impact the number of function calls. Maybe there’s an implementation within the Arnoldi method in eigs that overrides the maxiter for certain condition.

I am not expecting the maxiter and number of function calls to be exactly the same, rather, I expect the function calls to be eventually impacted when maxiter is significantly reduced. Unfortunately, this is not happening.

10

This appears to be because the LinearOperator you are providing currently successfully converges after 1 iteration - 34 appears to be a normal amount of function calls it takes for k=16. What does work for me is to vary k.

You might be able to figure out how many function calls happen by looking at the algorithm linked in the docs for eigs - but I doubt that you will be able to modify the number of calls too much.

1 Like
11

Good one, I will look into this.