Be sure to set format long before generating any output I. Consider the problem

Question

Be sure to set format long before generating any output I. Consider the problem Ax = 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). (a) 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 add/sub and mult/div operations separately, then give the overall order of the total operations needed (using O(a) notation). (b) 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 when run on a 1,000x 1,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.

Explanation / Answer

(a) Only n operation will be require to make Gaussian Elimination efficient.

Since each time only one pivot is required and only one row (subtraction/multiplication) will require to make that column entry zero except pivot one. Similarly only n operation will require to back substitution as each time we only need one substraction and multiplication or division require to find x i solutions.

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.