libs/mathlib/linear.c

   1 #ifndef __APPLE__
   2 #include <malloc.h>
   3 #else
   4 #include <stdlib.h>
   5 #endif
   6 #include <limits.h>
   7 #include <float.h>
   8
   9 #include "mathlib.h"
  10
  11 #define TINY FLT_MIN
  12
  13 void lubksb( float **a, int n, int *indx, float b[] ){
  14 // Solves the set of n linear equations A.X=B. Here a[n][n] is input, not as the matrix
  15 // A but rather as its LU decomposition determined by the routine ludcmp. indx[n] is input
  16 // as the permutation vector returned by ludcmp. b[n] is input as the right-hand side vector
  17 // B, and returns with the solution vector X. a, n and indx are not modified by this routine
  18 // and can be left in place for successive calls with different right-hand sides b. This routine takes
  19 // into account the possibility that b will begin with many zero elements, so it is efficient for use
  20 // in matrix inversion
  21         int i,ii = -1,ip,j;
  22         float sum;
  23
  24         for ( i = 0; i < n; i++ ) {
  25                 ip = indx[i];
  26                 sum = b[ip];
  27                 b[ip] = b[i];
  28                 if ( ii >= 0 ) {
  29                         for ( j = ii; j < i; j++ ) sum -= a[i][j] * b[j];
  30                 }
  31                 else if ( sum ) {
  32                         ii = i;
  33                 }
  34                 b[i] = sum;
  35         }
  36         for ( i = n - 1; i >= 0; i-- ) {
  37                 sum = b[i];
  38                 for ( j = i + 1; j < n; j++ ) sum -= a[i][j] * b[j];
  39                 b[i] = sum / a[i][i];
  40         }
  41 }
  42 /* (C) Copr. 1986-92 Numerical Recipes Software */
  43
  44
  45 int ludcmp( float **a, int n, int *indx, float *d ){
  46 // given a matrix a[n][n] this routine replaces it with the LU decomposition of a rowwise
  47 // permutation of itself. a and n are input. a is output, arranged as in above equation;
  48 // indx[n] is an output vector that records the row permutation effected by the partial
  49 // pivoting; d is output as +/-1 depending on whether the number of row interchanges was even
  50 // or odd, respectively. This routine is used in combination with lubksb to solve linear
  51 // equations or invert a matrix.
  52         int i,imax,j,k;
  53         float big,dum,sum,temp;
  54         float *vv;
  55
  56         imax = 0;
  57         vv = (float*)malloc( sizeof( float ) * n );
  58         *d = 1.0;
  59         for ( i = 0; i < n; i++ ) {
  60                 big = 0.0;
  61                 for ( j = 0; j < n; j++ )
  62                         if ( ( temp = (float)fabs( a[i][j] ) ) > big ) {
  63                                 big = temp;
  64                         }
  65                 if ( big == 0.0 ) {
  66                         return 1;
  67                 }
  68                 vv[i] = 1.0f / big;
  69         }
  70         for ( j = 0; j < n; j++ ) {
  71                 for ( i = 0; i < j; i++ ) {
  72                         sum = a[i][j];
  73                         for ( k = 0; k < i; k++ ) sum -= a[i][k] * a[k][j];
  74                         a[i][j] = sum;
  75                 }
  76                 big = 0.0;
  77                 for ( i = j; i < n; i++ ) {
  78                         sum = a[i][j];
  79                         for ( k = 0; k < j; k++ )
  80                                 sum -= a[i][k] * a[k][j];
  81                         a[i][j] = sum;
  82                         if ( ( dum = vv[i] * (float)fabs( sum ) ) >= big ) {
  83                                 big = dum;
  84                                 imax = i;
  85                         }
  86                 }
  87                 if ( j != imax ) {
  88                         for ( k = 0; k < n; k++ ) {
  89                                 dum = a[imax][k];
  90                                 a[imax][k] = a[j][k];
  91                                 a[j][k] = dum;
  92                         }
  93                         *d = -( *d );
  94                         vv[imax] = vv[j];
  95                 }
  96                 indx[j] = imax;
  97                 if ( a[j][j] == 0.0 ) {
  98                         a[j][j] = TINY;
  99                 }
 100                 if ( j != n ) {
 101                         dum = 1.0f / ( a[j][j] );
 102                         for ( i = j + 1; i < n; i++ ) a[i][j] *= dum;
 103                 }
 104         }
 105         free( vv );
 106         return 0;
 107 }
 108 /* (C) Copr. 1986-92 Numerical Recipes Software */