Preconditioners in SciPy - Time & Space Complexity

Time Complexity: Preconditioners

O(n x k)

Understanding Time Complexity

We want to understand how using preconditioners affects the time it takes to solve linear systems with scipy.

Specifically, how does the work grow when the input size changes?

Scenario Under Consideration

Analyze the time complexity of this code snippet using a preconditioner with scipy's conjugate gradient solver.

import numpy as np
from scipy.sparse import diags
from scipy.sparse.linalg import cg, spilu, LinearOperator

n = 1000
A = diags([1, 2, 1], [-1, 0, 1], shape=(n, n))
M2 = spilu(A.tocsc())
M_x = lambda x: M2.solve(x)
M = LinearOperator((n, n), matvec=M_x)
x, info = cg(A, np.ones(n), M=M)
    

This code builds a sparse matrix, creates a preconditioner, and solves a system using conjugate gradient with that preconditioner.

Identify Repeating Operations

Look at what repeats during the solve process.

• Primary operation: Matrix-vector multiplications and preconditioner solves inside each iteration.
• How many times: Number of iterations depends on how well the preconditioner improves convergence.

How Execution Grows With Input

As the matrix size grows, each iteration takes more work, but a good preconditioner reduces the number of iterations.

Input Size (n)	Approx. Operations
10	Few iterations x small matrix-vector work
100	More iterations x larger matrix-vector work
1000	Even more iterations x much larger matrix-vector work

Pattern observation: Without a preconditioner, iterations grow fast; with a good preconditioner, iterations grow slowly, so total work grows closer to linear.

Final Time Complexity

Time Complexity: O(n \times k)

This means the time grows with the size of the matrix times the number of iterations, which the preconditioner helps keep small.

Common Mistake

[X] Wrong: "Preconditioners always make the solve faster regardless of matrix size."

[OK] Correct: Building and applying a preconditioner costs time, and if the matrix is small or the preconditioner is poor, it may not reduce total time.

Interview Connect

Understanding how preconditioners affect time helps you explain solver performance clearly and shows you grasp practical algorithm behavior.

Self-Check

"What if we replaced the preconditioner with a simpler one that is faster to apply but less effective? How would the time complexity change?"