theochem / procrustes

Python library for finding the optimal transformation(s) that makes two matrices as close as possible to each other.
https://procrustes.qcdevs.org/
GNU General Public License v3.0
109 stars 20 forks source link

More efficient evaluation of the error function for k-opt #79

Closed PaulWAyers closed 3 years ago

PaulWAyers commented 3 years ago

In permutation Procrustes, the error is computed by explicit multiplications like (A x P) or (P1 x A x P2). This is extremely inefficient because one is only rearranging rows/columns of A (an O(n^2) operation) but one is using matrix multiplication (which is O(n^3)) to do this. This can be done efficiently by:

  1. For each permutation matrix, construct the corresponding permutation of indices; then constructed the matrix with permuted rows/columns with fancy indexing.
  2. For each permutation matrix and the original matrix, construct a sparse matrix; use sparse matrix multiplication. The sparse matrix representation for A should be constructed only once or otherwise you'll give up much of the gains due to overhead.

(a) would be preferred in my view. It amounts to a more efficient way to evaluate the error function for k-opt in its application to Procrustes.

PaulWAyers commented 3 years ago

This is redundant with https://github.com/theochem/procrustes/issues/65