libs/mathlib/linear.c

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