An elliptic partial differential equation in three dimensions is discretized by

Question

An elliptic partial differential equation in three dimensions is discretized by boundary element method. The result is a large dense linear system of equations in which each equation corresponds to a triangular surface element on a large sphere. To improve the accuracy, one must make the triangles smaller and thereby increase the number of equations, but the error shrinks only linearly in proportion to h, the diameter of the largest triangle. A value of h is chosen, the system is solved by Gaussian elimination, and a solution accurate to two digits in obtained in one minute of computer time. It is decided that three digits of accuracy are needed. Assume storage is not a constraint, approximately how much time will be required for the new computation on the same computer?

You may assume that Gaussian elimination is implemented via an LU decomposition. Hint. Since the triangles must cover the sphere, the number of triangles is inversely proportional to the area of the triangles.

Explanation / Answer

We need a co-relation between the increase in the number of new triangles and the change in the value of h.

Since the area of the sphere is constant, what we have is:

no. of triangle * area of each = k;

Assume there were 'n' triangles initially;

then k = n*h2 ;

Error needs to be reduced by 10 times; implies new h' = h/10;

Therefore new no. of Triangle's n' *h' = n *h;

n' = n*h2/ (h/10)2 = 100n.

The time complexity of the above-mentioned method for a dense matrix is: O(n3)

So new time t' = (100 n)3/ n3 t = (106)t = 106 minutes ~ 278 hours

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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