Sparse iterative solvers (gmres, cg) in SciPy - Mini Project: Build & Apply

Solving Sparse Linear Systems with GMRES and CG

📖 Scenario: You work as a data scientist helping engineers solve large systems of equations that come from real-world problems like network flows or physical simulations. These systems are often very large but have mostly zero values, called sparse systems.To solve these efficiently, you will use special methods called iterative solvers: GMRES and CG. These methods find approximate solutions quickly without using too much memory.

🎯 Goal: You will create a sparse matrix and a vector, then use the GMRES and CG solvers from scipy.sparse.linalg to find solutions. Finally, you will print the results to see how well the solvers worked.

📋 What You'll Learn

Create a sparse matrix using scipy.sparse

Create a vector with exact values

Set a tolerance level for the solver

Use gmres and cg solvers from scipy.sparse.linalg

Print the solution vectors

💡 Why This Matters

🌍 Real World

Sparse iterative solvers are used in engineering, physics, and computer science to solve large systems efficiently, such as in simulations, network analysis, and optimization.

💼 Career

Knowing how to use sparse solvers helps data scientists and engineers handle big data problems and scientific computations where memory and speed are critical.

1

Create a sparse matrix and vector

Create a sparse matrix called A using scipy.sparse.csr_matrix with these exact values: [[4, 1, 0], [1, 3, 1], [0, 1, 2]]. Also create a vector called b as a NumPy array with values [1, 2, 3].

SciPy

# Create sparse matrix A and vector b
# Your code here

Hint

Use csr_matrix to create the sparse matrix A with the exact 3x3 values. Use np.array to create vector b.

2

Set the tolerance for the solvers

Create a variable called tol and set it to 1e-5 to control the solver accuracy.

SciPy

import numpy as np
from scipy.sparse import csr_matrix

A = csr_matrix([[4, 1, 0], [1, 3, 1], [0, 1, 2]])
b = np.array([1, 2, 3])
# Set tolerance tol to 1e-5
# Your code here

Hint

Simply assign 1e-5 to a variable named tol.

3

Solve the system using GMRES and CG

Import gmres and cg from scipy.sparse.linalg. Use gmres to solve Ax = b with tolerance tol and store the solution in x_gmres. Use cg to solve Ax = b with tolerance tol and store the solution in x_cg. Ignore the second returned value from both solvers.

SciPy

import numpy as np
from scipy.sparse import csr_matrix

A = csr_matrix([[4, 1, 0], [1, 3, 1], [0, 1, 2]])
b = np.array([1, 2, 3])
tol = 1e-5
# Import gmres and cg and solve Ax=b
# Your code here

Hint

Use gmres(A, b, tol=tol) and cg(A, b, tol=tol). Assign the first returned value to x_gmres and x_cg respectively, and ignore the second value with _.

4

Print the solutions

Print the solution vectors x_gmres and x_cg each on a separate line.

SciPy

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.linalg import gmres, cg

A = csr_matrix([[4, 1, 0], [1, 3, 1], [0, 1, 2]])
b = np.array([1, 2, 3])
tol = 1e-5

x_gmres, _ = gmres(A, b, tol=tol)
x_cg, _ = cg(A, b, tol=tol)
# Print x_gmres and x_cg
# Your code here

Hint

Use print(x_gmres) and print(x_cg) to show the solution vectors.

Practice

1. Which of the following statements about scipy.sparse.linalg.cg is true?

easy

A. cg is slower than gmres for all matrices.

B. cg can solve any linear system regardless of matrix properties.

C. cg uses dense matrix methods internally.

D. cg requires the matrix to be symmetric and positive definite.

Solution

1. Step 1: Understand the requirements of cg

   The conjugate gradient method (cg) is designed for symmetric positive definite matrices only.

2. Step 2: Compare with other options

   cg cannot solve any matrix (B is wrong), it is often faster than gmres for suitable matrices (A is wrong), and it uses sparse methods, not dense (D is wrong).

3. Final Answer:

   cg requires the matrix to be symmetric and positive definite. -> Option D

4. Quick Check:

   cg needs symmetric positive definite matrix [OK]

Hint: Remember: CG needs symmetric positive definite matrices [OK]

Common Mistakes:

• Thinking CG works for any matrix
• Confusing CG with GMRES
• Assuming CG uses dense matrix methods

2. Which is the correct way to import the GMRES solver from SciPy?

easy

A. import scipy.linalg.gmres

B. from scipy.sparse.linalg import gmres

C. from scipy.linalg import gmres

D. import gmres from scipy.sparse

Solution

1. Step 1: Recall the module location of GMRES

   The GMRES solver is in scipy.sparse.linalg, so it must be imported from there.

2. Step 2: Check the import syntax

   Correct Python import syntax for a function is from module import function. from scipy.sparse.linalg import gmres matches this and the correct module.

3. Final Answer:

   from scipy.sparse.linalg import gmres -> Option B

4. Quick Check:

   Correct import syntax and module [OK]

Hint: Import gmres from scipy.sparse.linalg using 'from ... import' [OK]

Common Mistakes:

• Importing from scipy.linalg instead of sparse.linalg
• Using incorrect import syntax
• Trying to import gmres directly from scipy.sparse

3. What will be the output of the following code snippet?

import numpy as np
from scipy.sparse.linalg import cg
from scipy.sparse import diags

A = diags([1, 2, 1], [-1, 0, 1]).toarray()
b = np.array([4, 6, 4])
x, info = cg(A, b)
print(np.round(x, 2))

medium

A. [1. 2. 1.]

B. [2. 1. 2.]

C. [0. 0. 0.]

D. Error due to matrix not positive definite

Solution

1. Step 1: Analyze the matrix and vector

   The matrix A is tridiagonal with diagonals [1,2,1], which is symmetric positive definite. Vector b is [4,6,4].

2. Step 2: Solve using conjugate gradient

   Using cg, the solution x satisfies Ax = b. The solution is approximately [1, 2, 1].

3. Final Answer:

   [1. 2. 1.] -> Option A

4. Quick Check:

   cg solves Ax=b with symmetric positive definite A [OK]

Hint: Check matrix symmetry and positive definiteness before cg [OK]

Common Mistakes:

• Assuming cg fails on this matrix
• Confusing the solution vector with b
• Not rounding output before comparing

4. Identify the error in this code using cg solver:

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

A = np.array([[0, 1], [1, 0]])
b = np.array([1, 2])
x, info = cg(A, b)
print(x)

medium

A. Matrix A is not symmetric positive definite, so cg will fail.

B. Vector b has wrong shape.

C. cg function is not imported correctly.

D. No error; code runs fine.

Solution

1. Step 1: Check matrix properties

   Matrix A = [[0,1],[1,0]] is symmetric but not positive definite (its eigenvalues are 1 and -1).

2. Step 2: Understand cg requirements

   The conjugate gradient method requires A to be symmetric positive definite. Since A is not, cg will fail or not converge properly.

3. Final Answer:

   Matrix A is not symmetric positive definite, so cg will fail. -> Option A

4. Quick Check:

   cg needs symmetric positive definite matrix [OK]

Hint: Check matrix eigenvalues before using cg [OK]

Common Mistakes:

• Ignoring matrix definiteness
• Assuming cg works for any symmetric matrix
• Thinking vector shape causes error

5. You have a large sparse matrix that is not symmetric positive definite. Which solver should you use to solve Ax = b efficiently?

hard

A. Use cg because it is always faster.

B. Convert matrix to dense and use direct solver.

C. Use gmres because it works for general matrices.

D. Use cg after transposing the matrix.

Solution

1. Step 1: Identify matrix properties

   The matrix is large, sparse, and not symmetric positive definite, so cg is not suitable.

2. Step 2: Choose appropriate solver

   gmres can handle general matrices efficiently without requiring symmetry or positive definiteness.

3. Step 3: Avoid dense conversion

   Converting to dense wastes memory and time, so it is not efficient.

4. Final Answer:

   Use gmres because it works for general matrices. -> Option C

5. Quick Check:

   gmres handles general sparse matrices [OK]

Hint: Use gmres for non-symmetric or indefinite sparse matrices [OK]

Common Mistakes:

• Trying to use cg on non-symmetric matrices
• Converting sparse to dense unnecessarily
• Thinking transposing fixes definiteness