home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / octa21fb.zip / octave / SCRIPTS.ZIP / scripts.fat / control / zgscal.m < prev    next >
Text File  |  1999-12-24  |  5KB  |  145 lines
  1. ## Copyright (C) 1996,1998 Auburn University.  All Rights Reserved
  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, 59 Temple Place, Suite 330, Boston, MA 02111 USA. 
  18.  
  19. ## -*- texinfo -*-
  20. ## @deftypefn {Function File } { x =} zgscal (@var{f}, @var{z}, @var{n}, @var{m}, @var{p})
  21. ## Generalized conjugate gradient iteration to 
  22. ## solve zero-computation generalized eigenvalue problem balancing equation 
  23. ## @math{fx=z};
  24. ## called by @code{zgepbal}
  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. function x = zgscal (a, b, c, d, z, n, m, p)
  32.  
  33.   ## A. S. Hodel July 24 1992
  34.   ## Conversion to Octave R. Bruce Tenison July 3, 1994
  35.  
  36.   ## initialize parameters:
  37.   ## Givens rotations, diagonalized 2x2 block of F, gcg vector initialization
  38.  
  39.   nmp = n+m+p;
  40.   
  41.   ## x_0 = x_{-1} = 0, r_0 = z
  42.   x = zeros(nmp,1);
  43.   xk1 = x;
  44.   xk2 = x;
  45.   rk1 = z;
  46.   k = 0;
  47.  
  48.   ## construct balancing least squares problem
  49.   F = eye(nmp);
  50.   for kk=1:nmp
  51.     F(1:nmp,kk) = zgfmul(a,b,c,d,F(:,kk));
  52.   endfor
  53.  
  54.   [U,H,k1] = krylov(F,z,nmp,1e-12,1);
  55.   if(!is_sqr(H))
  56.     if(columns(H) != k1) 
  57.       error("zgscal(tzero): k1=%d, columns(H)=%d",k1,columns(H));
  58.     elseif(rows(H) != k1+1)
  59.       error("zgscal: k1=%d, rows(H) = %d",k1,rows(H));
  60.     elseif ( norm(H(k1+1,:)) > 1e-12*norm(H,"inf") )
  61.       zgscal_last_row_of_H = H(k1+1,:)
  62.       error("zgscal: last row of H nonzero (norm(H)=%e)",norm(H,"inf"))
  63.     endif
  64.     H = H(1:k1,1:k1);
  65.     U = U(:,1:k1);
  66.   endif
  67.  
  68.   ## tridiagonal H can still be rank deficient, so do permuted qr 
  69.   ## factorization
  70.   [qq,rr,pp] = qr(H);    # H = qq*rr*pp'
  71.   nn = rank(rr);
  72.   qq = qq(:,1:nn);
  73.   rr = rr(1:nn,:);            # rr may not be square, but "\" does least
  74.   xx = U*pp*(rr\qq'*(U'*z));  # squares solution, so this works
  75.   ## xx1 = pinv(F)*z;
  76.   ## zgscal_x_xx1_err = [xx,xx1,xx-xx1]
  77.   return;
  78.  
  79.   ## the rest of this is left from the original zgscal;
  80.   ## I've had some numerical problems with the GCG algorithm,
  81.   ## so for now I'm solving it with the krylov routine.
  82.  
  83.   ## initialize residual error norm
  84.   rnorm = norm(rk1,1);
  85.  
  86.   xnorm = 0;
  87.   fnorm = 1e-12 * norm([a,b;c,d],1);
  88.  
  89.   ## dummy defines for MATHTOOLS compiler
  90.   gamk2 = 0;      omega1 = 0;      ztmz2 = 0;
  91.  
  92.   ## do until small changes to x
  93.   len_x = length(x);
  94.   while ((k < 2*len_x) & (xnorm> 0.5) & (rnorm>fnorm))|(k == 0)
  95.     k = k+1;
  96.     
  97.     ## solve F_d z_{k-1} = r_{k-1}
  98.     zk1= zgfslv(n,m,p,rk1);
  99.  
  100.     ## Generalized CG iteration
  101.     ## gamk1 = (zk1'*F_d*zk1)/(zk1'*F*zk1);
  102.     ztMz1 = zk1'*rk1;
  103.     gamk1 = ztMz1/(zk1'*zgfmul(a,b,c,d,zk1));
  104.  
  105.     if(rem(k,len_x) == 1) omega = 1;
  106.     else                  omega = 1/(1-gamk1*ztMz1/(gamk2*omega1*ztmz2));
  107.     endif
  108.  
  109.     ## store x in xk2 to save space
  110.     xk2 = xk2 + omega*(gamk1*zk1 + xk1 - xk2);
  111.  
  112.     ## compute new residual error: rk = z - F xk, check end conditions
  113.     rk1 = z - zgfmul(a,b,c,d,xk2);
  114.     rnorm = norm(rk1);
  115.     xnorm = max(abs(xk1 - xk2));
  116.  
  117.     ## printf("zgscal: k=%d, gamk1=%e, gamk2=%e, \nztMz1=%e ztmz2=%e\n", ...
  118.     ##   k,gamk1, gamk2, ztMz1, ztmz2);
  119.     ## xk2_1_zk1 = [xk2 xk1 zk1]
  120.     ## ABCD = [a,b;c,d]
  121.     ## prompt
  122.  
  123.     ## get ready for next iteration
  124.     gamk2 = gamk1;
  125.     omega1 = omega;
  126.     ztmz2 = ztMz1;
  127.     [xk1,xk2] = swap(xk1,xk2);
  128.   endwhile
  129.   x = xk2;
  130.  
  131.   ## check convergence
  132.   if (xnorm> 0.5 & rnorm>fnorm) 
  133.     warning("zgscal(tzero): GCG iteration failed; solving with pinv");
  134.  
  135.     ## perform brute force least squares; construct F
  136.     Am = eye(nmp);
  137.     for ii=1:nmp
  138.       Am(:,ii) = zgfmul(a,b,c,d,Am(:,ii));
  139.     endfor
  140.  
  141.     ## now solve with qr factorization
  142.     x = pinv(Am)*z;
  143.   endif
  144. endfunction
  145.