It provides classes for statically- (known at compile time) and dynamically- (unknown at compile time) sized vectors and matrices and it delegates advanced functions (like SVD or multiplication of large matrices) to LAPACK and BLAS (this means you will need libblas and liblapack).
The library makes substantial internal use of templates to achieve run-time speed efficiency whilst retaining a clear programming syntax.
Why use this library?
using namespace TooN;
.
cvs -z3 -d:pserver:anoncvs@cvs.savannah.nongnu.org:/cvsroot/toon co TooN
The home page for the library with a version of this documentation is at:
http://mi.eng.cam.ac.uk/~er258/cvd/toon.html
The code will work as-is, and comes with a default configuration, which should work on any system.
On a unix system, ./configure && make install
will install TooN to the correct place. Note there is no code to be compiled, but the configure script performs some basic checks.
On non-unix systems, e.g. Windows and embedded systems, you may wish to configure the library manually. See Manual configuration..
#include <TooN/TooN.h>
Everything lives in the TooN
namespace.
Then, make sure the directory containing TooN is in your compiler's search path. If you use any decompositions, you will need to link against LAPACK, BLAS and any required support libraries. On a modern unix system, linking against LAPACK will do this automatically.
Vector<3> v1; //Create a static sized vector of size 3 Vector<> v2(4); //Create a dynamically sized vector of size 4 Vector<Dynamic> v2(4); //Create a dynamically sized vector of size 4
See also Can I have a precision other than double?.
Matrix<3> m; //A 3x3 matrix (statically sized) Matrix<3,2> m; //A 3x2 matrix (statically sized) Matrix<> m(5,6); //A 5x6 matrix (dynamically sized) Matrix<3,Dynamic> m(3,6); //A 3x6 matrix with a dynamic number of columns and static number of rows. Matrix<Dynamic,2> m(3,2); //A 2x3 matrix with a dynamic number of rows and static number of columns.
See also Can I have a precision other than double?.
template<int Size> void func(Vector<Size> v);
To write a function taking any type of vector by reference:
template<int Size, typename Base> void func(const Vector<Size, double, Base>& v);
=
. See also Why does assigning mismatched dynamic vectors fail?.These operators apply to vectors or matrices and scalars. The operator is applied to every element with the scalar.
*=, /=, *, /
Vector and vectors or matrices and matrices:
+, -, +=, -=
Dot product:
Vector * Vector
Matrix multiply:
Matrix * Matrix
Matrix multiplying a column vector:
Matrix * Vector
Row vector multiplying a matrix:
Vector * Matrix
3x3 Vector cross product:
Vector<3> ^ Vector<3>
All the functions listed below return slices. The slices are simply references to the original data and can be used as lvalues.
Getting the transpose of a matrix:
Matrix.T()
Accessing elements:
Vector[i] //get element i Matrix(i,j) //get element i,j Matrix[i] //get row i as a vector Matrix[i][j] //get element i,j
Turning vectors in to matrices:
Vector.as_row() //vector as a 1xN matrix Vector.as_col() //vector as a Nx1 matrix
Slicing with a start position and size:
Vector.slice<Start, Length>(); //Static slice Vector.slice(start, length); //Dynamic slice Matrix.slice<RowStart, ColStart, NumRows, NumCols>(); //Static slice Matrix.slice(rowstart, colstart, numrows, numcols); //Dynamic slice Matrix.diagonal_slice(); //Get the leading diagonal as a vector.
Like other features of TooN, mixed static/dynamic slicing is allowed. For example:
Vector.slice<Dynamic, 2>(3, 2); //Slice starting at index 3, of length 2.
Slicing can also be perferformed relative to the end of a vector.
WARNING:
End<-99>
Vector<6> v; v.slice<1, End<0> >(); //Equivalent to v.slice<1, 5> v.slice<2, End<-1> >(); //Equivalent to v.slice<2, 3> v.slice(1, End); //Equivalent to v.slice(1, 5); v.slice(3, End(-2)); //Equivalent to v.slice(3, 2);
See also What are slices?
Vector<3> v = Zeros; Matrix<3> m = Zeros Vector<> v2 = Zeros(2); //Note in they dynamic case, the size must be specified Matrix<> m2 = Zeros(2,2); //Note in they dynamic case, the size must be specified
Vectors can be filled with makeVector:
Vector<> v = makeVector(2,3,4,5,6);
Matrices can be initialized to the identity matrix:
Matrix<2> m = Idendity; Matrix<> m2 = Identity(3);
Matrices can be filled from data in row-major order:
Matrix<3> m = Data(1, 2, 3, 4, 5, 6, 7, 8, 9);
A less general, but visually more pleasing syntax can also be used:
Note that underfilling is a run-time check, since it can not be detected at compile time.They can also be initialized with data from another source. See also I have a pointer to a bunch of data. How do I turn it in to a vector/matrix without copying?.
Vector<3> a, b; ... b = a + Ones*3; // b_i = a_i + 3 a+= Ones * 3; // a_i <- a_i + 3
It is supported the same way on Matrix and slices.
Vector<Resizable> v;
v.resize(3);
v = makeVector(1, 2, 3);
v = makeVector(1, 2); //Error!
The policy behind the design of TooN is that it is a linear algebra library, not a generic container library, so resizable vectors ONLY change their size with a call to .resize()
. Assigning mismatched sizes is a fatal error, just like with static and dynamic vectors. Resizing is efficient since it is implemented internally with std::vector
. Note that upon resize, existing data elements are retained but new data elements are uninitialized.
Currently, resizable matrices are unimplemented. If you want a resizable matrix, you may consider using a std::vector
, and accessing it as a TooN object when appropriate. See I have a pointer to a bunch of data. How do I turn it in to a vector/matrix without copying?. Also, the speed and complexity of resizable matrices depends on the memory layout, so you may wish to use column major matrices as opposed to the default row major layout.
Bounds are not checked by default. Bounds checking can be enabled by defining the macro TOON_CHECK_BOUNDS
. None of these macros change the interface, so debugging code can be freely mixed with optimized code.
The debugging checks can be disabled by defining either of the following macros:
TOON_NDEBUG
NDEBUG
Additionally, individual checks can be disabled with the following macros:TOON_NDEBUG_MISMATCH
TOON_NDEBUG_SLICE
TOON_NDEBUG_SIZE
TOON_NDEBUG_FILL
TOON_NDEBUG_FILL
Errors are manifested to a call to std::abort()
.
TooN does not initialize data in a Vector or Matrix. For debugging purposes the following macros can be defined:
TOON_INITIALIZE_QNAN
or TOON_INITIALIZE_NAN Sets every element of newly defined Vectors or Matrixs to quiet NaN, if it exists, and 0 otherwise. Your code will not compile if you have made a Vector or Matrix of a type which cannot be constructed from a number.TOON_INITIALIZE_SNAN
Sets every element of newly defined Vectors or Matrixs to signalling NaN, if it exists, and 0 otherwise.TOON_INITIALIZE_VAL
Sets every element of newly defined Vectors or Matrixs to the expansion of this macro.TOON_INITIALIZE_RANDOM
Fills up newly defined Vectors and Matrixs with random bytes, to trigger non repeatable behaviour. The random number generator is automatically seeded with a granularity of 1 second. Your code will not compile if you have a Vector or Matrix of a non-POD type.
Matrix<3> m = Identity; m.slice<0,0,2,2>() *= 3; //Multiply the top-left 2x2 submatrix of m by 3. m[2] /=10; //Divide the third row of M by 10. m.T()[2] +=2; //Add 2 to every element of the second column of M. m[1].slice<1,2>() = makeVector(3,4); //Set m_1,1 to 3 and m_1,2 to 4 m[0][0]=6;
Vector<3, float> v; //Static sized vector of floats Vector<Dynamic, float> v(4); //Dynamic sized vector of floats
Likewise for matrix.
Matrix<3> A; A[0]=makeVector(1,2,3); A[1]=makeVector(3,2,1); A[2]=makeVector(1,0,1); Vector<3> b = makeVector (2,3,4); // solve Ax=b using LU LU<3> luA(A); Vector<3> x1 = luA.backsub(b); // solve Ax=b using SVD SVD<3> svdA(A); Vector<3> x2 = svdA.backsub(b);
Similarly for the other decomposition objects
For square symmetric matrices there are: SymEigen and Cholesky
If all you want to do is solve a single Ax=b then you may want gaussian_elimination()
void func(Vector<3>& v);
Vector<3>
by reference, and operate on it in place. A Vector<3>
is a type which allocates memory on the stack. A slice merely references memory, and is a subtly different type. To write a function taking any kind of vector (including slices) you can write:
template<class Base> void func(Vector<3, double, Base>& v);
A slice is a temporary object, and according to the rules of C++, you can't pass a temporary to a function as a non-const reference. TooN provides the .ref()
method to escape from this restriction, by returning a reference as a non-temporary. You would then have to write:
Vector<4> v; ... func(v.slice<0,3>().ref());
You may also wish to consider writing functions that do not modify structures in place. The unit
function of TooN computes a unit vector given an input vector. In the following context, the code:
//There is some Vector, which may be a slice, etc called v; v = unit(v);
Normalize(v)
which operates in place (for static vectors). Consult the ChangeLog entries dated ``Wed 25 Mar, 2009 20:18:16'' and ``Wed 1 Apr, 2009 16:48:45'' for further discussion. Matrix<3, 3, double, ColMajor> m; //3x3 Column major matrix
double d[]={1,2,3,4};
Vector<4,double,Reference> v1(d);
Vector<Dynamic,double,Reference> v2(d,4);
double d[]={1,2,3,4}; wrapVector<4>(d); //Returns a Vector<4> wrapVector<4,double>(d); //Returns a Vector<4> wrapVector(d,3); //Return a Vector<Dynamic> of size 3 wrapVector<Double>(d,3); //Return a Vector<Dynamic> of size 3
To crate a matrix use
double d[]={1,2,3,4,5,6}; Matrix<2,3,double,Reference::RowMajor> m1(d); Matrix<2,3,double,Reference::ColMajor> m2(d); Matrix<Dynamic, Dynamic, double, Reference::RowMajor> m3(d, 2, 3); Matrix<Dynamic, 3, double, Reference::RowMajor> m4(d, 2, 3); // note two size arguments are required for semi-dynamic matrices
Here is a function which mixes up a vector with a random matrix:
template<int Size, class Precision, class Base> Vector<Size, Precision> mixup(const Vector<Size, Precision, Base>& v) { //Create a square matrix, of the same size as v. If v is of dynamic //size, then Size == Dynamic, and so Matrix will also be dynamic. In //this case, TooN will use the constructor arguments to select the //matrix size. If Size is a real size, then TooN will simply ighore //the constructor values. Matrix<Size, Size, Precision> m(v.size(), v.size()); //Fill the matrix with random values that sum up to 1. Precision sum=0; for(int i=0; i < v.size(); i++) for(int j=0; j < v.size(); j++) sum += (m[i][j] = rand()); m/= sum; return m * v; }
Writing functions which safely accept multiple objects requires assertions on the sizes since they may be either static or dynamic. TooN's built in size check will fail at compile time if mismatched static sizes are given, and at run-time if mismatched dynamic sizes are given:
template<int S1, class B1, int S2, class B2> void func_of_2_vectors(const Vector<S1, double, B1>& v1, const Vector<S2, double, B2>& v2) { //Ensure that vectors are the same size SizeMismatch<S1, S2>::test(v1.num_rows(), v2.num_rows()); }
// Initialise the vectors Vector<3> a = makeVector(3,5,0); Vector<3> b = makeVector(4,1,3); // Now work out the products double dot = a*b; // Dot product Matrix<3,3> outer = a.as_col() * b.as_row(); // Outer product Vector<3> cross = a ^ b; // Cross product cout << "a:" << endl << a << endl; cout << "b:" << endl << b << endl; cout << "Outer:" << endl << outer << endl; cout << "Cross:" << endl << cross << endl;
Create a vector and a matrix and multiply the two together
// Initialise a vector Vector<3> v = makeVector(1,2,3); // Initialise a matrix Matrix<2,3> M(d); M[0] = makeVector(2,4,5); M[1] = makeVector(6,8,9); // Now perform calculations Vector<2> v2 = M*v; // OK - answer is a static 2D vector Vector<> v3 = M*v; // OK - vector is determined to be 2D at runtime Vector<> v4 = v*M; // Compile error - dimensions of matrix and vector incompatible
sizeof(Vector<3>)
is 24. This means that when you write Vector<3> v;
the data for v
is allocated on the stack and hence new
/delete
(malloc
/free
) overhead is avoided. However, for large vectors and matrices, this would be a Bad Thing since Vector<1000000> v;
would result in an object of 8 megabytes being allocated on the stack and potentially overflowing it. TooN gets around that problem by having a cutoff at which statically sized vectors are allocated on the heap. This is completely transparent to the programmer, the objects' behaviour is unchanged and you still get the type safety offered by statically sized vectors and matrices. The cutoff size at which the library changes the representation is defined in TooN.h
as the const int TooN::Internal::max_bytes_on_stack=1000;
.
When you apply the subscript operator to a Matrix<3,3>
and the function simply returns a vector which points to the the apropriate hunk of memory as a reference (i.e. it basically does no work apart from moving around a pointer). This avoids copying and also allows the resulting vector to be used as an l-value. Similarly the transpose operation applied to a matrix returns a matrix which referes to the same memory but with the opposite layout which also means the transpose can be used as an l-value so M1 = M2.T();
and M1.T() = M2;
do exactly the same thing.
Warning: This also means that M = M.T();
does the wrong thing. However, since .T() essentially costs nothing, it should be very rare that you need to do this.
v1 = M * v2;
a naive implementation will compute M * v2
and store the result in a temporary object. It will then copy this temporary object into v1
. A method often advanced to avoid this is to have M * v2
simply return an special object O
which contains references to M
and v2
. When the compiler then resolves v1 = O
, the special object computes M*v2
directly into v1
. This approach is often called lazy evaluation and the special objects lazy vectors or lazy matrices. Stroustrup (The C++ programming language Chapter 22) refers to them as composition closure objects or compositors.
The killer is this: What if v1 is just another name for v2? i.e. you write something like v = M * v;
. In this case the semantics have been broken because the values of v
are being overwritten as the computation progresses and then the remainder of the computation is using the new values. In this library v1
in the expression could equally well alias part of M
, thus you can't even solve the problem by having a clever check for aliasing between v1
and v2
. This aliasing problem means that the only time the compiler can assume it's safe to omit the temporary is when v1
is being constructed (and thus cannot alias anything else) i.e. Vector<3> v1 = M * v2;
.
TooN provides this optimisation by providing the compiler with the opportunity to use a return value optimisation. It does this by making M * v2
call a special constructor for Vector<3>
with M
and v2
as arguments. Since nothing is happening between the construction of the temporary and the copy construction of v1
from the temporary (which is then destroyed), the compiler is permitted to optimise the construction of the return value directly into v1
.
Because a naive implemenation of this strategy would result in the vector and matrix classes having a very large number of constructors, these classes are provided with template constructors that take a standard form. The code that does this, declared in the header of class Vector
is:
template <class Op> inline Vector(const Operator<Op>& op) : Base::template VLayout<Size, Precision> (op) { op.eval(*this); }
template<int, typename, int, typename> struct GenericVBase; template<int, typename> struct VectorAlloc; struct VBase { template<int Size, class Precision> struct VLayout : public GenericVBase<Size, Precision, 1, VectorAlloc<Size, Precision> > { ... }; }; template <int Size, class Precision, class Base=VBase> class Vector: public Base::template VLayout<Size, Precision> { ... };
then take a look at the source code ...
internal/config.hh
. If this file is empty then the default configuration will be used and TooN will work. There are several options.TOON_TYPEOF_DECLTYPE
TOON_TYPEOF_TYPEOF
typeof
extension. Only works with GCC and will fail with -pedanticTOON_TYPEOF___TYPEOF__
__typeof__
extension. Only works with GCC and will work with -pedanticTOON_TYPEOF_BOOST
TOON_TYPEOF_BUILTIN
std::complex<float>
and std::complex<double>
.TOON_USE_LAPACK
then LAPACK will be used for large systems, where optional. The individual functions are:TOON_DETERMINANT_LAPACK
Note that these macros do not affect classes that are currently only wrappers around LAPACK.