Eigenvalue problems (eigs, eigsh) in SciPy - Time & Space Complexity

Time Complexity: Eigenvalue problems (eigs, eigsh)

O(k \, n)

Understanding Time Complexity

When solving eigenvalue problems with scipy's eigs or eigsh, we want to know how the time needed grows as the matrix size grows.

We ask: How does the computation time change when the matrix gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

# Create a large sparse matrix
n = 1000
A = np.diag(np.arange(n))

# Compute 6 largest eigenvalues
vals, vecs = eigs(A, k=6)
    

This code finds 6 eigenvalues and eigenvectors of a large matrix using an iterative method.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix-vector multiplications inside the iterative solver.
• How many times: The solver repeats these multiplications many times until convergence, usually proportional to the number of eigenvalues requested and matrix size.

How Execution Grows With Input

As the matrix size grows, the number of operations grows roughly with the size times the number of iterations needed.

Input Size (n)	Approx. Operations
10	Few hundred matrix-vector multiplications
100	Thousands of multiplications
1000	Hundreds of thousands of multiplications

Pattern observation: The time grows roughly linearly with matrix size times iterations, which depends on requested eigenvalues.

Final Time Complexity

Time Complexity: O(k \, n)

This means the time grows roughly with the number of eigenvalues requested times the matrix size.

Common Mistake

[X] Wrong: "The eigs function always runs in linear time with matrix size because it uses sparse methods."

[OK] Correct: Even with sparse methods, the number of iterations and matrix-vector multiplications depends on matrix size and requested eigenvalues, so time grows faster than linear.

Interview Connect

Understanding how eigenvalue solvers scale helps you explain performance in real data science tasks, showing you know how algorithms behave on big data.

Self-Check

"What if we increase the number of eigenvalues requested (k) significantly? How would the time complexity change?"