Sparse linear algebra solvers in SciPy - Step-by-Step Execution

Concept Flow - Sparse linear algebra solvers

Start with sparse matrix A and vector b

↓

Choose solver method (e.g., cg, bicg, gmres)

↓

Initialize solver variables

↓

Iterative solve loop

↓

Compute residual

↓

Converged?

↓

Return solution

↓

End

The solver starts with a sparse matrix and vector, chooses an iterative method, then loops updating the solution until it converges or stops.

Execution Sample

SciPy

from scipy.sparse.linalg import cg
from scipy.sparse import csr_matrix
import numpy as np
A = csr_matrix(np.array([[4,1],[1,3]]))
b = np.array([1,2])
x, info = cg(A, b)
print(x)

This code solves the linear system Ax = b using the Conjugate Gradient method.

Execution Table

Step	Action	Residual norm	Solution x	Converged?
1	Initialize x0 = [0,0]	||r0|| = 2.236	[0.0, 0.0]	No
2	Iteration 1 update	||r1|| = 0.447	[0.0909, 0.5455]	No
3	Iteration 2 update	||r2|| = 0.0	[0.0909, 0.6364]	Yes
4	Return solution	-	[0.0909, 0.6364]	Yes

💡 Converged at iteration 2 because residual norm reached zero.

Variable Tracker

Variable	Start	After 1	After 2	Final
x	[0.0, 0.0]	[0.0909, 0.5455]	[0.0909, 0.6364]	[0.0909, 0.6364]
Residual norm	2.236	0.447	0.0	0.0

Key Moments - 3 Insights

Why does the solution x start at [0,0]?

The solver initializes x with zeros as a starting guess before iterations, as shown in step 1 of the execution table.

What does the residual norm tell us?

It measures how close Ax is to b; when it reaches zero (step 3), the solution has converged.

Why does the solver stop after iteration 2?

Because the residual norm became zero, indicating the exact solution was found, so no more iterations are needed.

Visual Quiz - 3 Questions

Look at the execution table, what is the residual norm after iteration 1?

A 0.447

B 2.236

C 0.0

D 1.0

💡 Hint

Check the 'Residual norm' column at Step 2 (Iteration 1 update).

At which step does the solver declare convergence?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Converged?' column where it first says 'Yes'.

If the initial guess x was not zero, how would the variable tracker change?

A Residual norm would start at zero.

B The start value of x would be different, but later values depend on iterations.

C Solution x would not update.

D The solver would never converge.

💡 Hint

Variable tracker shows 'Start' values; changing initial guess affects only the start.

Concept Snapshot

Sparse linear algebra solvers use iterative methods to solve Ax=b when A is sparse.
Common methods: Conjugate Gradient (cg), BiCGSTAB, GMRES.
Start with initial guess x0 (often zeros).
Iterate updating x and residual until convergence.
Residual norm measures solution accuracy.
Stop when residual is small enough or max iterations reached.

Full Transcript

Sparse linear algebra solvers help solve equations where the matrix A has mostly zeros. We start with a guess for the solution x, usually zeros. Then, the solver updates x step by step, checking how close Ax is to b by measuring the residual norm. When the residual norm is very small or zero, the solver stops and returns the solution. This process uses iterative methods like Conjugate Gradient. The example code solves a small system and shows how x and residual change each step until convergence.