Sparse iterative solvers (gmres, cg) in SciPy - Practice Problems & Coding Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of CG solver on a simple sparse system

What is the output of the following code snippet that uses the Conjugate Gradient (CG) solver from scipy.sparse.linalg to solve a sparse linear system?

SciPy

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

# Create a sparse diagonal matrix
n = 5
k = [-1*np.ones(n-1), 2*np.ones(n), -1*np.ones(n-1)]
offsets = [-1, 0, 1]
A = diags(k, offsets)

b = np.array([1, 2, 3, 4, 5])

x, info = cg(A, b)
print(x)

A [5.83 10.67 13.5 13.33 9.17]

B [2. 3. 4. 5. 6.]

C [0.75 1.5 2. 2.5 3. ]

D [1. 2. 3. 4. 5.]

💡 Hint

Think about how the CG solver solves Ax = b for a tridiagonal matrix with 2 on the diagonal and -1 on the off-diagonals.

The matrix A is a tridiagonal matrix representing a simple finite difference operator. The CG solver finds the solution x such that Ax = b. The output vector x is approximately [0.75, 1.5, 2.0, 2.5, 3.0].

❓ Predict Output

intermediate

GMRES solver output for a sparse system

What is the output of the following code that uses GMRES to solve a sparse linear system?

SciPy

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

n = 4
k = [np.ones(n), 2*np.ones(n), np.ones(n)]
offsets = [-1, 0, 1]
A = diags(k, offsets)

b = np.array([1, 2, 3, 4])

x, info = gmres(A, b)
print(x)

A [0.25 0.5 0.75 1. ]

B [0. 1. 0. 2. ]

C [1. 2. 3. 4.]

D [0.5 1. 1.5 2. ]

💡 Hint

GMRES solves Ax = b for a matrix with 2 on the diagonal and 1 on the off-diagonals.

The matrix A has 2 on the diagonal and 1 on the off-diagonals. The GMRES solver finds x such that Ax = b. The solution vector x is approximately [0.25, 0.5, 0.75, 1.0].

❓ data_output

advanced

Number of iterations for CG solver convergence

Given the following code that solves a sparse system using CG with a tolerance of 1e-8, what is the number of iterations taken for convergence?

SciPy

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

n = 10
k = [-1*np.ones(n-1), 2*np.ones(n), -1*np.ones(n-1)]
offsets = [-1, 0, 1]
A = diags(k, offsets)

b = np.arange(1, n+1)

x, info = cg(A, b, tol=1e-8, maxiter=1000)
print(info)

A 0

B 10

C 1000

D 5

💡 Hint

The info output from cg returns 0 if convergence is reached successfully.

The CG solver converges successfully and info returns 0 indicating successful convergence within the allowed iterations.

🔧 Debug

advanced

Identify the error in GMRES solver usage

What error will the following code raise when trying to solve a sparse system with GMRES?

SciPy

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

n = 3
k = [np.ones(n), 2*np.ones(n), np.ones(n)]
offsets = [-1, 0, 1]
A = diags(k, offsets)

b = np.array([1, 2])

x, info = gmres(A, b)
print(x)

A IndexError: index out of range

B ValueError: dimension mismatch between A and b

C TypeError: unsupported operand type(s) for +: 'int' and 'str'

D No error, prints solution vector

💡 Hint

Check the size of matrix A and vector b.

The matrix A is 3x3 but vector b has length 2, causing a dimension mismatch error when calling gmres.

🚀 Application

expert

Choosing solver based on matrix properties

You have a large sparse symmetric positive definite matrix A and vector b. Which solver is the best choice to efficiently solve Ax = b?

A Use GMRES solver because it works for any matrix

B Use Jacobi iterative method for faster convergence

C Use direct solver like LU decomposition for sparse matrices

D Use CG solver because it is optimized for symmetric positive definite matrices

💡 Hint

Consider matrix properties and solver strengths.

CG solver is designed for symmetric positive definite matrices and is more efficient than GMRES or Jacobi for such cases. Direct solvers are often slower for large sparse matrices.

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