| 1 |
|
| /* eigens.c |
| 2 |
|
| * |
| 3 |
|
| * Eigenvalues and eigenvectors of a real symmetric matrix |
| 4 |
|
| * |
| 5 |
|
| * |
| 6 |
|
| * |
| 7 |
|
| * SYNOPSIS: |
| 8 |
|
| * |
| 9 |
|
| * int n; |
| 10 |
|
| * double A[n*(n+1)/2], EV[n*n], E[n]; |
| 11 |
|
| * void eigens( A, EV, E, n ); |
| 12 |
|
| * |
| 13 |
|
| * |
| 14 |
|
| * |
| 15 |
|
| * DESCRIPTION: |
| 16 |
|
| * |
| 17 |
|
| * The algorithm is due to J. vonNeumann. |
| 18 |
|
| * - - |
| 19 |
|
| * A[] is a symmetric matrix stored in lower triangular form. |
| 20 |
|
| * That is, A[ row, column ] = A[ (row*row+row)/2 + column ] |
| 21 |
|
| * or equivalently with row and column interchanged. The |
| 22 |
|
| * indices row and column run from 0 through n-1. |
| 23 |
|
| * |
| 24 |
|
| * EV[] is the output matrix of eigenvectors stored columnwise. |
| 25 |
|
| * That is, the elements of each eigenvector appear in sequential |
| 26 |
|
| * memory order. The jth element of the ith eigenvector is |
| 27 |
|
| * EV[ n*i+j ] = EV[i][j]. |
| 28 |
|
| * |
| 29 |
|
| * E[] is the output matrix of eigenvalues. The ith element |
| 30 |
|
| * of E corresponds to the ith eigenvector (the ith row of EV). |
| 31 |
|
| * |
| 32 |
|
| * On output, the matrix A will have been diagonalized and its |
| 33 |
|
| * orginal contents are destroyed. |
| 34 |
|
| * |
| 35 |
|
| * ACCURACY: |
| 36 |
|
| * |
| 37 |
|
| * The error is controlled by an internal parameter called RANGE |
| 38 |
|
| * which is set to 1e-10. After diagonalization, the |
| 39 |
|
| * off-diagonal elements of A will have been reduced by |
| 40 |
|
| * this factor. |
| 41 |
|
| * |
| 42 |
|
| * ERROR MESSAGES: |
| 43 |
|
| * |
| 44 |
|
| * None. |
| 45 |
|
| |
| 46 |
|
| Now orders output using code from TQL2 from EISPACK |
| 47 |
|
| * |
| 48 |
|
| */ |
| 49 |
|
| /* |
| 50 |
|
| Copyright 1973, 1991 by Stephen L. Moshier |
| 51 |
|
| Copyleft version. |
| 52 |
|
| */ |
| 53 |
|
| |
| 54 |
|
| #include <math.h> |
| 55 |
|
| |
| 56 |
5 |
| void eigens( double A[], double EV[], double E[], int N ) { |
| 57 |
|
| int IND, L, LL, LM, M, MM, MQ, I, J, IA, LQ; |
| 58 |
|
| int IQ, IM, IL, NLI, NMI; |
| 59 |
|
| double ANORM, ANORMX, AIA, THR, ALM, ALL, AMM, X, Y; |
| 60 |
|
| double SINX, SINX2, COSX, COSX2, SINCS, AIL, AIM; |
| 61 |
|
| double RLI, RMI; |
| 62 |
|
| static double RANGE = 1.0e-10; /*3.0517578e-5;*/ |
| 63 |
|
| |
| 64 |
|
| /* Initialize identity matrix in EV[] */ |
| 65 |
116 |
▶ | for ( J=0; J<N*N; J++ ) |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J=0; J<N*N; J++ ) |
111 |
5 |
116 |
|
| 66 |
111 |
| EV[J] = 0.0; |
| 67 |
5 |
| MM = 0; |
| 68 |
26 |
▶ | for ( J=0; J<N; J++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J=0; J<N; J++ ) { |
21 |
5 |
26 |
|
| 69 |
21 |
| EV[MM + J] = 1.0; |
| 70 |
21 |
| MM += N; |
| 71 |
|
| } |
| 72 |
|
| |
| 73 |
5 |
| ANORM=0.0; |
| 74 |
26 |
▶ | for ( I=0; I<N; I++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( I=0; I<N; I++ ) { |
21 |
5 |
26 |
|
| 75 |
132 |
▶ | for ( J=0; J<N; J++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J=0; J<N; J++ ) { |
111 |
21 |
132 |
|
| 76 |
111 |
▶ | if ( I != J ) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ( I != J ) { |
90 |
21 |
111 |
|
| 77 |
90 |
| IA = I + (J*J+J)/2; |
| 78 |
90 |
| AIA = A[IA]; |
| 79 |
90 |
| ANORM += AIA * AIA; |
| 80 |
|
| } |
| 81 |
|
| } |
| 82 |
|
| } |
| 83 |
5 |
▶ | if ( ANORM > 0.0 ) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ( ANORM > 0.0 ) { |
5 |
0 |
5 |
|
| 84 |
5 |
| ANORM = sqrt( ANORM + ANORM ); |
| 85 |
5 |
| ANORMX = ANORM * RANGE / N; |
| 86 |
5 |
| THR = ANORM; |
| 87 |
|
| |
| 88 |
113 |
▶ | while ( THR > ANORMX ) { |
Branch: 1 branch
| Branch | True | False | Total |
| while ( THR > ANORMX ) { |
108 |
5 |
113 |
|
| 89 |
108 |
| THR /= N; |
| 90 |
|
| |
| 91 |
|
| do { /* while IND != 0 */ |
| 92 |
146 |
| IND = 0; |
| 93 |
|
| |
| 94 |
605 |
▶ | for ( L=0; L<N-1; L++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( L=0; L<N-1; L++ ) { |
459 |
146 |
605 |
|
| 95 |
1753 |
▶ | for ( M=L+1; M<N; M++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( M=L+1; M<N; M++ ) { |
1294 |
459 |
1753 |
|
| 96 |
1294 |
| MQ=(M*M+M)/2; |
| 97 |
1294 |
| LM=L+MQ; |
| 98 |
1294 |
| ALM=A[LM]; |
| 99 |
1294 |
▶ | if ( fabs(ALM) < THR ) |
Branch: 1 branch
| Branch | True | False | Total |
| if ( fabs(ALM) < THR ) |
1162 |
132 |
1294 |
|
| 100 |
1162 |
| continue; |
| 101 |
|
| |
| 102 |
132 |
| IND=1; |
| 103 |
132 |
| LQ=(L*L+L)/2; |
| 104 |
132 |
| LL=L+LQ; |
| 105 |
132 |
| MM=M+MQ; |
| 106 |
132 |
| ALL=A[LL]; |
| 107 |
132 |
| AMM=A[MM]; |
| 108 |
132 |
| X=(ALL-AMM)/2.0; |
| 109 |
132 |
| Y=ALM/sqrt(ALM*ALM+X*X); |
| 110 |
132 |
▶ | if (X >= 0.0) |
Branch: 1 branch
| Branch | True | False | Total |
| if (X >= 0.0) |
46 |
86 |
132 |
|
| 111 |
46 |
| Y=-Y; |
| 112 |
132 |
| SINX = Y / sqrt( 2.0 * (1.0 + sqrt( 1.0-Y*Y)) ); |
| 113 |
132 |
| SINX2=SINX*SINX; |
| 114 |
132 |
| COSX2=1.0-SINX2; |
| 115 |
132 |
| COSX=sqrt(COSX2); |
| 116 |
132 |
| SINCS=SINX*COSX; |
| 117 |
|
| |
| 118 |
|
| /* ROTATE L AND M COLUMNS */ |
| 119 |
1032 |
▶ | for ( I=0; I<N; I++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( I=0; I<N; I++ ) { |
900 |
132 |
1032 |
|
| 120 |
900 |
| IQ=(I*I+I)/2; |
| 121 |
900 |
▶ | if ( (I != M) && (I != L) ) { |
Branch: 2 branches
| Branch | True | False | Total |
| if ( (I != M) && (I != L) ) { |
768 |
132 |
900 |
| if ( (I != M) && (I != L) ) { |
636 |
132 |
768 |
|
| 122 |
636 |
▶ | IM=(I > M) ? M+IQ : I+MQ; |
Branch: 1 branch
| Branch | True | False | Total |
| IM=(I > M) ? M+IQ : I+MQ; |
228 |
408 |
636 |
|
| 123 |
636 |
▶ | IL=(I >= L) ? L+IQ : I+LQ; |
Branch: 1 branch
| Branch | True | False | Total |
| IL=(I >= L) ? L+IQ : I+LQ; |
437 |
199 |
636 |
|
| 124 |
636 |
| AIL=A[IL]; |
| 125 |
636 |
| AIM=A[IM]; |
| 126 |
636 |
| X=AIL*COSX-AIM*SINX; |
| 127 |
636 |
| A[IM]=AIL*SINX+AIM*COSX; |
| 128 |
636 |
| A[IL]=X; |
| 129 |
|
| } |
| 130 |
900 |
| NLI = N*L + I; |
| 131 |
900 |
| NMI = N*M + I; |
| 132 |
900 |
| RLI = EV[ NLI ]; |
| 133 |
900 |
| RMI = EV[ NMI ]; |
| 134 |
900 |
| EV[NLI]=RLI*COSX-RMI*SINX; |
| 135 |
900 |
| EV[NMI]=RLI*SINX+RMI*COSX; |
| 136 |
|
| } |
| 137 |
|
| |
| 138 |
132 |
| X=2.0*ALM*SINCS; |
| 139 |
132 |
| A[LL]=ALL*COSX2+AMM*SINX2-X; |
| 140 |
132 |
| A[MM]=ALL*SINX2+AMM*COSX2+X; |
| 141 |
132 |
| A[LM]=(ALL-AMM)*SINCS+ALM*(COSX2-SINX2); |
| 142 |
|
| } /* for M=L+1 to N-1 */ |
| 143 |
|
| } /* for L=0 to N-2 */ |
| 144 |
|
| |
| 145 |
146 |
▶ | } while ( IND != 0 ); |
Branch: 1 branch
| Branch | True | False | Total |
| } while ( IND != 0 ); |
38 |
108 |
146 |
|
| 146 |
|
| |
| 147 |
|
| } /* while THR > ANORMX */ |
| 148 |
|
| } |
| 149 |
|
| |
| 150 |
|
| /* Extract eigenvalues from the reduced matrix */ |
| 151 |
5 |
| L=0; |
| 152 |
26 |
▶ | for ( J=0; J<N; J++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J=0; J<N; J++ ) { |
21 |
5 |
26 |
|
| 153 |
21 |
| L=L+J+1; |
| 154 |
21 |
| E[J]=A[L-1]; |
| 155 |
|
| } |
| 156 |
|
| |
| 157 |
|
| /* from TQL2, order eigenvalues and -vectors */ |
| 158 |
|
| int II; |
| 159 |
21 |
▶ | for ( II = 1; II < N; II++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( II = 1; II < N; II++) { |
16 |
5 |
21 |
|
| 160 |
16 |
| I = II - 1; |
| 161 |
16 |
| int K = I; |
| 162 |
16 |
| double P = E[I]; |
| 163 |
61 |
▶ | for ( J = II; J < N; J++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J = II; J < N; J++ ) { |
45 |
16 |
61 |
|
| 164 |
45 |
▶ | if (E[J] >= P) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (E[J] >= P) continue; |
33 |
12 |
45 |
|
| 165 |
12 |
| K = J; |
| 166 |
12 |
| P = E[J]; |
| 167 |
|
| } |
| 168 |
16 |
▶ | if (K == I) continue; |
Branch: 1 branch
| Branch | True | False | Total |
| if (K == I) continue; |
5 |
11 |
16 |
|
| 169 |
11 |
| E[K] = E[I]; |
| 170 |
11 |
| E[I] = P; |
| 171 |
72 |
▶ | for ( J = 0; J < N; J++ ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for ( J = 0; J < N; J++ ) { |
61 |
11 |
72 |
|
| 172 |
61 |
| P = EV[ N*I+J ]; |
| 173 |
61 |
| EV[ N*I+J ] = EV[ N*K+J ]; |
| 174 |
61 |
| EV[ N*K+J ] = P; |
| 175 |
|
| } |
| 176 |
|
| } |
| 177 |
5 |
| } |