Suppose that multiplying two general n by n matrices takes 3 seconds on a given

Question

Suppose that multiplying two general n by n matrices takes 3 seconds on a given computer, if n = 1000. Estimate how much time it will take to compute the LU-decomposition of such a matrix. Suppose that solving a general system of linear equations of dimension 1000 takes 10 seconds on a given computer. Estimate how much time it will take to solve a tridiagonal linear system of dimension 10^6 on that computer. How many divisions are needed for LU-decomposition of an n by n tridiagonal matrix (not counting multiplications and additions)? How many divisions are needed for LU-decomposition of an n by n general matrix (not counting multiplications and additions)?

Explanation / Answer

a) It is known for a fact that multiplying n*n matrix takes n3 time in general while LU-decomposition takes approximately n3 /3 multiplications and divisions.

As given, general multiplication take 3 seconds. Hence LU will take 3/3=1 sec

b) Solving a general system of n linear equations takes approximately n3 / 3 multiplications and divisions, while solving a tridiagonal system takes approximately 5n multiplications and divisions. Thus the answer is

[(5*106)/(10003 / 3)]*10 = (15*106 / 109)*10 = 0.15 seconds

c) Tridiagonal requires (2n-2) multiplication and divisions.

d) We have to eliminate n(n1)/2 terms below the main diagonal. Each elimination requires computing the row multiplier, which involves division by the pivotal element.

Implementing this verbatim, one gets n(n1)/2 divisions. However, as Algebraic Pavel notes, one can compute the reciprocal of the pivot first, and then the rest is multiplication. Hence, n1 divisions.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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