GRASS Programmer's Manual  6.5.svn(2014)-r66266
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
solvers_direct.c
Go to the documentation of this file.
1 
2 /*****************************************************************************
3  *
4  * MODULE: Grass PDE Numerical Library
5  * AUTHOR(S): Soeren Gebbert, Berlin (GER) Dec 2006
6  * soerengebbert <at> gmx <dot> de
7  *
8  * PURPOSE: direkt linear equation system solvers
9  * part of the gpde library
10  *
11  * COPYRIGHT: (C) 2007 by the GRASS Development Team
12  *
13  * This program is free software under the GNU General Public
14  * License (>=v2). Read the file COPYING that comes with GRASS
15  * for details.
16  *
17  *****************************************************************************/
18 
19 #include <math.h>
20 #include <unistd.h>
21 #include <stdio.h>
22 #include <string.h>
23 #include "grass/gis.h"
24 #include "grass/glocale.h"
25 #include "grass/gmath.h"
26 
27 #define TINY 1.0e-20
28 #define COMP_PIVOT 100
29 
43 int G_math_solver_gauss(double **A, double *x, double *b, int rows)
44 {
45  G_message(_("Starting direct gauss elimination solver"));
46 
47  G_math_gauss_elimination(A, b, rows);
48  G_math_backward_solving(A, x, b, rows);
49 
50  return 1;
51 }
52 
67 int G_math_solver_lu(double **A, double *x, double *b, int rows)
68 {
69  int i;
70 
71  double *c, *tmpv;
72 
73  G_message(_("Starting direct lu decomposition solver"));
74 
75  tmpv = G_alloc_vector(rows);
76  c = G_alloc_vector(rows);
77 
78  G_math_lu_decomposition(A, b, rows);
79 
80 #pragma omp parallel
81  {
82 
83 #pragma omp for schedule (static) private(i)
84  for (i = 0; i < rows; i++) {
85  tmpv[i] = A[i][i];
86  A[i][i] = 1;
87  }
88 
89 #pragma omp single
90  {
91  G_math_forward_solving(A, b, b, rows);
92  }
93 
94 #pragma omp for schedule (static) private(i)
95  for (i = 0; i < rows; i++) {
96  A[i][i] = tmpv[i];
97  }
98 
99 #pragma omp single
100  {
101  G_math_backward_solving(A, x, b, rows);
102  }
103  }
104 
105  G_free(c);
106  G_free(tmpv);
107 
108 
109  return 1;
110 }
111 
126 int G_math_solver_cholesky(double **A, double *x, double *b, int bandwith,
127  int rows)
128 {
129 
130  G_message(_("Starting cholesky decomposition solver"));
131 
132  if (G_math_cholesky_decomposition(A, rows, bandwith) != 1) {
133  G_warning(_("Unable to solve the linear equation system"));
134  return -2;
135  }
136 
137  G_math_forward_solving(A, b, b, rows);
138  G_math_backward_solving(A, x, b, rows);
139 
140  return 1;
141 }
142 
155 void G_math_gauss_elimination(double **A, double *b, int rows)
156 {
157  int i, j, k;
158 
159  double tmpval = 0.0;
160 
161  /*compute the pivot -- commented out, because its meaningless
162  to compute it only nth times. */
163  /*G_math_pivot_create(A, b, rows, 0); */
164 
165  for (k = 0; k < rows - 1; k++) {
166 #pragma omp parallel for schedule (static) private(i, j, tmpval) shared(k, A, b, rows)
167  for (i = k + 1; i < rows; i++) {
168  tmpval = A[i][k] / A[k][k];
169  b[i] = b[i] - tmpval * b[k];
170  for (j = k + 1; j < rows; j++) {
171  A[i][j] = A[i][j] - tmpval * A[k][j];
172  }
173  }
174  }
175 
176  return;
177 }
178 
192 void G_math_lu_decomposition(double **A, double *b, int rows)
193 {
194 
195  int i, j, k;
196 
197  /*compute the pivot -- commented out, because its meaningless
198  to compute it only nth times. */
199  /*G_math_pivot_create(A, b, rows, 0); */
200 
201  for (k = 0; k < rows - 1; k++) {
202 #pragma omp parallel for schedule (static) private(i, j) shared(k, A, rows)
203  for (i = k + 1; i < rows; i++) {
204  A[i][k] = A[i][k] / A[k][k];
205  for (j = k + 1; j < rows; j++) {
206  A[i][j] = A[i][j] - A[i][k] * A[k][j];
207  }
208  }
209  }
210 
211  return;
212 }
213 
227 int G_math_cholesky_decomposition(double **A, int rows, int bandwith)
228 {
229 
230  int i = 0, j = 0, k = 0;
231 
232  double sum_1 = 0.0;
233 
234  double sum_2 = 0.0;
235 
236  int colsize;
237 
238  if (bandwith <= 0)
239  bandwith = rows;
240 
241  colsize = bandwith;
242 
243  for (k = 0; k < rows; k++) {
244 #pragma omp parallel for schedule (static) private(i, j, sum_2) shared(A, k) reduction(+:sum_1)
245  for (j = 0; j < k; j++) {
246  sum_1 += A[k][j] * A[k][j];
247  }
248 
249  if (0 > (A[k][k] - sum_1)) {
250  G_warning("Matrix is not positive definite. break.");
251  return -1;
252  }
253  A[k][k] = sqrt(A[k][k] - sum_1);
254  sum_1 = 0.0;
255 
256  if ((k + bandwith) > rows) {
257  colsize = rows;
258  }
259  else {
260  colsize = k + bandwith;
261  }
262 
263 #pragma omp parallel for schedule (static) private(i, j, sum_2) shared(A, k, sum_1, colsize)
264 
265  for (i = k + 1; i < colsize; i++) {
266  sum_2 = 0.0;
267  for (j = 0; j < k; j++) {
268  sum_2 += A[i][j] * A[k][j];
269  }
270  A[i][k] = (A[i][k] - sum_2) / A[k][k];
271  }
272 
273  }
274  /*we need to copy the lower triangle matrix to the upper trianle */
275 #pragma omp parallel for schedule (static) private(i, k) shared(A, rows)
276  for (k = 0; k < rows; k++) {
277  for (i = k + 1; i < rows; i++) {
278  A[k][i] = A[i][k];
279  }
280  }
281 
282 
283  return 1;
284 }
285 
296 void G_math_backward_solving(double **A, double *x, double *b, int rows)
297 {
298  int i, j;
299 
300  for (i = rows - 1; i >= 0; i--) {
301  for (j = i + 1; j < rows; j++) {
302  b[i] = b[i] - A[i][j] * x[j];
303  }
304  x[i] = (b[i]) / A[i][i];
305  }
306 
307  return;
308 }
309 
320 void G_math_forward_solving(double **A, double *x, double *b, int rows)
321 {
322  int i, j;
323 
324  double tmpval = 0.0;
325 
326  for (i = 0; i < rows; i++) {
327  tmpval = 0;
328  for (j = 0; j < i; j++) {
329  tmpval += A[i][j] * x[j];
330  }
331  x[i] = (b[i] - tmpval) / A[i][i];
332  }
333 
334  return;
335 }
336 
337 
357 int G_math_pivot_create(double **A, double *b, int rows, int start)
358 {
359  int num = 0; /*number of changed rows */
360 
361  int i, j, k;
362 
363  double max;
364 
365  int number = 0;
366 
367  double tmpval = 0.0, s = 0.0;
368 
369  double *link = NULL;
370 
371  link = G_alloc_vector(rows);
372 
373  G_debug(2, "G_math_pivot_create: swap rows if needed");
374  for (i = start; i < rows; i++) {
375  s = 0.0;
376  for (k = i + 1; k < rows; k++) {
377  s += fabs(A[i][k]);
378  }
379  max = fabs(A[i][i]) / s;
380  number = i;
381  for (j = i + 1; j < rows; j++) {
382  s = 0.0;
383  for (k = j; k < rows; k++) {
384  s += fabs(A[j][k]);
385  }
386  /*search for the pivot element */
387  if (max < fabs(A[j][i]) / s) {
388  max = fabs(A[j][i] / s);
389  number = j;
390  }
391  }
392  if (max == 0) {
393  max = TINY;
394  G_warning("Matrix is singular");
395  }
396  /*if an pivot element was found, swap the les entries */
397  if (number != i) {
398 
399  G_debug(4, "swap row %i with row %i", i, number);
400 
401  if (b != NULL) {
402  tmpval = b[number];
403  b[number] = b[i];
404  b[i] = tmpval;
405  }
406  G_math_d_copy(A[number], link, rows);
407  G_math_d_copy(A[i], A[number], rows);
408  G_math_d_copy(link, A[i], rows);
409  num++;
410  }
411  }
412 
413  G_free_vector(link);
414 
415  return num;
416 }
int G_math_solver_lu(double **A, double *x, double *b, int rows)
The LU solver for quardatic matrices.
void G_free(void *buf)
Free allocated memory.
Definition: gis/alloc.c:142
float b
Definition: named_colr.c:8
void G_math_forward_solving(double **A, double *x, double *b, int rows)
forward solving
int G_math_solver_cholesky(double **A, double *x, double *b, int bandwith, int rows)
The choleksy decomposition solver for quardatic, symmetric positiv definite matrices.
long num
Definition: g3dcats.c:93
#define max(x, y)
Definition: draw2.c:69
int G_math_cholesky_decomposition(double **A, int rows, int bandwith)
cholesky decomposition for symmetric, positiv definite matrices with bandwith optimization ...
int G_math_pivot_create(double **A, double *b, int rows, int start)
Optimize the structure of the linear equation system with a common pivoting strategy.
int G_math_solver_gauss(double **A, double *x, double *b, int rows)
The gauss elimination solver for quardatic matrices.
void G_math_lu_decomposition(double **A, double *b, int rows)
lu decomposition
void G_free_vector(double *v)
Vector memory deallocation.
Definition: dalloc.c:129
#define TINY
void G_message(const char *msg,...)
Print a message to stderr.
Definition: lib/gis/error.c:74
void G_math_d_copy(double *x, double *y, int rows)
Copy the vector x to y.
Definition: blas_level_1.c:236
void G_math_backward_solving(double **A, double *x, double *b, int rows)
backward solving
return NULL
Definition: dbfopen.c:1394
G_warning("category support for [%s] in mapset [%s] %s", name, mapset, type)
int G_debug(int level, const char *msg,...)
Print debugging message.
Definition: gis/debug.c:51
void G_math_gauss_elimination(double **A, double *b, int rows)
Gauss elimination.
double * G_alloc_vector(size_t n)
Vector matrix memory allocation.
Definition: dalloc.c:41