lib/PDL/MatrixOps/eigens.c

filter: Statementstmt 100% 84 / 84 Branchbran 97.8% 45 / 46 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 99.2% 129 / 130 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« lib/PDL/MatrixOps/svd.c ↑ Summary .pptest/sub/Makefile.PL »
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for ( I=0; I<N; I++ ) { 21 5 26
75 132 ▶ for ( J=0; J<N; J++ ) {
Branch: 1 branch
BranchTrueFalseTotal
for ( J=0; J<N; J++ ) { 111 21 132
76 111 ▶ if ( I != J ) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for ( L=0; L<N-1; L++ ) { 459 146 605
95 1753 ▶ for ( M=L+1; M<N; M++ ) {
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
IM=(I > M) ? M+IQ : I+MQ; 228 408 636
123 636 ▶ IL=(I >= L) ? L+IQ : I+LQ;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
} 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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
for ( J = II; J < N; J++ ) { 45 16 61
164 45 ▶ if (E[J] >= P) continue;
Branch: 1 branch
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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
BranchTrueFalseTotal
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 }
« lib/PDL/MatrixOps/svd.c ↑ Summary .pptest/sub/Makefile.PL »