Eigen - versatile, fast, reliable linear algebra library for C++

After years of trudging along with all manners of legacy libraries for vector math, both homegrown and 3rd party, I finally got turned on to Eigen by a coworker. Unfortunately I can't provide any first impressions of it yet - I've been too giddy over all the cool features (vectorization! loop unrolling! lazy evaluation! elegance! it's free!) to actually be able to sit down and try it out. Instead, I present you with the product overview verbatim from their website:

• Eigen is versatile.
  • It supports all matrix sizes, from small fixed-size matrices to arbitrarily large dense matrices, and even sparse matrices.
  • It supports all standard numeric types, including std::complex, integers, and is easily extensible to custom numeric types.
  • It supports various matrix decompositions and geometry features.
  • Its ecosystem of unsupported modules provides many specialized features such as non-linear optimization, matrix functions, a polynomial solver, FFT, and much more.
• Eigen is fast.
  • Expression templates allow to intelligently remove temporaries and enable lazy evaluation, when that is appropriate.
  • Explicit vectorization is performed for SSE 2/3/4, ARM NEON, and AltiVec instruction sets, with graceful fallback to non-vectorized code.
  • Fixed-size matrices are fully optimized: dynamic memory allocation is avoided, and the loops are unrolled when that makes sense.
  • For large matrices, special attention is paid to cache-friendliness.
• Eigen is reliable.
  • Algorithms are carefully selected for reliability. Reliability trade-offs are clearly documented and extremely safe decompositions are available.
  • Eigen is thoroughly tested through its own test suite (over 500 executables), the standard BLAS test suite, and parts of the LAPACK test suite.
• Eigen is elegant.
  • The API is extremely clean and expressive while feeling natural to C++ programmers, thanks to expression templates.
  • Implementing an algorithm on top of Eigen feels like just copying pseudocode.
• Eigen has good compiler support as we run our test suite against many compilers to guarantee reliability and work around any compiler bugs. Eigen also is standard C++98 and maintains very reasonable compilation times.

Off-screen OpenGL drawing without a graphics card using Mesa 7.6.1 on CentOS 5

So let's say you wanna rasterize a couple of polygons using OpenGL, but don't have access to a graphics card. Maybe yours broke - or maybe you're on a 6000 node render farm without a single GPU in sight. Either way you're just plain out of luck when it comes using regular OpenGL.

The Mesa 3D Graphics Library could save your day! It's been around since the dawn of time, was started by this guy named Brian Paul and as the website states:

"Mesa is an open-source implementation of the OpenGL specification - a system for rendering interactive 3D graphics.

A variety of device drivers allows Mesa to be used in many different environments ranging from software emulation to complete hardware acceleration for modern GPUs.

Mesa ties into several other open-source projects: the Direct Rendering Infrastructure and X.org to provide OpenGL support to users of X on Linux, FreeBSD and other operating systems."

Ok, but of what use is it to you? It turns out that among many other nifty things Mesa includes an off-screen rendering engine which allows you to render into any buffer, rather than the framebuffer on your non-existent graphics card. It's in other words a software version of OpenGL so not nearly as fast as your average graphics board, but hey, it's exactly that kind of hardware independence that we're after in the first place, right?


Installation

Being on CentOS, we're as usual at a rather tiresome disadvantage due to the pletora of ancient - albeit very stable - drivers in the distro, many of which you may not want (or more likely, be allowed) to fully replace, so throughout this installation guide I'll make frequent of use of the --prefix argument to "configure" in order to redirect my installations and builds to some local directory rather than the restricted /usr area.

Let's get started! First of all, CentOS 5 ships with a rather old x-org server which means the latest Mesa versions don't seem to want to build with it. Instead we'll settle for version 7.6.1, which seemingly has all the off-screen capabilities we'd like, while still working with CentOS 5. (as always, don't take my word for it though - try for yourself!). Grab it here:

ftp://ftp.freedesktop.org/pub/mesa/7.6.1/MesaLib-7.6.1.tar.bz2 (md5: 7db4617e9e10ad3aca1b64339fd71b7d)

However, before we can build Mesa we need a couple of prerequisites:

libpthread-stubs

According to Linux From Scratch,

The libpthread-stubs package provides weak aliases for pthread functions not provided in libc or otherwise available by default. This is useful for libraries that rely on pthread stubs to use pthreads optionally. On Linux, all necessary pthread functions are available, so this package is simply a placeholder.

Just download, untar, and:

> ./configure --prefix=/home/username/local

> ./make 

> ./make install

Make sure to change "/home/username/local" to wherever you want to install your Mesa setup, or ignore the prefix switch altogether AT YOUR OWN PERIL, as this will permanently change your machine configuration and likely affect other users as well.

libdrm

Again according to Linux From Scratch,

"libdrm provides core library routines for the X Window System to directly interface with video hardware using the Linux kernel's Direct Rendering Modules."

Unfortunately we can't just grab the latest version from http://www.linuxfromscratch.org/blfs/view/cvs/general/libdrm.html due to a conflict with the Nouveau driver (http://bugs.gentoo.org/324539), so instead let's grab 2.4.20 from here:

http://dri.freedesktop.org/libdrm/libdrm-2.4.20.tar.bz2 (md5: 3c56e03172b236e14905ef9a68ba2f97)

Again, download and untar, but this time:

> env PKG_CONFIG_PATH=/home/username/local/lib/pkconfig./configure --prefix=/home/username/local

> ./make 

> ./make install

Same thing again with the prefix path, but with the addition of PKG_CONFIG_PATH in order to tell autoconf where our new, custom package config resides.

Now repeat this with dri2proto-2.1 and glproto-1.4.11 as well:

http://xorg.freedesktop.org/archive/individual/proto/dri2proto-2.1.tar.bz2 (md5 5cb7987d29db068153bdc8f23c767c43)

http://xorg.freedesktop.org/archive/individual/proto/glproto-1.4.11.tar.bz2 (md5  78e7c4dc7dcb74b1869fee7897e00f59)

That should do it! Now let's build and install Mesa. However, the autoconfigure options aren't super clear and may not give us all the options we need, so instead let's do an old-school build:

> make realclean

> make linux-x86-64

This is for my specific 64-bit Intel rig - go ahead and try other options which may suit you better. You can get a listing of available ones by simply typing 'make'.

After the build has succeeded, but before we can install Mesa, we'll need to tweak the install path manually as we're not using autoconf. Open configs/default and set INSTALL_DIR to match the path used above:

INSTALL_DIR = /home/username/local

Save and close, and now you can:

> make install

Alright, that should do it! Let's try it out...


Usage

If you pull down the "Mesa Demos" tarball from:

ftp://ftp.freedesktop.org/pub/mesa/7.6.1/MesaDemos-7.6.1.tar.bz2 (md5 a4226f06732a02556fcf6be290b86dff)

you'll find a very simple and instructive demo program in progs/osdemos. To try it out, simply:

> env LD_LIBRARY_PATH=/home/username/local/lib64:{LD_LIBRARY_PATH} make

> env LD_LIBRARY_PATH=/home/username/local/lib64:{LD_LIBRARY_PATH} ./osdemo test.tga

There are obviously many other ways to infuse the newly installed directory into your LD library path. Eventually you'll also want to point your compiler at the new include path at /home/username/local/include.

Once you've successfully run the demo program, load up "test.tga" in your image viewer of choice and behold a couple of really awesome colorful primitives:

100% rendered in software (this particular one is from an 8-core Intel Xeon blade server located somewhere in the American midwest).

New website, new blog template, same old Mattias

Three posts in a day, and that's no joke! Anyway, while I have my typing gloves on I thought I'd plug my new website:

http://www.mattiasbergbom.com

and also take a moment to join the blogosphere in spontaneous cheering over the new css theme that I found in Blogspot's crypts. I figured since I didn't check since late 2007 there just had to be something new there, and blimey if I wasn't right.

In the process of transmogrifying my blog I realized I've collected a handful of comments over the years which I never saw and thus never responded to, but I'm full of faith that the posters didn't take my silence as some kind of gesture of hubris (now that I have a job and all), but rather a sign of increasing age and deteriorating cognitive ability. Sorry guys!

I'll leave you with that. Now go hike my visitor count please.

ps uT and other Linux memory goodness

The nerdery continues...

Ever wondered how much resident memory this one app consumes that you just launched from your shell?

> ps uT

and check the 'RSS' column.

Ever wondered how much physical memory you *actually* have access to?

> free -m

Ever wondered how much disk space you have available?

> df

TGIF.

Python slice notation

Addressing subsets of a list is easy a hell in Python. Dig this:

Assuming we have a list a=[some items],

a[:]
gives you the entire list. Ok, the benefit of that one maybe wasn't too obvious. Bear with me though!

a[x:y]
gives you items x to y (excluding 'y')

a[x:]
gives you items from x to the end of the list

a[:y]
gives you items from the beginning of the list to (but again excluding) y

So far so good. Let's step it up a notch:

a[x:y:z]
gives you items x to y, hitting only every z item (this is called 'stride')

a[x::z]
gives you items x to the end, with stride z

a[:y:z]
you guessed it: this gives you items from the beginning to y, with stride z

Ok. That about covers it, right? Not quite...

a[-x]
gives you x:th to last item, e.g. a[-1] gives you the last item, a[-2] the second to last and so on.

a[-x:-y]
gives you x:th to last to y:th to last items, so e.g. a[-5:-2] gives you the fifth item to the end to the second item to the end.

Now you probably go: what about a[-2:-5]? That just returns []! That's because not providing a stride means you're implicitly using a stride of +1, which in this case is equal to saying "take two steps back, then walk straight forward one step at a time until you're five steps behind where you started". Now, assuming you walk *straight* forward and don't follow the curvature of the earth, that's one hopeless journey, one which Python fortunately saves you from by just returning [].

Instead try this:

a[-x:-y:-z] 

which much as you'd expect returns the elements a[-x] to a[-y] in reverse order with stride z.

This obviously also means that a[::-1]  gives you the entire list, reversed.

Much like a[::2]  gives you every other item in the list, and a[::-2] gives you every other item in the list, in reverse order.

I may be preaching to the choir here but the ability to leverage Matlab-like short-hand like this inside a modern, object oriented, modular language is one of the things that make Python such an invaluable tool during prototyping and rapid application development, especially in a such a crazy environment as a Hollywood movie production.

Finally, if you agree that the above seems pretty friggin convenient, consider this: 3**9