Problem
Consider the problem Ar = b where A is a tridiagonal matrix (a matrix where nonzero entries appear only on the main diagonal and on the diagonals immediately above and below it).
• What is the operation count for the elimination and back substitution steps of an efficient Gaussian elimination applied to this case? In other words, if you use your knowledge of the form of A to avoid unnecessary operations, how much more cost-efficient can the GJE algorithm be made? Count- ing add/sub/mult/div operations, give the overall order of the total operations needed (using O(n?) notation).
• Imagine that you're working on a problem that will require you to solve a large (50,000x50,000) tridiagonal system. If standard GJE takes roughly a second to finish on your machine when run on a 1,000x1,000 tridiagonal system, determine whether it would be worth your time to code a custom version of GJE (i.e., tailored to the tridiagonal format) to run on your problem.