Matrices with banded structure are a type of sparse matrices that often arise in computational science...

   

Transcribed Image Text:

Matrices with banded structure are a type of sparse matrices that often arise in computational science applications, especially discretizing differential equations (you will see this later). Banded structure means that the nonzero entries are not too far off the diagonal. The constant k = max{i-j: Aj #0} is called the bandwidth. While you could solve Ax = b with Gaussian elimination, which takes O(n³) elementary operations, it would be very inefficient. A matrix of bandwidth 1 looks like L = m12 m21 M22 m23 feed m32 m33 m34 mn,n-1 mnn, where the empty entries are zeros. The LU factors for A look like 1 A = ull U12 and U = 4)-[*) Inn-1 121 1 mil 132 1 U22 U23 U33 U34 Unn, In general, the LU factors for a matrix A of bandwidth k will also have bandwidth k (assuming no pivoting). Activate Window In this problem, you will write a banded LU solver that takes advantage of the structure of A. You will be given a list of matrices, along with the associated right-acti hand side vectors b, as well as the bandwith, k. These are stored in A_list, b_list, and k_list, respectively. Write functions to compute the LU factorization of a banded matrix and solve the linear systems by using banded forward and banded backward substitution. In taking advantage of the banded structure, make sure that your code doesn't perform any operations on the parts of the matrix that are zero No pivoting is required. You should not use scipy. Linalg. lu or the like. Note: In practice, L and U are stored in-place, overwriting A banded to reduce storage cost. If you want to re-use the storage space of a particular A matrix to hold L in the lower triangular portion (without the main diagonal) and U in the upper triangular portion, that is fine. The autograder will only check the important diagonals of each L and U inside L_list and U_list. To demonstrate the performance benefits from using the banded structure of a given matrix, you will time the execution of your banded solver for each matrix in A_list. You will also compute the time required to solve Ax=b for each matrix in A_list using la. solve. Make a plot comparing both sets of your timing data versus the size (number of rows) of each matrix from A_list using the function plot_times (dims, times_banded, times_full). The function accepts dims, a list of integers of size of linear systems, times_banded, a list of integers for times for solving the system using your banded solver and times_full, a list of integers for times for solving the system using la.solve. You may time code execution in Python as follows import time start_time = time.process_time() #INSERT CODE TO BE TIMED HERE end_time = time.process_time() total_time = end_time-start_time 1.For each of the matrices in A_list and right-hand sides in b_list with bandwidth in k_list: • Compute a banded L and U and store it in the lists L_11st and U_list. • Solve LU = b for a and store the solution in x_lists, taking advantage of the banded structure of Land U. • Compute the time it takes to both compute LU and solve for a. • Compute the time it takes to execute la. solve (A,b) 2.Generate a plot containing the timing data for your banded solver and la. solve using plot_times (dims, times_banded, times_full). Your banded solver should scale linearly with the dimension of the banded matrix. INPUT: A_list: A list of numpy arrays . b_list: List right hand sides k_list: The bandwidth, an integer constant . OUTPUT: L_list, U_list: List of L and U factors from each of the matrices in A_list. x_list: List of solutions to each system from A_list and b_list. . Matrices with banded structure are a type of sparse matrices that often arise in computational science applications, especially discretizing differential equations (you will see this later). Banded structure means that the nonzero entries are not too far off the diagonal. The constant k = max{i-j: Aj #0} is called the bandwidth. While you could solve Ax = b with Gaussian elimination, which takes O(n³) elementary operations, it would be very inefficient. A matrix of bandwidth 1 looks like L = m12 m21 M22 m23 feed m32 m33 m34 mn,n-1 mnn, where the empty entries are zeros. The LU factors for A look like 1 A = ull U12 and U = 4)-[*) Inn-1 121 1 mil 132 1 U22 U23 U33 U34 Unn, In general, the LU factors for a matrix A of bandwidth k will also have bandwidth k (assuming no pivoting). Activate Window In this problem, you will write a banded LU solver that takes advantage of the structure of A. You will be given a list of matrices, along with the associated right-acti hand side vectors b, as well as the bandwith, k. These are stored in A_list, b_list, and k_list, respectively. Write functions to compute the LU factorization of a banded matrix and solve the linear systems by using banded forward and banded backward substitution. In taking advantage of the banded structure, make sure that your code doesn't perform any operations on the parts of the matrix that are zero No pivoting is required. You should not use scipy. Linalg. lu or the like. Note: In practice, L and U are stored in-place, overwriting A banded to reduce storage cost. If you want to re-use the storage space of a particular A matrix to hold L in the lower triangular portion (without the main diagonal) and U in the upper triangular portion, that is fine. The autograder will only check the important diagonals of each L and U inside L_list and U_list. To demonstrate the performance benefits from using the banded structure of a given matrix, you will time the execution of your banded solver for each matrix in A_list. You will also compute the time required to solve Ax=b for each matrix in A_list using la. solve. Make a plot comparing both sets of your timing data versus the size (number of rows) of each matrix from A_list using the function plot_times (dims, times_banded, times_full). The function accepts dims, a list of integers of size of linear systems, times_banded, a list of integers for times for solving the system using your banded solver and times_full, a list of integers for times for solving the system using la.solve. You may time code execution in Python as follows import time start_time = time.process_time() #INSERT CODE TO BE TIMED HERE end_time = time.process_time() total_time = end_time-start_time 1.For each of the matrices in A_list and right-hand sides in b_list with bandwidth in k_list: • Compute a banded L and U and store it in the lists L_11st and U_list. • Solve LU = b for a and store the solution in x_lists, taking advantage of the banded structure of Land U. • Compute the time it takes to both compute LU and solve for a. • Compute the time it takes to execute la. solve (A,b) 2.Generate a plot containing the timing data for your banded solver and la. solve using plot_times (dims, times_banded, times_full). Your banded solver should scale linearly with the dimension of the banded matrix. INPUT: A_list: A list of numpy arrays . b_list: List right hand sides k_list: The bandwidth, an integer constant . OUTPUT: L_list, U_list: List of L and U factors from each of the matrices in A_list. x_list: List of solutions to each system from A_list and b_list. .

Answer rating: 100% (QA)

The problem involves implementing a banded LU solver and comparing its performance with the builtin ... View the full answer