1 | /**************************************** |
---|
2 | * Computer Algebra System SINGULAR * |
---|
3 | ****************************************/ |
---|
4 | /* $Id: eigenval.cc,v 1.5 2002-01-19 14:48:14 obachman Exp $ */ |
---|
5 | /* |
---|
6 | * ABSTRACT: eigenvalues of constant square matrices |
---|
7 | */ |
---|
8 | |
---|
9 | #include "mod2.h" |
---|
10 | |
---|
11 | #ifdef HAVE_EIGENVAL |
---|
12 | |
---|
13 | #include "tok.h" |
---|
14 | #include "febase.h" |
---|
15 | #include "numbers.h" |
---|
16 | #include "polys.h" |
---|
17 | #include "ideals.h" |
---|
18 | #include "matpol.h" |
---|
19 | #include "clapsing.h" |
---|
20 | |
---|
21 | matrix swap(matrix M,int i,int j) |
---|
22 | { |
---|
23 | if(i==j) |
---|
24 | return M; |
---|
25 | poly p; |
---|
26 | for(int k=1;k<=MATROWS(M);k++) |
---|
27 | { |
---|
28 | p=MATELEM(M,i,k); |
---|
29 | MATELEM(M,i,k)=MATELEM(M,j,k); |
---|
30 | MATELEM(M,j,k)=p; |
---|
31 | } |
---|
32 | for(int k=1;k<=MATCOLS(M);k++) |
---|
33 | { |
---|
34 | p=MATELEM(M,k,i); |
---|
35 | MATELEM(M,k,i)=MATELEM(M,k,j); |
---|
36 | MATELEM(M,k,j)=p; |
---|
37 | } |
---|
38 | return(M); |
---|
39 | } |
---|
40 | |
---|
41 | matrix rowelim(matrix M,int i, int j, int k) |
---|
42 | { |
---|
43 | if(MATELEM(M,i,k)==NULL||MATELEM(M,j,k)==NULL) |
---|
44 | return M; |
---|
45 | number n=nDiv(pGetCoeff(MATELEM(M,i,k)), |
---|
46 | pGetCoeff(MATELEM(M,j,k))); |
---|
47 | for(int l=1;l<=MATCOLS(M);l++) |
---|
48 | { |
---|
49 | MATELEM(M,i,l)=pSub(MATELEM(M,i,l),pMult_nn(pCopy(MATELEM(M,j,l)),n)); |
---|
50 | } |
---|
51 | for(int l=1;l<=MATROWS(M);l++) |
---|
52 | { |
---|
53 | MATELEM(M,l,j)=pAdd(MATELEM(M,l,j),pMult_nn(pCopy(MATELEM(M,l,i)),n)); |
---|
54 | } |
---|
55 | nDelete(&n); |
---|
56 | return M; |
---|
57 | } |
---|
58 | |
---|
59 | matrix colelim(matrix M,int i, int j, int k) |
---|
60 | { |
---|
61 | if(MATELEM(M,k,i)==NULL||MATELEM(M,k,j)==NULL) |
---|
62 | return M; |
---|
63 | number n=nDiv(pGetCoeff(MATELEM(M,k,i)), |
---|
64 | pGetCoeff(MATELEM(M,k,j))); |
---|
65 | for(int l=1;l<=MATROWS(M);l++) |
---|
66 | { |
---|
67 | MATELEM(M,l,i)=pSub(MATELEM(M,l,i),pMult_nn(pCopy(MATELEM(M,l,j)),n)); |
---|
68 | } |
---|
69 | for(int l=1;l<=MATCOLS(M);l++) |
---|
70 | { |
---|
71 | MATELEM(M,j,l)=pAdd(MATELEM(M,j,l),pMult_nn(pCopy(MATELEM(M,i,l)),n)); |
---|
72 | } |
---|
73 | nDelete(&n); |
---|
74 | return M; |
---|
75 | } |
---|
76 | |
---|
77 | matrix tridiag(matrix M) |
---|
78 | { |
---|
79 | int n=MATCOLS(M); |
---|
80 | for(int k=1;k<=n-2;k++) |
---|
81 | { |
---|
82 | int j=k+1; |
---|
83 | while(j<=n&&MATELEM(M,j,k)==NULL) j++; |
---|
84 | if(j<=n) |
---|
85 | { |
---|
86 | for(int i=j+1;i<=n;i++) |
---|
87 | { |
---|
88 | M=rowelim(M,i,j,k); |
---|
89 | } |
---|
90 | M=swap(M,j,k+1); |
---|
91 | } |
---|
92 | j=k+1; |
---|
93 | while(j<=n&&MATELEM(M,k,j)==NULL) j++; |
---|
94 | if(j<=n) |
---|
95 | { |
---|
96 | for(int i=j+1;i<=n;i++) |
---|
97 | { |
---|
98 | M=colelim(M,i,j,k); |
---|
99 | } |
---|
100 | M=swap(M,j,k+1); |
---|
101 | } |
---|
102 | } |
---|
103 | return(M); |
---|
104 | } |
---|
105 | |
---|
106 | lists addval(lists l,poly e0,int m0) |
---|
107 | { |
---|
108 | ideal ee=(ideal)l->m[0].data; |
---|
109 | intvec *mm=(intvec*)l->m[1].data; |
---|
110 | int n=0; |
---|
111 | if(ee!=NULL) |
---|
112 | n=IDELEMS(ee); |
---|
113 | for(int i=n-1;i>=0;i--) |
---|
114 | { |
---|
115 | if(pEqualPolys(ee->m[i],e0)) |
---|
116 | { |
---|
117 | (*mm)[i]+=m0; |
---|
118 | return l; |
---|
119 | } |
---|
120 | } |
---|
121 | ideal e=idInit(n+1,1); |
---|
122 | for(int i=n-1;i>=0;i--) |
---|
123 | { |
---|
124 | e->m[i]=ee->m[i]; |
---|
125 | ee->m[i]=NULL; |
---|
126 | } |
---|
127 | e->m[n]=e0; |
---|
128 | l->m[0].data=e; |
---|
129 | if(ee!=NULL) |
---|
130 | idDelete(&ee); |
---|
131 | mm->resize(n+1); |
---|
132 | (*mm)[n]=m0; |
---|
133 | return l; |
---|
134 | } |
---|
135 | |
---|
136 | lists sortval(lists l) |
---|
137 | { |
---|
138 | ideal ee=(ideal)l->m[0].data; |
---|
139 | intvec *mm=(intvec*)l->m[1].data; |
---|
140 | int n=IDELEMS(ee); |
---|
141 | for(int i=n-1;i>=1;i--) |
---|
142 | for(int j=i-1;j>=0;j--) |
---|
143 | if(nGreater(pGetCoeff(ee->m[j]),pGetCoeff(ee->m[i]))) |
---|
144 | { |
---|
145 | poly e=ee->m[i]; |
---|
146 | ee->m[i]=ee->m[j]; |
---|
147 | ee->m[j]=e; |
---|
148 | int m=(*mm)[i]; |
---|
149 | (*mm)[i]=(*mm)[j]; |
---|
150 | (*mm)[j]=m; |
---|
151 | } |
---|
152 | return l; |
---|
153 | } |
---|
154 | |
---|
155 | lists eigenval(matrix M) |
---|
156 | { |
---|
157 | M=tridiag(M); |
---|
158 | int n=MATCOLS(M); |
---|
159 | lists l=(lists)omAllocBin(slists_bin); |
---|
160 | l->Init(2); |
---|
161 | l->m[0].rtyp=IDEAL_CMD; |
---|
162 | l->m[0].data=NULL; |
---|
163 | l->m[1].rtyp=INTVEC_CMD; |
---|
164 | l->m[1].data=new intvec; |
---|
165 | int j=1; |
---|
166 | while(j<=n) |
---|
167 | { |
---|
168 | while(j<n&&(MATELEM(M,j,j+1)==NULL||MATELEM(M,j+1,j)==NULL)||j==n) |
---|
169 | { |
---|
170 | l=addval(l,MATELEM(M,j,j),1); |
---|
171 | MATELEM(M,j,j)=NULL; |
---|
172 | j++; |
---|
173 | } |
---|
174 | if(j<n) |
---|
175 | { |
---|
176 | poly t=pOne(); |
---|
177 | pSetExp(t,1,1); |
---|
178 | pSetm(t); |
---|
179 | poly d0=pSub(MATELEM(M,j,j),t); |
---|
180 | MATELEM(M,j,j)=NULL; |
---|
181 | j++; |
---|
182 | poly d1=pOne(); |
---|
183 | poly d2=NULL; |
---|
184 | while(j<=n&&MATELEM(M,j,j-1)!=NULL&&MATELEM(M,j-1,j)!=NULL) |
---|
185 | { |
---|
186 | d2=d1; |
---|
187 | d1=pCopy(d0); |
---|
188 | poly t=pOne(); |
---|
189 | pSetExp(t,1,1); |
---|
190 | pSetm(t); |
---|
191 | d0=pSub(pMult(d0,pSub(MATELEM(M,j,j),t)), |
---|
192 | pMult(pMult(d2,MATELEM(M,j-1,j)),MATELEM(M,j,j-1))); |
---|
193 | MATELEM(M,j,j)=NULL; |
---|
194 | MATELEM(M,j-1,j)=NULL; |
---|
195 | MATELEM(M,j,j-1)=NULL; |
---|
196 | j++; |
---|
197 | } |
---|
198 | pDelete(&d1); |
---|
199 | intvec *m0=NULL; |
---|
200 | #ifdef HAVE_FACTORY |
---|
201 | ideal e0=singclap_factorize(d0,&m0,0); |
---|
202 | #else |
---|
203 | ideal e0 = NULL; |
---|
204 | #endif |
---|
205 | pDelete(&d0); |
---|
206 | for(int i=IDELEMS(e0)-1;i>=1;i--) |
---|
207 | { |
---|
208 | poly p=e0->m[i]; |
---|
209 | e0->m[i]=NULL; |
---|
210 | poly p0,p1; |
---|
211 | poly pp=p; |
---|
212 | while(pp!=NULL&&pGetExp(pp,1)<=1) |
---|
213 | { |
---|
214 | if(pGetExp(pp,1)==0) |
---|
215 | p0=pp; |
---|
216 | else |
---|
217 | if(pGetExp(pp,1)==1) |
---|
218 | p1=pp; |
---|
219 | pp=pNext(pp); |
---|
220 | } |
---|
221 | if(pp==NULL) |
---|
222 | { |
---|
223 | pp=p; |
---|
224 | p=pNSet(nNeg(nDiv(pGetCoeff(p0),pGetCoeff(p1)))); |
---|
225 | pDelete(&pp); |
---|
226 | } |
---|
227 | else |
---|
228 | { |
---|
229 | p=pMult_nn(p,pGetCoeff(e0->m[0])); |
---|
230 | } |
---|
231 | l=addval(l,p,(*m0)[i]); |
---|
232 | } |
---|
233 | delete m0; |
---|
234 | idDelete(&e0); |
---|
235 | } |
---|
236 | } |
---|
237 | idDelete((ideal*)&M); |
---|
238 | return sortval(l); |
---|
239 | } |
---|
240 | |
---|
241 | BOOLEAN tridiag(leftv res,leftv h) |
---|
242 | { |
---|
243 | if((h!=NULL) && (h->Typ()==MATRIX_CMD)) |
---|
244 | { |
---|
245 | matrix M=(matrix)h->Data(); |
---|
246 | if(MATCOLS(M)!=MATROWS(M)) |
---|
247 | { |
---|
248 | WerrorS("square matrix expected"); |
---|
249 | } |
---|
250 | res->rtyp=MATRIX_CMD; |
---|
251 | res->data=(void*)tridiag(mpCopy(M)); |
---|
252 | return FALSE; |
---|
253 | } |
---|
254 | WerrorS("<matrix> expected"); |
---|
255 | return TRUE; |
---|
256 | } |
---|
257 | |
---|
258 | BOOLEAN eigenval(leftv res,leftv h) |
---|
259 | { |
---|
260 | if((h!=NULL) && (h->Typ()==MATRIX_CMD)) |
---|
261 | { |
---|
262 | matrix M=(matrix)h->Data(); |
---|
263 | if(MATCOLS(M)!=MATROWS(M)) |
---|
264 | { |
---|
265 | WerrorS("square matrix expected"); |
---|
266 | } |
---|
267 | res->rtyp=LIST_CMD; |
---|
268 | res->data=(void*)eigenval(mpCopy(M)); |
---|
269 | return FALSE; |
---|
270 | } |
---|
271 | WerrorS("<matrix> expected"); |
---|
272 | return TRUE; |
---|
273 | } |
---|
274 | #endif |
---|