TASK 1. Calculate the number of arithmetic operations that are required to solve aβ¦
- User
TASK 1. Calculate the number of arithmetic operations that are required to solve a tridiagonal system ππ = π of size π using the Thomas algorithm. Based on this result, determine the asymptotic complexity of the Thomas algorithm, and compare it to the asymptotic complexity of the standard Gaussian elimination. TASK 2. Rewrite the Thomas algorithm in terms of the arrays π΄,π΅, and πΆ introduced to store the matrix π efficiently. TASK 3. Implement the Thomas algorithm from TASK 2 as a Python function. The input parameters to the function should be the coefficient matrix π (stored as three arrays π΄,π΅, and πΆ) and the right-hand side vector π. The output should be the solution vector π. The coefficient matrix and the right-hand side should be defined in the main script and passed to the function that solves the system. TASK 4. Test your code by solving the linear system of size π = 10 with the values π΄ = 2, and π΅ = πΆ = β1. Set the right-hand side to π = π. To verify the correctness of your code, compare the solution vector obtained from the Thomas algorithm to that obtained by applying the direct solver numpy.linalg.solve(). For the latter, the coefficient matrix should be assembled. TASK 5. Solve five linear systems ππ = π with π΄ = 2, π΅ = πΆ = β1 and π = π varying the problem size π between 106 and 108 . Record the execution times in seconds for each case. To accomplish this task, explore the Python function timer() from the package timeit (refer to the code for matrix multiplication covered in lectures). Plot a graph where the obtained execution times are represented as the function of the problem size π. What are your conclusions about the cost of the Thomas algorithm?
- Assistant
TASK 1: To calculate the number of arithmetic operations needed by the Thomas algorithm to solve a tridiagonal system ππ₯ = π, consider the following steps in the algorithm.
Forward elimination (for n-1 rows):
- For every row i from 2 to n, modify the 3 main components (A[i], B[i], C[i], and f[i]):
- 2 operations for modifying C[i]
- 3 operations to modify f[i]
- 1 operation to modify B[i]
- Total for each row: 2 + 3 + 1 = 6
- Total: 6 * (n - 1)
Back substitution (for n elements):
- For backward calculation of the solution in vector x:
- 1 operation for the last element
- For every element i from n-1 down to 1:
- 2 operations for i-th element (one subtraction, one division)
- Total for back substitution: 1 + 2 * (n - 1)
Adding the two parts together:
-
Forward elimination: 6 * (n - 1)
-
Back substitution: 1 + 2 * (n - 1)
-
Total operations = 6 * (n - 1) + 1 + 2 * (n - 1) = 8 * (n - 1) + 1
Therefore, the number of arithmetic operations is linear with respect to n. The exact number can vary depending on the implementation, but the complexity will be O(n).
Comparing this with the standard Gaussian elimination, which has a complexity of O(n^3), the Thomas algorithm is significantly more efficient for tridiagonal systems, with a complexity of O(n).
TASK 2: Given the tridiagonal matrix π stored in three arrays π΄, π΅, and πΆ:
- A - sub-diagonal elements (A[1] to A[n-1])
- B - main diagonal elements (B[0] to B[n-1])
- C - super-diagonal elements (C[0] to C[n-2])
- f - right-hand side vector
Here is a pseudocode version of the Thomas algorithm:
For i from 1 to n - 1 do: w = A[i] / B[i - 1] B[i] = B[i] - w * C[i - 1] f[i] = f[i] - w * f[i - 1] End for x[n - 1] = f[n - 1] / B[n - 1] For i from n - 2 down to 0 do: x[i] = (f[i] - C[i] * x[i + 1]) / B[i] End for Return xTASK 3: Here's a Python function that implements the Thomas algorithm:
def thomas_algorithm(A, B, C, f): n = len(f) x = [0] * n # Forward elimination for i in range(1, n): w = A[i] / B[i-1] B[i] -= w * C[i-1] f[i] -= w * f[i-1] # Back substitution x[-1] = f[-1] / B[-1] for i in range(n-2, -1, -1): x[i] = (f[i] - C[i] * x[i+1]) / B[i] return x # Main script A = [2] + [2] * (n - 1) # A[0] is unused B = [-1] * (n - 1) + [-1] C = [2] * n f = [1] * n x = thomas_algorithm(A, B, C, f)TASK 4: Testing the function with a specified system:
import numpy as np n = 10 A = [0] + [2] * (n - 1) # A starts at index 1 B = [-1] * n C = [-1] * (n - 1) + [0] f = [1] * n # Solve with Thomas algorithm x_thomas = thomas_algorithm(A, B, C, f) # Assemble the full matrix to use with numpy.linalg.solve full_matrix = np.diag(B) + np.diag(C[:-1], 1) + np.diag(A[1:], -1) # Solve with numpy.linalg.solve x_direct = np.linalg.solve(full_matrix, f) # Verify the correctness print('Solution from Thomas algorithm:', x_thomas) print('Solution from direct solver:', x_direct) print('Difference:', np.abs(np.array(x_thomas) - x_direct))TASK 5: Please note that solving linear systems with n on the order of 10^6 to 10^8 might not be feasible on a standard computer due to memory constraints. However, for the sake of the task, you can use the following template to perform the experiment and plot the graph (not tested due to the high n values):
import timeit import matplotlib.pyplot as plt sizes = [10**6, 10**7, 10**8] times = [] for n in sizes: A = [0] + [2] * (n - 1) B = [-1] * n C = [-1] * (n - 1) + [0] f = [1] * n start_time = timeit.default_timer() x = thomas_algorithm(A, B, C, f) times.append(timeit.default_timer() - start_time) plt.plot(sizes, times) plt.xlabel('Problem size n') plt.ylabel('Execution time (s)') plt.title('Thomas Algorithm Execution Time') plt.show()The expected conclusion is that the Thomas algorithm scales linearly with problem size (O(n)), indicating efficient scalability for large tridiagonal systems.
- For every row i from 2 to n, modify the 3 main components (A[i], B[i], C[i], and f[i]):
- User
how to print the matrix x in task 3
- Assistant
To print the solution vector
xobtained from the Thomas algorithm in Task 3, you can simply add a print statement after the line where thethomas_algorithmfunction is called. Here's how you can modify the main script:# Main script n = 10 # Define the size of the system A = [0] + [2] * (n - 1) # A starts at index 1, placeholder for 0 since we don't use A[0] B = [-1 for i in range(n)] # Main diagonal elements C = [-1 for i in range(n - 1)] # Super-diagonal elements, placeholder for 0 at the end f = [1 for i in range(n)] # Right-hand side vector # Solve with the Thomas algorithm x = thomas_algorithm(A, B, C, f) # Print the solution vector x print("Solution vector x:") print(x)This script assumes you have already defined the
thomas_algorithmfunction from Task 2 that receives the arraysA,B,C, andfas inputs and returns the solution vectorx.The
printstatement will output the solution vectorxto the console. If you're running a Python script, you will see the result in your terminal or command prompt. If you're using an interactive environment like Jupyter Notebook, the result will be displayed in the output cell. - User
import numpy as np import numpy.linalg as la
The Thomas algorithm function which introduces the matrices: A,B,C,f as input parameters
def thomas_Alg(A,B,C,f):
# Process of forward elimination # Required number of iterationsn = len(f)
#Forward elimination iterations for i in range(1,n): A[i]=A[i]-(B[i-1]/A[i-1])*C[i-1] f[i]=f[i]-(B[i-1]/A[i-1])*f[i-1]
# Back substitution # Create an x array of zeros (initialisation)x=[0]* n
#Back substitution interationsx[n-1]=f[n-1]/A[n-1] for i in range(n-2,-1,-1): x[i] = 1/A[i] * (f[i] - ([i] * x[i+1]))
#Output of the solution vector x return x
from timeit import default_timer as timer import matplotlib.pyplot as plt
n=10 A= [2]n B= [-1](n-1) C= [-1]*(n-1) f= [1]*n
print(thomas_Alg(A, B, C, f))
A= [2]n B= [-1](n-1) C= [-1]*(n-1) f= [1]*n
T=np.diag(A) + np.diag(B,-1) + np.diag(C,1)
print(la.solve(T,f))
identifty the error - Assistant
There are some issues with the
thomas_Algfunction in your implementation:-
There is a mistake in the back substitution loop: the line
x[i] = 1/A[i] * (f[i] - ([i] * x[i+1]))should bex[i] = 1/A[i] * (f[i] - (C[i] * x[i+1])), replacing the[i]withC[i]. -
The forward elimination in the
thomas_Algfunction seems to incorrectly update theAarray. Instead, it should update theBarray, which represents the main diagonal after forward elimination. -
It's important to ensure that when assembling the tridiagonal matrix
Tfor use withnumpy.linalg.solve, you are usingnumpy.diagflatinstead ofnumpy.diagto create the off-diagonal arrays.
Here's a corrected version of your Thomas algorithm implementation and subsequent use of
np.linalg.solve:import numpy as np import numpy.linalg as la # The Thomas algorithm function which introduces the matrices: A, B, C, f as input parameters def thomas_Alg(A, B, C, f): n = len(f) # Forward elimination for i in range(1, n): mult = B[i-1] / A[i-1] A[i] = A[i] - mult * C[i-1] f[i] = f[i] - mult * f[i-1] # Back substitution x = [0] * n x[n-1] = f[n-1] / A[n-1] for i in range(n-2, -1, -1): x[i] = (f[i] - C[i] * x[i+1]) / A[i] return x n = 10 A = [2] * n B = [-1] * (n - 1) C = [-1] * (n - 1) f = [1] * n # Thomas algorithm solution thomas_solution = thomas_Alg(A.copy(), B.copy(), C.copy(), f.copy()) print("Solution from Thomas algorithm:") print(thomas_solution) # Assembling the full matrix for numpy.linalg.solve T = np.diagflat(A) + np.diagflat(B, -1) + np.diagflat(C, 1) # numpy.linalg.solve solution numpy_solution = la.solve(T, f) print("Solution from NumPy 'linalg.solve':") print(numpy_solution)This script should work now without any errors, and it will print both solutions obtained from your Thomas algorithm and NumPy's built-in linear equation solver. The
.copy()is used to prevent the original lists from being altered during the forward elimination process of the Thomas algorithm. -