FAST ALGORITHM TEST

KUN LI

Abstract. Some tests for fast algorithm are used in our model problem. Cascadic method in spital is better than time.

1. Model problem

The following burgers equation is used as a model problem.

(1.1) uux - uxx = f
with u(0) = 0 and u(1) = 0.

MOC means that the psuedo time term is added and obtain the steady state solution by time marching method, namely, one solves the following equation until the steady state solution is attained:

2 (1.2) @u-+u @u--e @-u= 0 in (0,1)× (0, oo ) @t @x @x2

We introduce the material time derivative, i.e.,

Du @2u (1.3) --- - e--2-= f in (0,1)× (0, oo ) Dt @x
The first order time discretization for the material derivative can be written as follows:
Du- u(tn,x)--u(tn-1,X(tn--1,x))- (1.4) Dt ~~ Dt ,
where
dX(t,t)-= u(t,X(t,t)), X(t,t) = x. dt

With some finite element space, we got the following scheme:

un -un -1(x - bDt) (1.5) (-h----hDt--------,v)+ A(umh ,v) = (fn,v) v (- Mh
In the tests M h is quadratic elements space.

The scheme can be written in this form

Mhun+1 - M^hun n+1 n+1 (1.6) ----h-Dt-----h-+ Ahuh = Fh
here
integral Mhij = fi(x)fj(x)dx
integral M^hij = fi(x- bDt)fj(x)dx
n sum n u h(x) = uhifi(x)
and
integral Ahij = f'i(x)f'j(x)dx
integral Fn+1 = fi(x)f n+1(x)dx hi
.

fi(x) is the basis function of M h.

The steady solution u = sinpx is used in our test. The results are shown in Table 1.

The tolerance is

n+1 n ||u - u ||2 < edt
. e = 10-8 are used in our test.

number of elements dt = dx dt = dx2 dt = dx3
5 14 (0.0428) 56 (0.0105) 256 (0.0029)
10 25 (0.0236) 203 (0.0027) 1961 (3.5735 × 10-4)
20 45 (0.0124)775 (6.6268 × 10-4)15358 (4.370 × 10-5)

Table 1.1: Iteration number from u = 0. L2 error in ”()”

.

Remark 1: From Table 1, the error of L2 norm should be o(dx3) if we set dt = dx3.

Remark 2: How about e effect? In my other test e < 10-5 can shown the same approximation, but lager than that will not.

Remark 3: In next section, (m,n) the time marching on m elements with dt = dxn.

2. Fast algorithm

2.1. Time. First use large time step, then use small time step.

number of elements(.,1) --> (.,2) --> (.,3)Total
5 14-48-198 260
10 25-166-1386 1557
20 45-609-9725 10379

Table 2.1: Time fast algorithm

.

Remark 1: ”-->” in ”(.,1) --> (.,2)” means the second time marching with the first one’s results as initial solution.

Remark 2: The strategy of using dt = dx- 2 between ”(.,1) --> (.,2)” is not useful and leads more cost.

Remark 2: Because the spital size doesn’t change with different time step, the cost of computation doesn’t change. When the grid is fine, the result is better.

2.2. Cascadic method. First solve the problem on coarse grid, then do prolongation and solve the problem on fine grid.

(53) --> (10,3) --> (20,3)Total
5256-1387-9125 9883

Table 2.2: Cascadic method

.

Remark 1: Because the spital size changes, the cost of computation changes.

Remark 2: Compared with Table 1 and 2.1, it is not necessary to use time fast algorithm after prolongation.