Linear Algebra Packages

Dense

I think LAPACK is optimal for the most tasks. It is already installed on Linux and MacOSX. I followed examples from here.

Sparse

Problem Solutions
System of Linear Equations CXSparse
Eigenvalue decomposition:
Symmetric 		SVDLIBC using Lanczos method
Eigenvalue decomposition:
General 		MATLAB's eigs uses Implicitly Restarted Arnoldi Method. They use ARPACK implementation, which can also be used directly from C++ with arpack++. There exists a parallel version: PARPACK

PCA

There is a fast PCA method without calculating covariance matrix: EMPCA.

Approximate Nearest Neighbors

FLANN is easy to use. Pre-compiled binaries can be found here.
It doesn't return exact results, though, even if I force it to visit all the leafs.

I also have successfully used ANN before.