Add features required for the migration of rusty-machine to nalgebra

[sebcrozet]

See that issue from rusty-machine.
So far, the following features are missing from nalgebra:

• Simplify the construction of DVector by addressing Add more constructors adapted to DVector. #377 This will require breaking changes.
• Add statistics functions: variance, mean.
• Add more general norms by addressing Implement norm on vectors with custom metric #258
• Add row and column iterators.
• Add .select_rows(iterator) and .select_columns(iterator) to extract a subset of rows or columns from a matrix.
• Allow the concatenation of rows or columns by addressing No obvious way to concatenate vectors and matricies #446.
• Document all the added features, including doc-tests.

More element may be added to this list as I study the codebase of rusty-machine.

[ralfbiedert]

Not sure if this belongs here, but I'm the author of ffsvm (a SVM classifier) and I also considered migrating to nalgebra for my math, and to simplify data exchange.

We use ffsvm in our company as a module in VR and gaming libraries, where literally every microsecond (and allocation) counts.

Right now there are 2 features missing in nalgebra that prevent me from making a switch. I generally believe they are essential for any performance sensitive SVM implementation; rusty-machine, ffsvm, or otherwise:

• sparse vectors
• properly aligned SIMD vectors

Sparse vectors are basically needed for high-dimensional SVMs, like word lists, where a vector might have +30k entries, out of which only very few are actually used. Using dense vectors here would be a big performance hit.

Conversely, for "fully dense" SVMs, properly aligned SIMD vectors are the way to go. When I started looking into ffsvm about a year ago I evolved the code from "naive" over "manual vectorization" to "actual SIMD":

At least back then, there was a 2x speed difference between "trusting the compiler" and "do SIMD yourself". I wouldn't be surprised if that difference is up to >4x even today when considering various compiler flags, target platforms, ... On top of that (not properly reflected in the graph because the test vectors were so big) is a performance impact when dealing with unaligned SIMD data.

If I had to prioritize between these I'd pick SIMD over sparse vectors.

Long story short, I have seen you have tracking issues for these items already. However, I wanted to post this as more of a note that I would also love to align with rustsim / nalgebra, but those issues are holding me back.

[sebcrozet]

@ralfbiedert Thank you for describing your needs and use-case! There is an increasing demand for SIMD and sparse vectors/matrices in nalgebra so those are the two big topics we will want to address in 2019. To help prioritize our work could you:

• Provide in that issue details about the kind of operations you need on sparse vectors.
• Provide in that issue details about the linear algebra operations you are using expensively in ffsvm. You seem to have a great deal of experience with SIMD, so we will greatly appreciate if you share any expertise about the best practices or even contribute to the nalgebra code if you which!