IETL Concepts and Interfaces

Here we define the requirements on the types necesary to use the IETL algorithms:

The vector space concept

Linear eigensolvers mathematically rely on the concept of a vectorspace, which also defines the necessary functionality for the IETL. Going beyond the ITL we expand on the concept of a vectorspace and find the necessity to require a vector space class to be passed to the algorithms. Let
then the following types have to be defined:

Type
Documentation
ietl::vectorspace_traits<VS>::vector_type
the type of vectors in the vector space
ietl::vectorspace_traits<VS>::scalar_type
the type of scalars in the vector space
ietl::vectorspace_traits<VS>::magnitude_type
a scalar type appropriate for storing norms, usually the same as scalar_type for real types, or the corresponding real type for complex types.
ietl::vectorspace_traits<VS>::size_type
an integral type large enough to store the dimension of the vector space

and the following expression have to be defined for the vector space object:

Expression
return type
Documentation
new_vector(vs)
ietl::vectorspace_traits<VS>::vector_type creates a new vector of the vector space
vec_dimension(vs)
ietl::vectorspace_traits<VS>::size_type
returns the dimension of the vector space
project(x,vs)
void
projects the vector x into the vector space.

The new_vector function is necessary since we do not know the types and number of arguments needed for the constructor of a vector. The ITL assumes there is a constructor taking only the vector size as argument but this is insufficient in cases where more than the size is needed in the constructor, such as:
The project function is required if the actual vector space is a subspace of the representation space. E.g. if special boundary conditions are imposed on an array.

For the most common case, where the vector models the concept of an STL Container we provide two model implementations: vectorspace and wrapper_vectorspace.

Requirements on the matrix

Iterative algorithms require the matrix (linear operator) of which eigenvalues and eigenvectors are to be calculated only in the form of matrix-vector products. Hence only a single function is required. Let
then the following expression needs to be defined

Expression
return type
Documentation
ietl::mult(a,x,y)
void calculates the matrix-vector product y=a*x

For all uBlas matrix types, the ietl::mult function with boost::numeric:ublas::vector as vector type is implemented in the header ietl/interface/ublas.h .

Requirements on the vector

The vector type needs to fulfill the following requirements.
Then the following expressions need to be defined for all IETL algorithms.

Expression
return type
Documentation
ietl::generate(x,g)
void fills the vector x with numbers from the generator g. For a standard container this can be implemented as std::generate(x.begin(),x.end(),g);
std::swap(x,y)
void
swaps the two vectors x and y
ietl::dot(x,y)
S
calculates the scalar product of the two vectors x and y.
ietl::two_norm(x)
M
calculates the 2-norm of the vector x. This is equivalent to sqrt(ietl::dot(x,x)).
ietl::copy(x,y)
void
a deep copy y = x. Modifications of x after the call are not allowed to modify y.
y = x
const V&
a (possibly shallow) copy
x *= t
const V&

x /= t
const V&

x += y
const V&

x += t*y
const V&

x -= t*y
const V&

x = t*y
const V&


The necessary functions are implemented in the header ietl/interface/ublas.h for ublas vectors, and in ietl/interface/blitz.h for Blitz++ arrays.

Requirements on the standard iteration control object

Iterative algorithms run until the desired accuracy is reached. To control the termination of the iteration, the IETL algorithms take an iteration control object. Let it be the iteration control object, lambda the best estimate for the eigenvalue and residual be the residual ||A v - lambda v|| then the following expressions need to be defined:

Expression
return type
Documentation
++it
void is called at the start of a new iteration
it.finished(residual, lambda)
bool
returns true if the desired accuracy is reached and the iteration can be terminated, returns false otherwise. residual and lambda are of the magnitude_type and are the residual and and latest estimate of the eigenvalue respectively
A model implementation basic_iteration is provided in ietl/iteration.h.

Some algorithms require more complex iteration control objects. They will be discussed with the algorithms.

Requirements on the Lanczos iteration control object

Iterative algorithms run until the desired accuracy is reached. To control the termination of the iteration, the IETL algorithms take an iteration control object. Let it be the iteration control object, lambda the best estimate for the eigenvalue and residual be the residual ||A v - lambda v|| then the following expressions need to be defined:

Expression
return type
Documentation
++it
void is called at the start of a new iteration
it.finished(tmatrix)
bool
returns true if the desired accuracy is reached and the iteration can be terminated, returns false otherwise. The T-matrix of the Lanczos iterations is passed as argument.

Model implementation are provided in ietl/iteration.h.

Some algorithms require more complex iteration control objects. They will be discussed with the algorithms.



copyright 2002-2004 by Matthias Troyer and Prakash Dayal