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 {
  22         int i,ii=-1,ip,j;
  23         float sum;
  24
  25         for (i=0;i<n;i++) {
  26                 ip=indx[i];
  27                 sum=b[ip];
  28                 b[ip]=b[i];
  29                 if (ii>=0)
  30                         for (j=ii;j<i;j++) sum -= a[i][j]*b[j];
  31                 else if (sum) ii=i;
  32                 b[i]=sum;
  33         }
  34         for (i=n-1;i>=0;i--) {
  35                 sum=b[i];
  36                 for (j=i+1;j<n;j++) sum -= a[i][j]*b[j];
  37                 b[i]=sum/a[i][i];
  38         }
  39 }
  40 /* (C) Copr. 1986-92 Numerical Recipes Software */
  41
  42
  43 int ludcmp(float **a, int n, int *indx, float *d)
  44 // given a matrix a[n][n] this routine replaces it with the LU decomposition of a rowwise
  45 // permutation of itself. a and n are input. a is output, arranged as in above equation;
  46 // indx[n] is an output vector that records the row permutation effected by the partial
  47 // pivoting; d is output as +/-1 depending on whether the number of row interchanges was even
  48 // or odd, respectively. This routine is used in combination with lubksb to solve linear
  49 // equations or invert a matrix.
  50 {
  51         int i,imax,j,k;
  52         float big,dum,sum,temp;
  53         float *vv;
  54
  55         imax = 0;
  56         vv=(float*)malloc(sizeof(float)*n);
  57         *d=1.0;
  58         for (i=0;i<n;i++) {
  59                 big=0.0;
  60                 for (j=0;j<n;j++)
  61                         if ((temp=(float)fabs(a[i][j])) > big) big=temp;
  62                 if (big == 0.0) return 1;
  63                 vv[i]=1.0f/big;
  64         }
  65         for (j=0;j<n;j++) {
  66                 for (i=0;i<j;i++) {
  67                         sum=a[i][j];
  68                         for (k=0;k<i;k++) sum -= a[i][k]*a[k][j];
  69                         a[i][j]=sum;
  70                 }
  71                 big=0.0;
  72                 for (i=j;i<n;i++) {
  73                         sum=a[i][j];
  74                         for (k=0;k<j;k++)
  75                                 sum -= a[i][k]*a[k][j];
  76                         a[i][j]=sum;
  77                         if ( (dum=vv[i]*(float)fabs(sum)) >= big) {
  78                                 big=dum;
  79                                 imax=i;
  80                         }
  81                 }
  82                 if (j != imax) {
  83                         for (k=0;k<n;k++) {
  84                                 dum=a[imax][k];
  85                                 a[imax][k]=a[j][k];
  86                                 a[j][k]=dum;
  87                         }
  88                         *d = -(*d);
  89                         vv[imax]=vv[j];
  90                 }
  91                 indx[j]=imax;
  92                 if (a[j][j] == 0.0) a[j][j]=TINY;
  93                 if (j != n) {
  94                         dum=1.0f/(a[j][j]);
  95                         for (i=j+1;i<n;i++) a[i][j] *= dum;
  96                 }
  97         }
  98         free(vv);
  99   return 0;
 100 }
 101 /* (C) Copr. 1986-92 Numerical Recipes Software */