Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-previewΒ· openaiHugging Face Suzhen/CodeChat

TASK 1. Calculate the number of arithmetic operations that are required to solve a…

  1. 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?

  2. 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 x
    

    TASK 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.

  3. User

    how to print the matrix x in task 3

  4. Assistant

    To print the solution vector x obtained from the Thomas algorithm in Task 3, you can simply add a print statement after the line where the thomas_algorithm function 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_algorithm function from Task 2 that receives the arrays A, B, C, and f as inputs and returns the solution vector x.

    The print statement will output the solution vector x to 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.

  5. 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 iterations
    

    n = 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 interations
    

    x[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
    
  6. Assistant

    There are some issues with the thomas_Alg function in your implementation:

    1. There is a mistake in the back substitution loop: the line x[i] = 1/A[i] * (f[i] - ([i] * x[i+1])) should be x[i] = 1/A[i] * (f[i] - (C[i] * x[i+1])), replacing the [i] with C[i].

    2. The forward elimination in the thomas_Alg function seems to incorrectly update the A array. Instead, it should update the B array, which represents the main diagonal after forward elimination.

    3. It's important to ensure that when assembling the tridiagonal matrix T for use with numpy.linalg.solve, you are using numpy.diagflat instead of numpy.diag to 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.