New user self-registration is disabled due to spam. Please email eigen-core-team @ lists.tuxfamily.org if you need an account.
Before reporting a bug, please make sure that your Eigen version is up-to-date!
Bug 226 - In-place transpose
Summary: In-place transpose
Status: CONFIRMED
Alias: None
Product: Eigen
Classification: Unclassified
Component: Core - general (show other bugs)
Version: unspecified
Hardware: All All
: Low Optimization
Assignee: Nobody
URL:
Whiteboard:
Keywords: JuniorJob
Depends on:
Blocks:
 
Reported: 2011-03-20 11:36 UTC by cdubout
Modified: 2016-04-07 05:34 UTC (History)
5 users (show)



Attachments

Description cdubout 2011-03-20 11:36:27 UTC
Hello,

I just saw from the release code of Eigen 3.0 that Eigen still do in-place transposition through a temporary matrix copy.
This is problematic if the matrix is very big as there might not be enough memory to recopy it.
I have already implemented an in-place transpose operation for dense matrices using a smarter algorithm, requiring much less memory as long as the matrix is not too elongated, and I am willing to help implement this feature in Eigen if you deem it interesting.
If so, please help me getting started.
Best,

Charles
Comment 1 Christoph Hertzberg 2014-03-04 16:26:20 UTC
Sorry leaving this unattended for so long. If you are still interested, we could put your algorithm into Eigen 3.3
Comment 2 Christoph Hertzberg 2014-09-07 17:20:27 UTC
If someone is interested in implementing this, perhaps start with reading 
https://en.wikipedia.org/wiki/In-place_matrix_transposition
and the quoted references.
Make sure to benchmark your solution!

If you have trouble integrating this into Eigen, start with a stand-alone method which, e.g., takes a Matrix<Scalar, Dynamic, Dynamic>& or a Scalar pointer and two dimensions.
Comment 3 IvanKush 2016-03-25 23:37:38 UTC
Is this ticket still valid?
Comment 4 Christoph Hertzberg 2016-03-26 20:04:07 UTC
Yes, as far as I know, nobody has (re-) started working on it.
Comment 5 Dmitry Zhdanov 2016-03-31 23:37:02 UTC
(In reply to cdubout from comment #0)
> Hello,
> 
> I just saw from the release code of Eigen 3.0 that Eigen still do in-place
> transposition through a temporary matrix copy.
> This is problematic if the matrix is very big as there might not be enough
> memory to recopy it.
> I have already implemented an in-place transpose operation for dense
> matrices using a smarter algorithm, requiring much less memory as long as
> the matrix is not too elongated, and I am willing to help implement this
> feature in Eigen if you deem it interesting.
> If so, please help me getting started.
> Best,
> 
> Charles

Hello Charles.

I wrote very efficient parallelized and AVX-vectorized code for trasposeInPlace() for symmetric dense std::complex<double> matrices (and also the memory efficient algorithm for special types of sparse matrices, see the bug# 1179). It does not involve any intermediate copies, can optimized to specific processor cache size via dedicated template parameter and more than 10 times faster than Eigen implementation for 600x600 matrices on my laptop. I tried to write the code which is easily extendable for general transpose() operation (i.e. to efficiently transpose the matrix of arbitrary shape into another memory location) but never extensively tested it. 

How about to share and distribute our efforts to improve this side of Eigen? For example, all vectorized code (which means almost all code) needs to be rewritten from scratch for double and int matrices. But I do not have time now to do it.
Comment 6 Gael Guennebaud 2016-04-04 12:01:08 UTC
Hi Dmitry,

it would still be nice if you could share your specialized version. In Eigen we already provide some low level abstraction function for transposing
Comment 7 Gael Guennebaud 2016-04-04 12:03:19 UTC
(oops I hit "save change" by mistake)

Hi Dmitry,

it would still be nice if you could share your specialized version. In Eigen we already provide some low level abstraction function for transposing a block of packet: internal::ptranspose. This should help writing a generic and cross platform transposeInPlace. Your specialized version would help anyone who would like to give it a try!
Comment 8 Dmitry Zhdanov 2016-04-07 05:34:25 UTC
(In reply to Gael Guennebaud from comment #7)
> (oops I hit "save change" by mistake)
> 
> Hi Dmitry,
> 
> it would still be nice if you could share your specialized version. In Eigen
> we already provide some low level abstraction function for transposing a
> block of packet: internal::ptranspose. This should help writing a generic
> and cross platform transposeInPlace. Your specialized version would help
> anyone who would like to give it a try!

Gael: 
1) I am planning to make my project open-source, so that entire code will be available for interested people soon. I think that it contains several other pieces which might be relevant for Eigen project. So, I prefer to proceed step-by-step and finish with the Hypersparse feature first (looking forward for your feedback) unless there will be explicit interest from specific people. 

2) Regarding ptranspose packets: There is a conceptual issue with current implementation of transposeInPlace for symmetric matrices. Many useful operations like reducing matrix in place to its (anti)symmetric, (anti)Hermitian parts, calculating Hermitian adjoint etc. require replacing (i,j)-th element with some function of (i,j)-th and (j,i)-th elements. I would suggest to allow transposeInPlace to take functor as an optional argument which would allow end users to implement custom transformations of this type (this is how it is implemented in my code, and in fact I almost never use bare transpose operations in practice).

Note You need to log in before you can comment on or make changes to this bug.