Ordinamento autovettori dai loro autovalori (associato di smistamento)

Question

Ho un vettore non ordinato di autovalori e una matrice di autovettori correlato. Vorrei ordinare le colonne della matrice rispetto alla serie ordinata di autovalori. (Ad esempio, se autovalore [3] si sposta autovalore [2], voglio colonna 3 della matrice autovettore per spostarsi a colonna 2).

so che posso ordinare gli autovalori in O(N log N) via std::sort. Senza rotazione mia algoritmo di ordinamento, come faccio a rendere sicuro colonne della matrice (gli autovettori associati) seguire con i loro autovalori quanto questi ultimi sono allineati?

Answer 1

In genere basta creare una struttura simile a questa:

struct eigen { 
    int value;
    double *vector;

    bool operator<(eigen const &other) const { 
        return value < other.value;
    }
};

In alternativa, basta mettere l'autovalore / autovettore in un std::pair -. Anche se io preferirei eigen.value e eigen.vector sopra something.first e something.second

Answer 2

Ho fatto questo numero una di volte in diverse situazioni. Invece di ordinamento della matrice, basta creare un nuovo array con gli indici ordinate in esso.

Ad esempio, si dispone di un array di lunghezza n (Vector) evals e 2D evects matrice nxn. Creare un nuovo indice array con contiene i valori [0, n-1].

Quindi, piuttosto che accedere evals come evals [i], si accede come evals [indice [i]] invece di evects [i] [j], si accede evects [index [i]] [j].

Ora è scrivere il vostro routine di ordinamento per ordinare l'array di indici piuttosto che l'array evals, così invece di guardare come indice {0, 1, 2, ..., n-1}, il valore della matrice indice sarà in ordine dei valori crescenti nella matrice evals.

Così, dopo l'ordinamento, se si fa questo:

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

si otterrà un elenco ordinato di evals.

In questo modo è possibile ordinare tutto ciò che è associato con tale matrice evals senza effettivamente muoversi memoria intorno. Questo è importante quando n diventa grande, non si vuole essere in movimento intorno alle colonne della matrice evects.

fondamentalmente la-esimo più piccolo eval sarà ubicato a indice [i] e che corrisponde all'indice [i] esimo evect.

A cura di aggiungere. Ecco una funzione di ordinamento che ho scritto per il lavoro con std :: sort di fare quello che ho appena detto:

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

La soluzione si basa esclusivamente sulla strada si intende usare il matrice autovettori.

La migliore performance, mentre l'ordinamento sarà raggiunto se è possibile implementare swap(evector1, evector2) modo che rebinds solo i puntatori ei dati reali viene lasciata invariata.

Questo potrebbe essere fatto utilizzando qualcosa come double* o probabilmente qualcosa di più complicato, dipende dalla vostra implementazione della matrice.

Se fatto in questo modo, non sarebbe swap(...) influenzare le prestazioni operazione di ordinamento.

Answer 4

L'idea di conglomerating vostro vettore e la matrice è probabilmente il modo migliore per farlo in C ++. Sto pensando a come avrei potuto farlo in R e vedere se questo può essere tradotto in C ++. In R è molto facile, basta evec <-evec [, ordine (eval)]. Purtroppo, io non conosco nessun costruito in modo per eseguire l'operazione ordine () in C ++. Forse qualcun altro lo fa, nel qual caso questo potrebbe essere fatto in un modo simile.