Sort eigenvectors by their eigenvalues ​​(related sorting)

Question

I have an unsorted eigenvalue vector and an associated eigenvector matrix. I would like to sort the columns of the matrix relative to the sorted set of eigenvalues. (for example, if the eigenvalue [3] goes over to the eigenvalue [2], I want the column of the matrix of eigenvectors to move to column 2.)

I know that I can sort eigenvalues ​​in O(N log N) via std::sort . Without collapsing my own sorting algorithm, how can I make sure that the matrix columns (related eigenvectors) follow along with their own values ​​as they are sorted?

Answer 1

Typically, just create a structure like this:

 struct eigen { int value; double *vector; bool operator<(eigen const &other) const { return value < other.value; } }; 

Alternatively, just put the eigenvalue / eigenvector in std::pair - although I would prefer eigen.value and eigen.vector over something.first and something.second .

Answer 2

I have done this several times in different situations. Instead of sorting the array, just create a new array that has sorted indexes in it.

For example, you have the length n of the vector (vector), as well as the 2d nxn array. Create a new array index containing the values ​​[0, n-1].

Then, instead of accessing evals as evals [i], you get access to it as evals [index [i]], and instead of evects [i] [j] you get access to it [index [i]] [j].

Now you are writing your sort procedure to sort the index, not the evals array, so instead of an index similar to {0, 1, 2, ..., n-1}, the value in the index array will be in ascending order of values ​​in the evals array.

So, after sorting, if you do this:

 for (int i=0;i<n;++i) { cout << evals[index[i]] << endl; } 

You will get a sorted list of ratings.

this way you can sort everything related to this parsing array without actually moving the memory. This is important when n gets big, you don’t want to move around the columns of the evects matrix.

basically, the i-th smallest eval will be located at index [i] and corresponds to index [i] th evect.

Edited to add. Here's the sort function I wrote to work with std :: sort to do what I just said:

 template <class DataType, class IndexType> class SortIndicesInc { protected: DataType* mData; public: SortIndicesInc(DataType* Data) : mData(Data) {} Bool operator()(const IndexType& i, const IndexType& j) const { return mData[i]<mData[j]; } }; 

Answer 3

The solution completely depends on the method of storing the matrix of eigenvectors.

The best sorting performance will be achieved if you can implement swap(evector1, evector2) so that it only revises pointers and the real data remains unchanged.

This can be done using something like double* or perhaps something more complex, depending on the implementation of your matrix.

If this is done, swap(...) will not affect the performance of your sort.

Answer 4

The idea of ​​conglomerating your vector and matrix is ​​probably the best way to do this in C ++. I am thinking about how I will do this in R and see if this can be translated into C ++. In R, this is very simple, just evec <-evec [, order (eval)]. Unfortunately, I do not know any built-in way to execute the order () operation in C ++. Perhaps someone else is doing this, in which case it can be done in a similar way.