What lies beyond

Here are some class diagrams, that show how different parts of the solution are organized



The main part of the code with adaptive refinement





The part of the code, showing how domain decomposition is organized





The part of the code, showing modification of domain decomposition with parallel computations





The description of some basic classes, that were not included in the previous diagrams

Rates of convergence. Using DD preconditioning

Convergence of different methods solving system of linear equations for finite element method on grids of different sizes.

• The asterisk means that not the actual number of iterations is presented. The actual number is multiplied by some constant, so that the iterations in subdomains would also be taken into consideration.
• The number of iterations for Gauss method assumed to be equal to size of the matrix.
• Jacobi converges too slow, that's why here it is shown for accuracy 1e-5; 1e-8 for all the rest
• CG - stands for Conjugate Gradient method
• Additive Schwartz can be accelerated, by performing the iterations in subdomains parallel (my implementation accelerated it in nearly 1.3 times)
  

Adaptive refinement

The pictures below show how we come from big elements to smaller ones step by step, where it is needed.

Fine




Very fine




In 3D from a nice viewing point it looks like this

This picture consists of 15385 triangles



Another variant

Comparison of different approaches

Comparison of the error
(compared to very fine grid results;
the number after comma in the legend is N from the problem description)

Modifying:

• number of nodes
• degree of polynomial
  
• adding partial refinement

The refined domains look as follows
N=5



N=11

this one is refined 4 times, but the number of degrees of freedom is modified a little

For the points from the problem description the fine result is

• (0.25, 0.25) 0.03272
• (5/6, 1/6) 0.01840
  
  

It works!

Applying linear functions we obtain the following pictures.
For N = 5

For N = 11

Derivation of the discrete problem

A.

Number of degrees of freedom in :

.
Number of elements in :
,
effective (those that have at least one variable vertex):
.
B.

Take
,
then

integrating by parts we have:
,
,
which implies:

or

C.
Checking the assumptions:

1. Symmetry:
a(u,v) = a(v,u)
2. Continuity:

3. V-ellipticity:
Poincare–Friedrichs Inequality implies that for

,
s = 1 for our domain.
4. Continuity of L(v)=(1,v)
If we apply Schwartz inequality we have:
|L(v)|=|(1,v)|≤||1||||v||=||v||

E.

If we move to a finite dimensional space we will have to find the projection of the solution on this space

Instead of v we choose basis functions and get:

a(.,.) is a bilinear form, that allows us to take the sum out of it
,
for all j.
As both the left and the right side are integrals over the domain, we can divide them into parts, each corresponding to one element and compute the stiffness matrix and the load vector as the sum of these integrals in all finite elements. And since the functions have local support, there will be at most 6 triangles where one of the basis functions is non-zero. And each element will have at most 3 non zero basis functions.

G.

Transformation to standard triangle is
,
where
.
So, in order to use the solution from the reference triangle we should multiply gradient

and multiply the integral by Jacobian.