Login or Register to Ask a Question and Join Our Community

Linux and UNIX Man Pages

Linux & Unix Commands - Search Man Pages

math::vector::real::kdtree(3pm) [debian man page]

Math::Vector::Real::kdTree(3pm) 			User Contributed Perl Documentation			   Math::Vector::Real::kdTree(3pm)

NAME

       Math::Vector::Real::kdTree - kd-Tree implementation on top of Math::Vector::Real

SYNOPSIS

	 use Math::Vector::Real::kdTree;

	 use Math::Vector::Real;
	 use Math::Vector::Real::Random;

	 my @v = map Math::Vector::Real->random_normal(4), 1..1000;

	 my $tree = Math::Vector::Real::kdTree->new(@v);

	 my $ix = $tree->find_nearest_neighbor(V(0, 0, 0, 0));

	 say "nearest neighbor is $ix, $v[$ix]";

DESCRIPTION

       This module implements a kd-Tree data structure in Perl and some related algorithms.

       The following methods are provided:

       $t = Math::Vector::Real::kdTree->new(@points)
	   Creates a new kdTree containing the gived points.

       $t->insert($p)
	   Inserts the given point into the kdTree.

       $s = $t->size
	   Returns the number of points inside the tree.

       $p = $t->at($ix)
	   Returns the point at the given index inside the tree.

       $t->move($ix, $p)
	   Moves the point at index $ix to the new given position readjusting the tree structure accordingly.

       ($ix, $d) = $t->find_nearest_neighbor($p, $max_d, $but_ix)
	   Find the nearest neighbor for the given point $p and returns its index and the distance between the two points (in scalar context the
	   index is returned).

	   If $max_d is defined, the search is limited to the points within that distance

	   If $but_ix is defined, the point with the given index is not considered.

       @ix = $t->find_nearest_neighbor_all_internal
	   Returns the index of the nearest neighbor for every point inside the tree.

	   It is equivalent to (though, internally, it uses a better algorithm):

	     @ix = map {
		       scalar $t->nearest_neighbor($t->at($_), undef, $_)
		   } 0..($t->size - 1);

       @ix = $t->find_in_ball($z, $d, $but)
       $n = $t->find_in_ball($z, $d, $but)
	   Finds the points inside the tree contained in the hypersphere with center $z and radius $d.

	   In scalar context returns the number of points found. In list context returns the indexes of the points.

	   If the extra argument $but is provided. The point with that index is ignored.

       @ix = $t->ordered_by_proximity
	   Returns the indexes of the points in an ordered where is likely that the indexes of near vectors are also in near positions in the
	   list.

SEE ALSO

       http://en.wikipedia.org/wiki/K-d_tree <http://en.wikipedia.org/wiki/K-d_tree>

       Math::Vector::Real

COPYRIGHT AND LICENSE

       Copyright (C) 2011, 2012 by Salvador FandiA~Xo <sfandino@yahoo.com>

       This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.12.3 or,
       at your option, any later version of Perl 5 you may have available.

perl v5.14.2							    2012-06-18					   Math::Vector::Real::kdTree(3pm)

Check Out this Related Man Page

puzawa(4rheolef)						    rheolef-6.1 						  puzawa(4rheolef)

NAME

       puzawa -- Uzawa algorithm.

SYNOPSIS

	   template <class Matrix, class Vector, class Preconditioner, class Real>
	   int puzawa (const Matrix &A, Vector &x, const Vector &b, const Preconditioner &M,
	     int &max_iter, Real &tol, const Real& rho, odiststream *p_derr=0);

EXAMPLE

       The simplest call to 'puzawa' has the folling form:

	   size_t max_iter = 100;
	   double tol = 1e-7;
	   int status = puzawa(A, x, b, EYE, max_iter, tol, 1.0, &derr);

DESCRIPTION

       puzawa solves the linear system A*x=b using the Uzawa method. The Uzawa method is a descent method in the direction opposite to the  gradi-
       ent, with a constant step length 'rho'. The convergence is assured when the step length 'rho' is small enough.  If matrix  A  is  symmetric
       positive definite, please uses 'pcg' that computes automatically the optimal descdnt step length at each iteration.

       The return value indicates convergence within max_iter (input) iterations(0), or no convergence within max_iter iterations(1).  Upon suc-
       cessful return, output arguments have the following values:

       x      approximate solution to Ax = b

       max_iter
	      the number of iterations performed before the tolerance was reached

       tol    the residual after the final iteration

IMPLEMENTATION

       template < class Matrix, class Vector, class Preconditioner, class Real, class Size>
       int puzawa(const Matrix &A, Vector &x, const Vector &Mb, const Preconditioner &M,
	   Size &max_iter, Real &tol, const Real& rho,
	   odiststream *p_derr, std::string label)
       {
	   Vector b = M.solve(Mb);
	   Real norm2_b = dot(Mb,b);
	   Real norm2_r = norm2_b;
	   if (norm2_b == Real(0)) norm2_b = 1;
	   if (p_derr) (*p_derr) << "[" << label << "] #iteration residue" << std::endl;
	   for (Size n = 0; n <= max_iter; n++) {
	       Vector Mr = A*x - Mb;
	       Vector r = M.solve(Mr);
	       norm2_r = dot(Mr, r);
	       if (p_derr) (*p_derr) << "[" << label << "] " << n << " " << sqrt(norm2_r/norm2_b) << std::endl;
	       if (norm2_r <= sqr(tol)*norm2_b) {
		 tol = sqrt(norm2_r/norm2_b);
		 max_iter = n;
		 return 0;
	       }
	       x  -= rho*r;
	   }
	   tol = sqrt(norm2_r/norm2_b);
	   return 1;
       }

rheolef-6.1							    rheolef-6.1 						  puzawa(4rheolef)
Man Page