lfel.c

The Free Finite Element Package is a library which contains numerical methods required when working

/*--------------------------------------------------------------------------

Free Finite Element Package                             
Copyright (c) 2002-2006 by Joerg Frochte
All rights reserved.

Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:

1. Redistributions of source code must retain the above copyright
   notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright
   notice, this list of conditions and the following disclaimer in the
   documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
."AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
----------------------------------------------------------------------------*/

#include "lfel.h"

/** 
 * \file 
 * \brief Implementation of finite elements with linear base functions including FEM-Solvers like Multigrid Methods
 * \author Joerg Frochte 
*/

static inline MEML_FLOAT N1 (MEML_FLOAT x, MEML_FLOAT y)
{
  return (1 - x - y);
}
static inline double N2 (MEML_FLOAT x, MEML_FLOAT y)
{
  y = y;
  return (x);
}
static inline double N3 (MEML_FLOAT x, MEML_FLOAT y)
{
  x = x;
  return (y);
}

static inline double f_delta1(double rmax,double kmax,double hmax, double eps)
{
  double temp;

  /*
  temp =  1/(2*(kmax));
  temp =  1/(2*(kmax+rmax));
  temp =  sqrt(kmax-eps/hmax)/(0.5*(kmax+rmax));
  temp =  0;
  */

  temp =  0;
  temp =  1/(2*kmax);

  return(temp);
}

#ifndef DOXYGEN_SHOULD_SKIP_THIS
static inline int fuzzy_less(MEML_FLOAT x, MEML_FLOAT y)
{
    if (0 <= (y-x)+MEML_EPS)
    {
	return (MEML_TRUE);
    }
    else
	return (MEML_FALSE);
}
#endif

void lfel_compute_derivatives2 (const VECTOR * u1, MESH * mesh,
				MEML_INT node, MEML_INT number_of_nodes,
				MEML_FLOAT * u1_xx, MEML_FLOAT * u1_yy,
				MEML_FLOAT * u1_xy, MEML_FLOAT * u1_x,
				MEML_FLOAT * u1_y);
#ifndef DOXYGEN_SHOULD_SKIP_THIS
/* only for 1x3-Vectors */
void lfel_kreuzprodukt (VECTOR * a, VECTOR * b, VECTOR * c)
{

  c->data[0] = a->data[1] * b->data[2] - a->data[2] * b->data[1];

  c->data[1] = a->data[2] * b->data[0] - a->data[0] * b->data[2];

  c->data[2] = a->data[0] * b->data[1] - a->data[1] * b->data[0];
}
#endif

static inline VECTOR *lfel_calculate_plain (MEML_INT triangle, VECTOR * v,
					    MESH * mesh)
{
  TRANSFORMATION *transformation = mesh->transformation;
  VECTOR *c, *b1, *b2;
  VECTOR *plain;
  TRIANGLE the_triangle;

  c = meml_vector_new (3);
  b1 = meml_vector_new (3);
  b2 = meml_vector_new (3);
  plain = meml_vector_new (3);

  /* b1xb2=c */
  /* konstruiere b1 und b2 */
  meml_vector_element_set_f (b1, 0, transformation[triangle].B[0][0]);
  meml_vector_element_set_f (b1, 1, transformation[triangle].B[1][0]);

  meml_vector_element_set_f (b2, 0, transformation[triangle].B[0][1]);
  meml_vector_element_set_f (b2, 1, transformation[triangle].B[1][1]);

  /* dritte komponente berechnen */
  the_triangle = smfl_get_triangle (triangle, mesh->triangles->data);

  b1->data[2] = v->data[the_triangle.p[1] - 1] -
    v->data[the_triangle.p[0] - 1];
  b2->data[2] = v->data[the_triangle.p[2] - 1] -
    v->data[the_triangle.p[0] - 1];

  /* kreuprodukt berechnen */
  lfel_kreuzprodukt (b1, b2, c);

  if (c->data[2] != 0)
    {
      /* p[0]*x + p[1]*y + p[2] = z */
      plain->data[0] = -(c->data[0] / c->data[2]);
      plain->data[1] = -(c->data[1] / c->data[2]);
    }
  else
    {
      fprintf (stderr, "Error in lfel_grad: div with zero!\n");
      exit (EXIT_FAILURE);
    }

  plain->data[2] = v->data[the_triangle.p[0] - 1]
    - plain->data[0] * mesh->points->data[2 * (the_triangle.p[0] - 1)]

    - plain->data[1] * mesh->points->data[2 * (the_triangle.p[0] - 1) + 1];

  meml_vector_free (c);
  meml_vector_free (b1);
  meml_vector_free (b2);


  return (plain);
}

static int lfel_search_last_son(MESH **mesh ,const MEML_INT depth, 
				 MEML_INT *level,MEML_INT * triangle,
				 MEML_FLOAT x, MEML_FLOAT y)
{
  MEML_INT i,dreieck;
  MEML_FLOAT dalt[2], d[2], det, transx, transy;
  TRANSFORMATION *backtransformation;
  TRIANGLE the_triangle;

  if (mesh[(*level)]->son != NULL)
    {
      backtransformation = mesh[(*level)+1]->backtransformation;

      for (i=0;i<4;i++)
	{
	  dreieck=mesh[(*level)]->son[(*triangle)][i];
	  
	  /* existiert ein sohn ? */
	  if (dreieck != -1)
	    {
	      the_triangle = 
		smfl_get_triangle (dreieck,mesh[(*level)+1]->triangles->data);
	      
	      dalt[0] = mesh[(*level)+1]->points->data[(the_triangle.p[0] - 1) * 2];
	      dalt[1] = mesh[(*level)+1]->points->data[(the_triangle.p[0] - 1) * 2 + 1];

	      d[0] = backtransformation[dreieck].B[0][0] * dalt[0] +
		backtransformation[dreieck].B[0][1] * dalt[1];

	      d[1] = backtransformation[dreieck].B[1][0] * dalt[0] +
		backtransformation[dreieck].B[1][1] * dalt[1];

	      det = backtransformation[dreieck].det;

	      transx = (backtransformation[dreieck].B[0][0] * x +
			backtransformation[dreieck].B[0][1] * y - d[0]) * det;

	      transy = (backtransformation[dreieck].B[1][0] * x +
			backtransformation[dreieck].B[1][1] * y - d[1]) * det;

	      /* liegt der punkt im bereich es sohnes ? */
	      if ( ( fuzzy_less(0,transx) ) && ( fuzzy_less(0,transy))  && ( fuzzy_less(0,1-transx-transy) ) )
		{
		  (*triangle)=dreieck;
		  (*level) = (*level) +1;
		  return(lfel_search_last_son(mesh ,depth, level,triangle,x,y));
		}
	    }
	}
      return(MEML_FALSE);
    }
  else
    {
      return(MEML_TRUE);
    }

}

/**
 * \brief returns the value of a function at the point (x,y) 
 * defined by the mesh and the values v at its node 
 * for linear basis functions
 *
 * The order in v depends on the order of the points in mesh. 
 */
double lfel_discrete_function_value_treesearch (const VECTOR * v, MESH ** mesh,
						const MEML_INT depth, 
						const MEML_FLOAT x,
						const MEML_FLOAT y)
{
  MEML_INT i, number_of_triangles = mesh[0]->number_of_triangles;
  MEML_FLOAT transx, transy;
  TRIANGLE the_triangle;
  MEML_FLOAT d[2], dalt[2], konst, z, det;
  TRANSFORMATION *backtransformation = mesh[0]->backtransformation;
  TRANSFORMATION *transformation = mesh[0]->transformation;
  VECTOR *b1, *b2, *e, *s;
  MEML_INT level, triangle,kontrolle=0;

  for (i = 0; i < number_of_triangles; i++)
    {
      the_triangle = smfl_get_triangle (i, mesh[0]->triangles->data);

      dalt[0] = mesh[0]->points->data[(the_triangle.p[0] - 1) * 2];
      dalt[1] = mesh[0]->points->data[(the_triangle.p[0] - 1) * 2 + 1];

      d[0] = backtransformation[i].B[0][0] * dalt[0] +
	backtransformation[i].B[0][1] * dalt[1];

      d[1] = backtransformation[i].B[1][0] * dalt[0] +
	backtransformation[i].B[1][1] * dalt[1];

      det = backtransformation[i].det;

      transx = (backtransformation[i].B[0][0] * x +
		backtransformation[i].B[0][1] * y - d[0]) * det;

      transy = (backtransformation[i].B[1][0] * x +
		backtransformation[i].B[1][1] * y - d[1]) * det;

      if ( ( fuzzy_less(0,transx) ) && ( fuzzy_less(0,transy))  && ( fuzzy_less(0,1-transx-transy) ) )
	{
	  triangle=i;
	  level=0;
	  kontrolle=-1;
	  /* sohn suchen */
	  if ( MEML_TRUE == 
	       lfel_search_last_son(mesh ,depth,&level,&triangle,x,y))
	    {
	      kontrolle=1;
	    }

	  transformation = mesh[level]->transformation;

	  the_triangle = 
	    smfl_get_triangle (triangle, mesh[level]->triangles->data);
	  
	  b1 = meml_vector_new (3);
	  b2 = meml_vector_new (3);
	  e = meml_vector_new (3);
	  s = meml_vector_new (3);
	  
	  /* b1xb2=c */
	  /* konstruiere b1 und b2 */
	  meml_vector_element_set_f (b1, 0, transformation[triangle].B[0][0]);
	  meml_vector_element_set_f (b1, 1, transformation[triangle].B[1][0]);
	  
	  meml_vector_element_set_f (b2, 0, transformation[triangle].B[0][1]);
	  meml_vector_element_set_f (b2, 1, transformation[triangle].B[1][1]);
	  
	  meml_vector_element_set_f (s, 0,
				     mesh[level]->points->data[2 *
							       (the_triangle.
								p[0] - 1)]);
	  meml_vector_element_set_f (s, 1,
				     mesh[level]->points->data[2 *
							       (the_triangle.
								p[0] - 1) +
							       1]);
	  meml_vector_element_set_f (s, 2,
				     v->data[the_triangle.p[0] - 1]);
	  
	  /* dritte komponente berechnen */
	  
	  b1->data[2] = v->data[the_triangle.p[1] - 1] -
	    v->data[the_triangle.p[0] - 1];
	  b2->data[2] = v->data[the_triangle.p[2] - 1] -
	    v->data[the_triangle.p[0] - 1];
	  
	  lfel_kreuzprodukt (b1, b2, e);
	  
	  /* ebenengleichung 
	     e1 * x + e2*y + e3*z = konst */
	  konst = s->data[0] * e->data[0] +
	    s->data[1] * e->data[1] + s->data[2] * e->data[2];
	  
	  /* ebenengleichung 
	     z = (konst - e1 * x - e2*y)/e3 */
	  z = (konst - e->data[0] * x - e->data[1] * y) / e->data[2];
	  
	  meml_vector_free (b1);
	  meml_vector_free (b2);
	  meml_vector_free (e);
	  meml_vector_free (s);
  
	  if (kontrolle == 1)
	    return (z);
	}

    }

  if ( kontrolle== -1)
    { 
      return(z);
    }
  else
    {
      fprintf (stderr, "tree: Can't look up the point (%e,%e) in the mesh.\n", x, y);
      exit (1);
    }

}

/**
 * \brief returns the value of a function at the point (x,y) 
 * defined by the mesh and the values v at its node 
 * for linear basis functions
 *
 * The order in v depends on the order of the points in mesh. 
 */
double lfel_discrete_function_value (VECTOR * v, MESH * mesh,
				     MEML_FLOAT x, MEML_FLOAT y)
{
  MEML_INT i, number_of_triangles = mesh->number_of_triangles;
  MEML_FLOAT transx, transy;
  TRIANGLE the_triangle;
  MEML_FLOAT d[2], dalt[2], konst, z, det;
  TRANSFORMATION *backtransformation = mesh->backtransformation;
  TRANSFORMATION *transformation = mesh->transformation;
  VECTOR *b1, *b2, *e, *s;

  for (i = 0; i < number_of_triangles; i++)
    {
      the_triangle = smfl_get_triangle (i, mesh->triangles->data);

      dalt[0] = mesh->points->data[(the_triangle.p[0] - 1) * 2];
      dalt[1] = mesh->points->data[(the_triangle.p[0] - 1) * 2 + 1];

      d[0] = backtransformation[i].B[0][0] * dalt[0] +
	backtransformation[i].B[0][1] * dalt[1];

      d[1] = backtransformation[i].B[1][0] * dalt[0] +
	backtransformation[i].B[1][1] * dalt[1];

      det = backtransformation[i].det;

      transx = (backtransformation[i].B[0][0] * x +
		backtransformation[i].B[0][1] * y - d[0]) * det;

      transy = (backtransformation[i].B[1][0] * x +
		backtransformation[i].B[1][1] * y - d[1]) * det;

      if ( ( fuzzy_less(0,transx) ) && ( fuzzy_less(0,transy))  && ( fuzzy_less(0,1-transx-transy) ) )
	{
	  b1 = meml_vector_new (3);
	  b2 = meml_vector_new (3);
	  e = meml_vector_new (3);
	  s = meml_vector_new (3);

	  /* b1xb2=c */
	  /* konstruiere b1 und b2 */
	  meml_vector_element_set_f (b1, 0, transformation[i].B[0][0]);
	  meml_vector_element_set_f (b1, 1, transformation[i].B[1][0]);

	  meml_vector_element_set_f (b2, 0, transformation[i].B[0][1]);
	  meml_vector_element_set_f (b2, 1, transformation[i].B[1][1]);

	  meml_vector_element_set_f (s, 0,
				     mesh->points->data[2 *
							(the_triangle.p[0] -
							 1)]);
	  meml_vector_element_set_f (s, 1,
				     mesh->points->data[2 *
							(the_triangle.p[0] -
							 1) + 1]);
	  meml_vector_element_set_f (s, 2, v->data[the_triangle.p[0] - 1]);

	  /* dritte komponente berechnen */

	  b1->data[2] = v->data[the_triangle.p[1] - 1] -
	    v->data[the_triangle.p[0] - 1];
	  b2->data[2] = v->data[the_triangle.p[2] - 1] -
	    v->data[the_triangle.p[0] - 1];

	  lfel_kreuzprodukt (b1, b2, e);

	  /* ebenengleichung 
	     e1 * x + e2*y + e3*z = konst */
	  konst = s->data[0] * e->data[0] +
	    s->data[1] * e->data[1] + s->data[2] * e->data[2];

	  /* ebenengleichung 
	     z = (konst - e1 * x - e2*y)/e3 */
	  z = (konst - e->data[0] * x - e->data[1] * y) / e->data[2];

	  meml_vector_free (b1);
	  meml_vector_free (b2);
	  meml_vector_free (e);
	  meml_vector_free (s);

	  return (z);
	}
    }

  fprintf (stderr, "Can't look up the point (%e,%e) in the mesh.\n", x, y);
  return(0);
}


static void glaetter(ME_MATRIX * M, VECTOR *b, VECTOR * x)
{
  MEML_INT i, y;
  VECTOR * s;
  CR_MATRIX * A;
  MEML_FLOAT rii=0;

  s = meml_vector_new(b->dim);

  if (M->type == CS)
    {
      A = M->data.compressed_row;

      /* L*x */
#ifdef __HAVE_OPENMP
#pragma omp parallel shared(A,s) private(i,y)
      {
#pragma omp for schedule(static)
#endif
	
	for (i = 0; i < A->rows; i++)
	  {
	    for (y = A->row[i]; y < A->row[i + 1]; y++)
	      {
		/* nur den oberen linken teil */
		if (A->column[y] < i)
		  s->data[i] += A->data[y] * x->data[A->column[y]];
	      }
	  }
	
#ifdef __HAVE_OPENMP
      }
#endif
      
      /* s = -s */
      meml_vector_scaling_f(-1,s);

      /* s = b -s */
      meml_vector_add_f(b,s);

      /* (R+D)x = s */
      for (i = A->rows-1 ; i >= 0; i--)
	{
	  for (y = A->row[i]; y < A->row[i + 1]; y++)
	    {
	      /* nur den oberen linken teil */
	      if (A->column[y] > i)	      
		{
		  s->data[i] = s->data[i] - A->data[y] * x->data[A->column[y]];
		}
	      else if (A->column[y] == i)
		{
		  rii = A->data[y];
		}
	    }

	  x->data[i] = s->data[i] / rii;

	}
    }
  else
    {
      fprintf(stderr,"Waring : For non CS-Type Matrix Jacobi is used"
	      " in multigrid_solver.\n");
      exit(1);      
    }

  meml_vector_free(s);
}

static void lfel_multigrid_function(ME_MATRIX ** A, VECTOR * b, VECTOR * guess, 
				    MESH ** mesh, MEML_INT level, MEML_INT lastLevel,
				    MEML_INT k1,MEML_INT k2)
{
  VECTOR *x,*xDown, *r, *rDown;
  MEML_INT i;

  for (i=0;i<k1;i++)
    glaetter(A[level], b, guess);
  
  r = meml_matrix_vector_mul(A[level],guess);
  meml_vector_scaling_f(-1,r);
  meml_vector_add_f(b,r);
  
  rDown = meml_matrix_vector_mul (mesh[level]->restriction,r);