* moved zeroradiant (1.6) into trunk
[xonotic/netradiant.git] / 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         vv=(float*)malloc(sizeof(float)*n);
56         *d=1.0;
57         for (i=0;i<n;i++) {
58                 big=0.0;
59                 for (j=0;j<n;j++)
60                         if ((temp=(float)fabs(a[i][j])) > big) big=temp;
61                 if (big == 0.0) return 1;
62                 vv[i]=1.0f/big;
63         }
64         for (j=0;j<n;j++) {
65                 for (i=0;i<j;i++) {
66                         sum=a[i][j];
67                         for (k=0;k<i;k++) sum -= a[i][k]*a[k][j];
68                         a[i][j]=sum;
69                 }
70                 big=0.0;
71                 for (i=j;i<n;i++) {
72                         sum=a[i][j];
73                         for (k=0;k<j;k++)
74                                 sum -= a[i][k]*a[k][j];
75                         a[i][j]=sum;
76                         if ( (dum=vv[i]*(float)fabs(sum)) >= big) {
77                                 big=dum;
78                                 imax=i;
79                         }
80                 }
81                 if (j != imax) {
82                         for (k=0;k<n;k++) {
83                                 dum=a[imax][k];
84                                 a[imax][k]=a[j][k];
85                                 a[j][k]=dum;
86                         }
87                         *d = -(*d);
88                         vv[imax]=vv[j];
89                 }
90                 indx[j]=imax;
91                 if (a[j][j] == 0.0) a[j][j]=TINY;
92                 if (j != n) {
93                         dum=1.0f/(a[j][j]);
94                         for (i=j+1;i<n;i++) a[i][j] *= dum;
95                 }
96         }
97         free(vv);
98   return 0;
99 }
100 /* (C) Copr. 1986-92 Numerical Recipes Software */