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