Main Page | Namespace List | Class Hierarchy | Class List | Namespace Members | Class Members

Introduction

Introduction to LinAlg

LinAlg 3.1 is a simple C++ template vector and matrix library, generally intended for 2D, 3D, 4D computations in computer graphics and related fields. The objects are fixed-size and the storage is dense, resulting in good optimization opportunities for the compiler.

Vectors and matrices are stored as dense arrays of values. All basic types are supported for the underlying storage type, and by default, the library includes instantiations for float, double, int and unsigned int in two, three and four dimensions.

Changes since version 2.0

Removal of the dimension template parameter

In version 2, each of Vector and Matrix were templated on both the underlying data type and the dimension, for example, LinAlg::Vector<float,2>. However, using this approach, it is difficult to provide constructors such as Vector(float x, float y). The current version generates source for each dimension separately, for example, LinAlg::Vec2<float>. Note that the names were shortened from Vector to Vec and Matrix to Mat. The library provides source for both Vec and Mat in dimensions 2, 3, and 4. If you need different dimensions, they are trivially generated using src/generate.cpp. Please note that Vec?.h and Mat?.h are now generated files, and should not be edited directly. Edit VecTemplate.* and MatTemplate.* instead and re-run generate.

Note that this means that each individual header (Vec2.h, Vec3.h, etc.) should be smaller and faster to compile. Currently the headers only pull in <iosfwd> and <string>, the latter could be removed if the description() member is not needed.

Convenience.h and its build() functions has been removed in favor of using each classes' constructor directly. Similarily, the convert() methods (for converting from a class of different underlying type) have been replaced by the constructors.

Zero initialization by the default constructors

Some users wanted the default constructor to automatically zero out the object's data, making the default constructor the same as explicitly assigning from the zero vector. This is a speed/safety tradeoff which can be controlled by defining the preprocessor macro LINALG_DEFAULT_INITIALIZE_TO_ZERO. If this macro is not defined then vectors and matrices are not initialized in the default constructor. If this macro is defined, then they are intialized to zero.

Dependencies

The code is self-contained except for the optional ability to call the LAPACK numerical library to determine the eigenvalues and eigenvectors for matrices with dimension greater than three. For 2D and 3D matrices, it is more efficient and feasible to compute the eigenvalues and eigenvectors "by hand", so these do not need LAPACK.

On Unix-type systems, link against the system-supplied LAPACK library, ususally called liblapack or, on OS X, the vecLib framework. Under Windows, the easiest way to get LAPACK is to download Intel's MKL library, which includes LAPACK. Unfortunately, the MKL is commercial software, though it does have a free evaluation.

If you don't care about computing eigenvalues and eigenvectors for dimensions four and above, then you can define the macro LINALG_NO_LAPACK, which will remove the requirement to link against LAPACK and make LinAlg completely self-contained.

Included build environments

There are projects to build the library and its test suite for the following integrated development environments:

Test suite and examples

There is a test suite in src/run_tests.cpp that tests most aspects of the library and a tiny example in src/example.cpp that demonstrates "normal" usage. You should be able to build and run these to verify that everything is working. The included IDE project files include targets to do this for you.

Template libraries and linking

By default, LinAlg provides Vec and Mat for the types float, double, int and unsigned int in two, three and four dimensions. If this is all you need, then you can skip this section. If you need LinAlg to not generate these default types, or if you need to use a custom type, then you should read this section.

C++ template libraries are different from standard libraries. A C++ template does not actually generate code; it's a pattern that tells the compiler how to generate code when the user actually creates an instantiation of the class.

A normal class usage might look like this: 

// In the header List.h
class List {
    public:
    void print();
    ...
};

// In the implementation List.cpp
#include "List.h"
void List::print() {
    ...
}

// In some program
#include "List.h"
int main() {
    List list;
    list.print();
}
The implementation file is compiled once and the resulting object code for print() is stashed away into an object file List.o. When the main program is compiled, then the compiler generates a reference to the body of List::print(), then the linker puts it all together into a runnable program. It works because the linker can find the implementation of List::print() in List.o. The important point is that when the compiler is compiling the main program, it doesn't have the implementation of List::print() (it's only read List.h), but it can generate a reference to it and trust that the linker will find it.

If we change List to depend on a template parameter T, we might start with this: 

// In the header List.h
template <typename T> 
class List {
    public:
    void print();
    ...
};

// In the implementation List.cpp
#include "List.h"
template <typename T>
void List<T>::print() {
    ...
}

// In some program
#include "List.h"
int main() {
    List<int> list;
    list.print();
}
If you were to try to compile this together, however, you would get an error because the linker would not be able to find the implementation of List<int>::print(). When the compiler compiles the main program, it reads only List.h, not List.cpp. So when it sees the declaration List<int> list, it does its copy and paste trick replacing T for int in the List class. However, since it doesn't have the implementation of print(), all it can do is generate references to List<int>::print(), just like in the non-template version. So far, so good. However, the problem is that when the compiler compiles List.cpp, it has no clue what types might get substituted for the type T, and so it generates no actual object code at all. So List.o has no object code for List<int>::print() and the linker will fail to produce a working program.

A related problem is inline functions: for the compiler to insert the body of an inlined function into its caller, it must have the entire definition at hand when the function is called. Hence inline functions must always be placed in full in the header. Most of LinAlg functions are very simple (generally consisting of a single loop over the elements) and are inlined and thus defined fully in the header. However, some significantly-large ones are not: for example, input/output and those that call the standard numerical library LAPACK. The rest of this discussion pertains to these non-inlined functions.

In our simple example, there are currently two solutions: the first, and most common, is to simply append the definitions from List.cpp at the end of List.h as inlined functions and forget about List.cpp. Then, when the compiler compiles the main program, List.h contains the complete code for List and the declaration List<int> list generates object code for all of List<int>, including List<int>::print(). This is a "header-only" library, but it has one major drawback: the header file can get enormous. Every file that includes List.h has to read and parse the entire implementation of List! You are in effect not just compiling List.cpp once, but every time you compile a file that uses List. Remember also that while header files can often forward-declare or otherwise avoid including other headers, the actual implementation always needs full definitions and headers for everything it uses. This is a major reason why many C++ libraries are so horribly slow to compile against. Slow compilation times mean low programmer productivity.

The other solution is to force the compiler to generate object code for List<int> while it is compiling List.cpp. C++ has a mechanism for this, it is called explicit instantiation. With explicit instantiation, our example becomes: 

// In the header List.h
template <typename T> 
class List {
    public:
    void print();
    ...
};

// In the implementation List.cpp
#include "List.h"
template <typename T>
void List<T>::print() {
    ...
}
template class List<int>;   // Explicit instantiation

// In some program
#include "List.h"
int main() {
    List<int> list;
    list.print();
}
When the compiler compiles List.cpp and reads the explicit instantiation, it generates object code for all of List<int> and places them in List.o, since it has all the definitions it needs at that point. The linker will end up finding the object code for List<int>::print() in List.o and will generate a working program. The upside of this solution is that the implementation is only compiled once, not multiple times and the header gets to stay as small as possible. The downside is that you somehow have to magically know what types you will be using in your program and insert the explicit instantions into the implementation code. For general libraries, this is tricky or impossible. However, for a relatively well-characterized library like a linear algebra library, however, we can probably guess.

LinAlg uses this second solution to keep the header files as small as possible. By default we instantiate the templates for the float, double, int, and unsigned types. When compiling the library, you can control the explicit instantiations in two ways:

Known Problems

Visual Studio Express C++ 8.0

Visual Studio Express 8.0 with service pack 1 applied has a known bug when compiling some member functions. If you get an error C2244 "unable to match function definition" when compiling Vector.cpp, you need to apply the hotfix listed in the following knowledge base article from Microsoft:

http://support.microsoft.com/default.aspx/kb/930198

You should only apply this hotfix if you are actually getting the C2244 error.

Changes

Changes from version 3.0

Changes from version 3.0

Changes from version 3.0

© 2005-2008 Adrian Secord.