Solving linear systems (solve) in SciPy - Time & Space Complexity

Time Complexity: Solving linear systems (solve)

O(n^3)

Understanding Time Complexity

When we solve linear systems using scipy, we want to know how the time it takes changes as the system size grows.

We ask: How does solving a bigger system affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np
from scipy.linalg import solve

n = 10  # example size
A = np.random.rand(n, n)  # square matrix of size n
b = np.random.rand(n)     # vector of size n
x = solve(A, b)           # solve Ax = b

This code solves a system of linear equations with a square matrix A and vector b.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matrix factorization and substitution steps inside solve.
• How many times: Operations involve nested loops over matrix rows and columns, roughly n times for each dimension.

How Execution Grows With Input

As the matrix size n grows, the number of calculations grows much faster.

Input Size (n)	Approx. Operations
10	About 1,000 operations
100	About 1,000,000 operations
1000	About 1,000,000,000 operations

Pattern observation: The work grows roughly by the cube of n, so doubling n makes the work about eight times bigger.

Final Time Complexity

Time Complexity: O(n^3)

This means if you double the size of the system, the time to solve it grows about eight times.

Common Mistake

[X] Wrong: "Solving linear systems with solve grows linearly with n because it just loops once over the matrix."

[OK] Correct: The solve function does more than one loop; it performs matrix factorization which involves nested loops over rows and columns, making the work grow much faster than just n.

Interview Connect

Understanding how solving linear systems scales helps you explain performance in data science tasks like regression or simulations, showing you know how algorithms behave with bigger data.

Self-Check

"What if the matrix A is sparse instead of dense? How would the time complexity change?"

Practice

1. What does the scipy.linalg.solve function do in solving linear systems?

easy

A. It finds the exact solution vector for a system of linear equations.

B. It approximates the solution using random guesses.

C. It only checks if the system has any solution without solving.

D. It multiplies two matrices together.

Solution

1. Step 1: Understand the purpose of scipy.linalg.solve

   This function is designed to solve linear systems of the form Ax = b, where A is a matrix and b is a vector.

2. Step 2: Identify the output of the function

   The function returns the vector x that exactly satisfies the equation Ax = b.

3. Final Answer:

   It finds the exact solution vector for a system of linear equations. -> Option A

4. Quick Check:

   Function purpose = exact solution vector [OK]

Hint: Remember: solve() returns exact solutions, not guesses. [OK]

Common Mistakes:

• Thinking solve() approximates solutions
• Confusing solve() with matrix multiplication
• Assuming solve() only checks for solution existence

2. Which of the following is the correct way to import the solve function from scipy.linalg?

easy

A. from scipy.linalg import solve

B. import solve from scipy.linalg

C. from scipy import solve.linalg

D. import scipy.solve.linalg

Solution

1. Step 1: Recall Python import syntax for functions

   To import a specific function from a module, use from module import function.

2. Step 2: Match the correct module and function

   The function solve is inside the scipy.linalg module, so the correct import is from scipy.linalg import solve.

3. Final Answer:

   from scipy.linalg import solve -> Option A

4. Quick Check:

   Correct import syntax = from scipy.linalg import solve [OK]

Hint: Use 'from module import function' for specific imports. [OK]

Common Mistakes:

• Using 'import solve from ...' which is invalid syntax
• Trying to import submodules as functions
• Using dot notation incorrectly in import statements

3. What is the output of this code?

import numpy as np
from scipy.linalg import solve
A = np.array([[2, 1], [1, 3]])
b = np.array([10, 15])
x = solve(A, b)
print(x)

medium

A. [4. 3.]

B. [3. 4.]

C. [2. 5.]

D. [5. 2.]

Solution

1. Step 1: Set up the system of equations

   The matrix A and vector b represent the system:
   2x + y = 10
   x + 3y = 15

2. Step 2: Solve the system manually

   Solving manually:
   Multiply first equation by 3: 6x + 3y = 30
   Subtract second equation: 5x = 15 -> x = 3
   y = 10 - 2*3 = 4
   Thus, x = [3. 4.], which matches the output of solve(A, b).

3. Final Answer:

   [3. 4.] -> Option B

4. Quick Check:

   solve(A,b) output = [3. 4.] [OK]

Hint: Trust solve() output for exact numeric solutions. [OK]

Common Mistakes:

• Mixing up order of solution vector
• Trying to solve manually without decimals
• Assuming integer solutions only

4. What is wrong with this code snippet?

import numpy as np
from scipy.linalg import solve
A = np.array([[1, 2], [2, 4]])
b = np.array([5, 10])
x = solve(A, b)
print(x)

medium

A. The code will run and print the solution without issues.

B. Vector b has wrong shape and causes a syntax error.

C. The import statement is incorrect.

D. Matrix A is singular (not invertible), so solve() will raise an error.

Solution

1. Step 1: Check matrix A properties

   Matrix A = [[1, 2], [2, 4]] has rows that are multiples (second row = 2 * first row), so it is singular (determinant = 0).

2. Step 2: Understand solve() behavior with singular matrices

   Since A is singular, it cannot be inverted, so solve() will raise a LinAlgError indicating the matrix is singular.

3. Final Answer:

   Matrix A is singular (not invertible), so solve() will raise an error. -> Option D

4. Quick Check:

   Singular matrix causes error in solve() [OK]

Hint: Check if matrix rows are multiples before solving. [OK]

Common Mistakes:

• Ignoring singular matrix errors
• Assuming solve() works for all matrices
• Confusing vector shape errors with matrix singularity

5. You have a system of 3 equations with 3 unknowns:

A = [[1, 2, 3], [0, 1, 4], [5, 6, 0]]
b = [11, 7, 28]

Using scipy.linalg.solve, what is the solution vector x?

hard

A. [1. 2. 3.]

B. [0. 1. 2.]

C. [2. 3. 1.]

D. [3. 1. 2.]

Solution

1. Step 1: Write the system of equations

   The system is:
   1x + 2y + 3z = 11
   0x + 1y + 4z = 7
   5x + 6y + 0z = 28

2. Step 2: Solve the system using substitution

   From second equation: y = 7 - 4z
   Substitute into first: x + 2(7 - 4z) + 3z = 11 -> x + 14 - 8z + 3z = 11 -> x - 5z = -3 -> x = -3 + 5z
   Substitute into third: 5(-3 + 5z) + 6(7 - 4z) = 28 -> -15 + 25z + 42 - 24z = 28 -> z + 27 = 28 -> z = 1
   y = 7 - 4*1 = 3
   x = -3 + 5*1 = 2
   Thus, x = [2. 3. 1.]

3. Final Answer:

   [2. 3. 1.] -> Option C

4. Quick Check:

   solve(A,b) = [2. 3. 1.] [OK]

Hint: Use solve() to avoid manual errors in 3x3 systems. [OK]

Common Mistakes:

• Manual calculation errors with substitution
• Mixing variable order in solution vector
• Ignoring code output for complex systems