|
3213
|
1 # Copyright (C) 1996,1998 A. Scottedward Hodel |
|
|
2 # |
|
|
3 # This file is part of Octave. |
|
|
4 # |
|
|
5 # Octave is free software; you can redistribute it and/or modify it |
|
|
6 # under the terms of the GNU General Public License as published by the |
|
|
7 # Free Software Foundation; either version 2, or (at your option) any |
|
|
8 # later version. |
|
|
9 # |
|
|
10 # Octave is distributed in the hope that it will be useful, but WITHOUT |
|
|
11 # ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
|
12 # FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
|
13 # for more details. |
|
|
14 # |
|
|
15 # You should have received a copy of the GNU General Public License |
|
|
16 # along with Octave; see the file COPYING. If not, write to the Free |
|
|
17 # Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. |
|
|
18 |
|
|
19 function x = zgscal(a,b,c,d,z,n,m,p) |
|
|
20 # x = zgscal(f,z,n,m,p) generalized conjugate gradient iteration to |
|
|
21 # solve zero-computation generalized eigenvalue problem balancing equation |
|
|
22 # fx=z |
|
|
23 # called by zgepbal |
|
|
24 # |
|
|
25 # References: |
|
|
26 # ZGEP: Hodel, "Computation of Zeros with Balancing," 1992, submitted to LAA |
|
|
27 # Generalized CG: Golub and Van Loan, "Matrix Computations, 2nd ed" 1989 |
|
|
28 |
|
|
29 # A. S. Hodel July 24 1992 |
|
|
30 # Conversion to Octave R. Bruce Tenison July 3, 1994 |
|
3236
|
31 |
|
3213
|
32 |
|
|
33 #************************************************************************** |
|
|
34 #initialize parameters: |
|
|
35 # Givens rotations, diagonalized 2x2 block of F, gcg vector initialization |
|
|
36 #************************************************************************** |
|
|
37 nmp = n+m+p; |
|
|
38 |
|
|
39 #x_0 = x_{-1} = 0, r_0 = z |
|
|
40 x = zeros(nmp,1); |
|
|
41 xk1 = x; |
|
|
42 xk2 = x; |
|
|
43 rk1 = z; |
|
|
44 k = 0; |
|
|
45 |
|
3236
|
46 # construct balancing least squares problem |
|
|
47 F = eye(nmp); |
|
|
48 for kk=1:nmp |
|
|
49 F(1:nmp,kk) = zgfmul(a,b,c,d,F(:,kk)); |
|
|
50 endfor |
|
|
51 |
|
3240
|
52 [U,H,k1] = krylov(F,z,nmp,1e-12,1); |
|
3236
|
53 if(!is_square(H)) |
|
|
54 if(columns(H) != k1) |
|
|
55 error("zgscal(tzero): k1=%d, columns(H)=%d",k1,columns(H)); |
|
|
56 elseif(rows(H) != k1+1) |
|
|
57 error("zgscal: k1=%d, rows(H) = %d",k1,rows(H)); |
|
|
58 elseif ( norm(H(k1+1,:)) > 1e-12*norm(H,"inf") ) |
|
|
59 zgscal_last_row_of_H = H(k1+1,:) |
|
|
60 error("zgscal: last row of H nonzero (norm(H)=%e)",norm(H,"inf")) |
|
|
61 endif |
|
|
62 H = H(1:k1,1:k1); |
|
|
63 U = U(:,1:k1); |
|
|
64 endif |
|
|
65 |
|
|
66 # tridiagonal H can still be rank deficient, so do permuted qr |
|
|
67 # factorization |
|
|
68 [qq,rr,pp] = qr(H); # H = qq*rr*pp' |
|
|
69 nn = rank(rr); |
|
|
70 qq = qq(:,1:nn); |
|
|
71 rr = rr(1:nn,:); # rr may not be square, but "\" does least |
|
|
72 xx = U*pp*(rr\qq'*(U'*z)); # squares solution, so this works |
|
|
73 #xx1 = pinv(F)*z; |
|
|
74 #zgscal_x_xx1_err = [xx,xx1,xx-xx1] |
|
|
75 return; |
|
|
76 |
|
|
77 # the rest of this is left from the original zgscal; |
|
|
78 # I've had some numerical problems with the GCG algorithm, |
|
|
79 # so for now I'm solving it with the krylov routine. |
|
|
80 |
|
3213
|
81 #initialize residual error norm |
|
|
82 rnorm = norm(rk1,1); |
|
|
83 |
|
|
84 xnorm = 0; |
|
|
85 fnorm = 1e-12 * norm([a,b;c,d],1); |
|
|
86 |
|
|
87 # dummy defines for MATHTOOLS compiler |
|
|
88 gamk2 = 0; omega1 = 0; ztmz2 = 0; |
|
|
89 |
|
|
90 #do until small changes to x |
|
|
91 len_x = length(x); |
|
|
92 while ((k < 2*len_x) & (xnorm> 0.5) & (rnorm>fnorm))|(k == 0) |
|
|
93 k = k+1; |
|
|
94 |
|
|
95 # solve F_d z_{k-1} = r_{k-1} |
|
|
96 zk1= zgfslv(n,m,p,rk1); |
|
|
97 |
|
|
98 # Generalized CG iteration |
|
|
99 # gamk1 = (zk1'*F_d*zk1)/(zk1'*F*zk1); |
|
|
100 ztMz1 = zk1'*rk1; |
|
|
101 gamk1 = ztMz1/(zk1'*zgfmul(a,b,c,d,zk1)); |
|
|
102 |
|
|
103 if(rem(k,len_x) == 1) omega = 1; |
|
|
104 else omega = 1/(1-gamk1*ztMz1/(gamk2*omega1*ztmz2)); |
|
|
105 endif |
|
|
106 |
|
|
107 # store x in xk2 to save space |
|
|
108 xk2 = xk2 + omega*(gamk1*zk1 + xk1 - xk2); |
|
|
109 |
|
|
110 # compute new residual error: rk = z - F xk, check end conditions |
|
|
111 rk1 = z - zgfmul(a,b,c,d,xk2); |
|
|
112 rnorm = norm(rk1); |
|
|
113 xnorm = max(abs(xk1 - xk2)); |
|
|
114 |
|
|
115 #printf("zgscal: k=%d, gamk1=%e, gamk2=%e, \nztMz1=%e ztmz2=%e\n", ... |
|
|
116 # k,gamk1, gamk2, ztMz1, ztmz2); |
|
|
117 # xk2_1_zk1 = [xk2 xk1 zk1] |
|
|
118 # ABCD = [a,b;c,d] |
|
|
119 # prompt |
|
|
120 |
|
|
121 # get ready for next iteration |
|
|
122 gamk2 = gamk1; |
|
|
123 omega1 = omega; |
|
|
124 ztmz2 = ztMz1; |
|
|
125 [xk1,xk2] = swap(xk1,xk2); |
|
|
126 endwhile |
|
|
127 x = xk2; |
|
|
128 |
|
|
129 # check convergence |
|
|
130 if (xnorm> 0.5 & rnorm>fnorm) |
|
|
131 warning("zgscal(tzero): GCG iteration failed; solving with pinv"); |
|
|
132 |
|
|
133 # perform brute force least squares; construct F |
|
|
134 Am = eye(nmp); |
|
|
135 for ii=1:nmp |
|
|
136 Am(:,ii) = zgfmul(a,b,c,d,Am(:,ii)); |
|
|
137 endfor |
|
|
138 |
|
|
139 # now solve with qr factorization |
|
|
140 x = pinv(Am)*z; |
|
|
141 endif |
|
|
142 endfunction |
