diff scripts/sparse/pcg.m @ 5838:376e02b2ce70

[project @ 2006-06-01 20:23:53 by jwe]
author jwe
date Thu, 01 Jun 2006 20:23:54 +0000
parents 55404f3b0da1
children 2c85044aa63f
line wrap: on
line diff
--- a/scripts/sparse/pcg.m
+++ b/scripts/sparse/pcg.m
@@ -18,20 +18,20 @@
 ## 02110-1301, USA.
 
 ## -*- texinfo -*-
-## @deftypefn {Function File} {@var{x} =} pcg (@var{A}, @var{b}, @var{tol}, @var{maxit}, @var{M}, @var{x0}, @dots{})
+## @deftypefn {Function File} {@var{x} =} pcg (@var{a}, @var{b}, @var{tol}, @var{maxit}, @var{m}, @var{x0}, @dots{})
 ## @deftypefnx {Function File} {[@var{x}, @var{flag}, @var{relres}, @var{iter}, @var{resvec}, @var{eigest}] =} pcg (@dots{})
 ##
-## Solves the linear system of equations @code{@var{A} * @var{x} =
+## Solves the linear system of equations @code{@var{a} * @var{x} =
 ## @var{b}} by means of the  Preconditioned Conjugate Gradient iterative
 ## method. The input arguments are
 ##
 ## @itemize
 ## @item
-## @var{A} can be either a square (preferably sparse) matrix or a
+## @var{a} can be either a square (preferably sparse) matrix or a
 ## function handle, inline function or string containing the name
-## of a function which computes @code{@var{A} * @var{x}}. In principle
-## @var{A} should be symmetric and positive definite; if @code{pcg}
-## finds @var{A} to not be positive definite, you will get a warning
+## of a function which computes @code{@var{a} * @var{x}}. In principle
+## @var{a} should be symmetric and positive definite; if @code{pcg}
+## finds @var{a} to not be positive definite, you will get a warning
 ## message and the @var{flag} output parameter will be set.
 ## 
 ## @item
@@ -39,8 +39,8 @@
 ## 
 ## @item
 ## @var{tol} is the required relative tolerance for the residual error,
-## @code{@var{b} - @var{A} * @var{x}}. The iteration stops if @code{norm
-## (@var{b} - @var{A} * @var{x}) <= @var{tol} * norm (@var{b} - @var{A} *
+## @code{@var{b} - @var{a} * @var{x}}. The iteration stops if @code{norm
+## (@var{b} - @var{a} * @var{x}) <= @var{tol} * norm (@var{b} - @var{a} *
 ## @var{x0})}. If @var{tol} is empty or is omitted, the function sets
 ## @code{@var{tol} = 1e-6} by default.
 ## 
@@ -50,15 +50,15 @@
 ## arguments, a default value equal to 20 is used.
 ## 
 ## @item
-## @var{M} is the (left) preconditioning matrix, so that the iteration is
+## @var{m} is the (left) preconditioning matrix, so that the iteration is
 ## (theoretically) equivalent to solving by @code{pcg} @code{@var{P} *
-## @var{x} = @var{M} \ @var{b}}, with @code{@var{P} = @var{M} \ @var{A}}.
+## @var{x} = @var{m} \ @var{b}}, with @code{@var{P} = @var{m} \ @var{a}}.
 ## Note that a proper choice of the preconditioner may dramatically
 ## improve the overall performance of the method. Instead of matrix
-## @var{M}, the user may pass a function which returns the results of 
-## applying the inverse of @var{M} to a vector (usually this is the
+## @var{m}, the user may pass a function which returns the results of 
+## applying the inverse of @var{m} to a vector (usually this is the
 ## preferred way of using the preconditioner). If @code{[]} is supplied
-## for @var{M}, or @var{M} is omitted, no preconditioning is applied.
+## for @var{m}, or @var{m} is omitted, no preconditioning is applied.
 ## 
 ## @item
 ## @var{x0} is the initial guess. If @var{x0} is empty or omitted, the 
@@ -66,14 +66,14 @@
 ## @end itemize
 ## 
 ## The arguments which follow @var{x0} are treated as parameters, and
-## passed in a proper way to any of the functions (@var{A} or @var{M})
+## passed in a proper way to any of the functions (@var{a} or @var{m})
 ## which are passed to @code{pcg}. See the examples below for further
 ## details. The output arguments are
 ##
 ## @itemize
 ## @item
 ## @var{x} is the computed approximation to the solution of
-## @code{@var{A} * @var{x} = @var{b}}.
+## @code{@var{a} * @var{x} = @var{b}}.
 ## 
 ## @item
 ## @var{flag} reports on the convergence. @code{@var{flag} = 0} means
@@ -95,23 +95,23 @@
 ## @code{@var{resvec} (i,2)} is the preconditioned residual norm,
 ## after the (@var{i}-1)-th iteration, @code{@var{i} =
 ## 1,2,...@var{iter}+1}. The preconditioned residual norm is defined as
-## @code{norm (@var{r}) ^ 2 = @var{r}' * (@var{M} \ @var{r})} where
-## @code{@var{r} = @var{b} - @var{A} * @var{x}}, see also the
-## description of @var{M}. If @var{eigest} is not required, only
+## @code{norm (@var{r}) ^ 2 = @var{r}' * (@var{m} \ @var{r})} where
+## @code{@var{r} = @var{b} - @var{a} * @var{x}}, see also the
+## description of @var{m}. If @var{eigest} is not required, only
 ## @code{@var{resvec} (:,1)} is returned.
 ## 
 ## @item
 ## @var{eigest} returns the estimate for the smallest @code{@var{eigest}
 ## (1)} and largest @code{@var{eigest} (2)} eigenvalues of the
-## preconditioned matrix @code{@var{P} = @var{M} \ @var{A}}. In 
+## preconditioned matrix @code{@var{P} = @var{m} \ @var{a}}. In 
 ## particular, if no preconditioning is used, the extimates for the
-## extreme eigenvalues of @var{A} are returned. @code{@var{eigest} (1)}
+## extreme eigenvalues of @var{a} are returned. @code{@var{eigest} (1)}
 ## is an overestimate and @code{@var{eigest} (2)} is an underestimate, 
 ## so that @code{@var{eigest} (2) / @var{eigest} (1)} is a lower bound
 ## for @code{cond (@var{P}, 2)}, which nevertheless in the limit should
 ## theoretically be equal to the actual value of the condition number. 
 ## The method which computes @var{eigest} works only for symmetric positive
-## definite @var{A} and @var{M}, and the user is responsible for
+## definite @var{a} and @var{m}, and the user is responsible for
 ## verifying this assumption. 
 ## @end itemize
 ## 
@@ -133,7 +133,7 @@
 ## @end example
 ## 
 ## @sc{Example 2:} @code{pcg} with a function which computes
-## @code{@var{A} * @var{x}}
+## @code{@var{a} * @var{x}}
 ## 
 ## @example
 ## @group
@@ -147,7 +147,7 @@
 ## 
 ## @sc{Example 3:} Preconditioned iteration, with full diagnostics. The
 ## preconditioner (quite strange, because even the original matrix
-## @var{A} is trivial) is defined as a function
+## @var{a} is trivial) is defined as a function
 ## 
 ## @example
 ## @group
@@ -190,31 +190,12 @@
 ## @seealso{sparse, pcr}
 ## @end deftypefn
 
-## REVISION HISTORY
-##
-## 2004-05-21, Piotr Krzyzanowski:
-##	Added 4 demos and 4 tests
-##
-## 2004-05-18, Piotr Krzyzanowski:
-##	Warnings use warning() function now
-##
-## 2004-04-29, Piotr Krzyzanowski:
-##	Added more warning messages when FLAG is not required
-##
-## 2004-04-28, Piotr Krzyzanowski:
-## 	When eigest is required, resvec returns both the Euclidean and the
-##	preconditioned residual norm convergence history
-##
-## 2004-04-20, Piotr Krzyzanowski: 
-## 	Corrected eigenvalue estimator. Changed the tridiagonal matrix
-##	eigenvalue solver to regular eig
-## 
+## Author: Piotr Krzyzanowski <piotr.krzyzanowski@mimuw.edu.pl>
 
-function [x, flag, relres, iter, resvec, eigest] = ...
-		pcg( A, b, tol, maxit, M, x0, varargin )
+function [x, flag, relres, iter, resvec, eigest] = pcg (A, b, tol, maxit, M, x0, varargin)
 
-  if ((nargin < 6) || isempty(x0))
-    x = zeros(size(b));
+  if (nargin < 6 || isempty (x0))
+    x = zeros (size (b));
   else
     x = x0;
   endif
@@ -223,125 +204,123 @@
     M = [];
   endif
 
-  if ((nargin < 4) || isempty(maxit))
-    maxit = min(size(b,1),20);
+  if (nargin < 4 || isempty (maxit))
+    maxit = min (size (b, 1), 20);
   endif
 
-  maxit = maxit + 2;
+  maxit += 2;
 
-  if ((nargin < 3) || isempty(tol))
+  if (nargin < 3 || isempty (tol))
     tol = 1e-6;
   endif
 
   preconditioned_residual_out = false;
   if (nargout > 5)
-    T = zeros(maxit,maxit);
+    T = zeros (maxit, maxit);
     preconditioned_residual_out = true;
   endif
 
   matrix_positive_definite = true;	# assume A is positive definite
 
-  p = zeros(size(b)); 
+  p = zeros (size (b));
   oldtau = 1; 
-  if (isnumeric(A))			# is A a matrix?
+  if (isnumeric (A))			# is A a matrix?
     r = b - A*x; 
   else					# then A should be a function!
-    r = b - feval(A,x,varargin{:});
+    r = b - feval (A, x, varargin{:});
   endif
 
-  resvec(1,1) = norm(r); 
+  resvec(1,1) = norm (r);
   alpha = 1;
   iter = 2;
 
-  while ((resvec(iter-1,1) > tol*resvec(1,1)) && (iter < maxit))
-    if (isnumeric(M))		# is M a matrix?
-      if isempty(M)		# if M is empty, use no precond
+  while (resvec(iter-1,1) > tol*resvec(1,1) && iter < maxit)
+    if (isnumeric (M))		# is M a matrix?
+      if (isempty (M))		# if M is empty, use no precond
 	z = r;
       else			# otherwise, apply the precond
 	z = M \ r;
       endif
     else			# then M should be a function!
-      z = feval(M,r,varargin{:});
+      z = feval (M, r, varargin{:});
     endif
-    tau = z'*r; 
-    resvec(iter-1,2) = sqrt(tau);
-    beta = tau/oldtau;
+    tau = z' * r; 
+    resvec(iter-1,2) = sqrt (tau);
+    beta = tau / oldtau;
     oldtau = tau;
     p = z + beta*p;
-    if (isnumeric(A))		# is A a matrix?
-      w = A*p;
+    if (isnumeric (A))		# is A a matrix?
+      w = A * p;
     else			# then A should be a function!
-      w = feval(A,p,varargin{:});
+      w = feval (A, p, varargin{:});
     endif
     oldalpha = alpha; 		# needed only for eigest
-    alpha = tau/(p'*w);
+    alpha = tau / (p'*w);
     if (alpha <= 0.0) # negative matrix?
       matrix_positive_definite = false;
     endif
-    x = x + alpha*p;
-    r = r - alpha*w;
-    if ((nargout > 5) && (iter > 2))
+    x += alpha*p;
+    r -= alpha*w;
+    if (nargout > 5 && iter > 2)
       T(iter-1:iter, iter-1:iter) = T(iter-1:iter, iter-1:iter) + ...
 	  [1 sqrt(beta); sqrt(beta) beta]./oldalpha;
       ## EVS = eig(T(2:iter-1,2:iter-1));
       ## fprintf(stderr,"PCG condest: %g (iteration: %d)\n", max(EVS)/min(EVS),iter);
     endif
-    resvec(iter,1) = norm(r);
-    iter = iter + 1;
+    resvec(iter,1) = norm (r);
+    iter++;
   endwhile
 
   if (nargout > 5)
-    if (matrix_positive_definite )
+    if (matrix_positive_definite)
       if (iter > 3)
 	T = T(2:iter-2,2:iter-2);
 	l = eig(T);
-	eigest = [min(l) max(l)];
-	## fprintf(stderr, "PCG condest: %g\n",eigest(2)/eigest(1));
+	eigest = [min(l), max(l)];
+	## fprintf (stderr, "PCG condest: %g\n", eigest(2)/eigest(1));
       else
-	eigest = [NaN NaN];
-	warning("PCG: eigenvalue estimate failed: iteration converged too fast.");
+	eigest = [NaN, NaN];
+	warning ("PCG: eigenvalue estimate failed: iteration converged too fast.");
       endif
     else
-      eigest = [NaN NaN];
+      eigest = [NaN, NaN];
     endif
 
     ## apply the preconditioner once more and finish with the precond
     ## residual
-    if (isnumeric(M))		# is M a matrix?
-      if isempty(M)		# if M is empty, use no precond
+    if (isnumeric (M))		# is M a matrix?
+      if (isempty (M))		# if M is empty, use no precond
 	z = r;
       else			# otherwise, apply the precond
-	z = M\r;
+	z = M \ r;
       endif
     else			# then M should be a function!
-      z = feval(M,r,varargin{:});
+      z = feval (M, r, varargin{:});
     endif
-    resvec(iter-1,2) = sqrt(r'*z);
+    resvec(iter-1,2) = sqrt (r'*z);
   else
-    resvec = resvec(:,1);	
+    resvec = resvec(:,1);
   endif
 
   flag = 0;
   relres = resvec(iter-1,1)./resvec(1,1);
-  iter = iter - 2;
-  if (iter >= (maxit-2))
+  iter -= 2;
+  if (iter >= maxit-2)
     flag = 1;
     if (nargout < 2)
-      warning("PCG: maximum number of iterations (%d) reached\n", iter);
-      warning("The initial residual norm was reduced %g times.\n", 1.0/relres);
+      warning ("PCG: maximum number of iterations (%d) reached\n", iter);
+      warning ("The initial residual norm was reduced %g times.\n", 1.0/relres);
     endif
-  else
-    if (nargout < 2)
-      fprintf(stderr, "PCG: converged in %d iterations. ", iter);
-      fprintf(stderr, "The initial residual norm was reduced %g times.\n",...
-	      1.0/relres);
-    endif
+  elseif (nargout < 2)
+    fprintf (stderr, "PCG: converged in %d iterations. ", iter);
+    fprintf (stderr, "The initial residual norm was reduced %g times.\n",...
+	     1.0/relres);
   endif
 
-  if (!matrix_positive_definite)
+  if (! matrix_positive_definite)
     flag = 3;
     if (nargout < 2)
-      warning("PCG: matrix not positive definite?\n");
+      warning ("PCG: matrix not positive definite?\n");
     endif
   endif
 endfunction