Matrix Transpose

onako · #1 29-Jul-2010, 07:35

I store matrix entries in std::vector<double>, such that the reading is row by row.
This means, for matrix
1 3 4 8 9 3
3 6 8 1 1 2
2 0 9 8 7 6

the std::vector<double> would have entries: {1,3,4,8,9,3,3,6,8,1,1,2,2,0,9,8,7,6}.
To transpose the matrix I use the naive approach of iterating through std::vector, calculating for each
entry its position in a matrix transpose. Recently, I got one suggestion:

"When you have a matrix and a mapping to a one-dimensional vector, transposing is equivalent to a permutation. Now execute this permutation by sorting the elements by requested rank in the permutation result."

I understand that transposing is equivalent to a permutation, but I dont know how to approach the problem this way.
Any suggestion on how to do this (or to do matrix transpose is a faster way) is welcome.

davekw7x · #2 29-Jul-2010, 08:51

Quote:

Originally Posted by onako

...Recently, I got one suggestion:

I would like to see if the person who gave you that suggestion (it wasn't offered on this forum as far as I can tell) can give us an example. Or is this a research project? See Footnote.

I would like to see either some pseudo-code, or some small example code (in any computer language) or a step-by-step description in English. I seem to recall that it's relatively "complicated" for some of us mere humans to get a handle on. (I am including myself in the class of humans for whom it seemed to be complicated, but it's been a long time since I saw it; maybe it's easier than I thought at the time. I mean, the world was young; Fast Fourier Transforms had just made their awesome presence known; computers were made of wood and ran on kerosene... Hmmm---maybe it's not that complicated after all. That is, maybe the implementation itself is not so very complicated...)

Quote:

Originally Posted by onako

matrix transpose i[n] a faster way

Let me get this straight: The permutation method was offered as a way that is faster than just copying a vector with elements stored in row-major form to another vector with elements stored in column-major form (or vice-versa)? Man, I would really, really (really) like to see that one! I don't mean that as a "code challenge," and I don't want you to think that I think it "can't be done." What I mean is that I would really like to see it. (Really.)

The permutation method is one of several in-place matrix transposition schemes that have been derived over the years, the idea being to minimize memory usage (by not having to create another matrix or vector with size equal to the original). I really didn't know someone had implemented a "fast" version. "Fast" and "memory efficient" are often conflicting requirements. (But not necessarily always conflicting, right?)

Regards,

Dave

Footnote:
I am always interested in why (as well as how) people use the things that they ask about. I'm guessing that your program stores a matrix as a vector so that the elements will be in consecutive memory locations. (Otherwise, why not just store them as a vector of vectors?)

Why? Is it to do something like an FFT that can be (has been) optimized if the matrix elements are in consecutive memory locations? Or what?

I am also interested in knowing that your program doing that requires fast matrix transpositions and also would like to use some in-place algorithm that minimizes temporary memory requirements.

If the matrix is stored as a vector, how does your program access the matrix elements? With matrix notation or vector notation? Or what?

If you don't want to answer (or can't tell us), I understand, and hope you don't think I am being too nosy, but I like to get some context. I'm funny that way.

ahbi82 · #3 30-Jul-2010, 03:10

I don't know how to relate permutation to transpose of matrix. I'm just an engineer and not a mathematician. I know how to apply FFT to my problems BUT not knowing HOW FFT came about. OK back to the point.

Given a matrix F, with its transpose F'

F'[i][j] = F[j][i];

Therefore, for in-place operations we only need to swap elements.
Completed with the theory, now with the technical implementation.

ASSUMING input is a square matrix.

CPP / C++ / C Code:


#include <iostream>
#include <vector>

template <typename T>
static void Transpose(std::vector<T> &_src)
{
    unsigned int N = std::sqrt(_src.size());

    for (unsigned int r = 0; r < N; r++)
        for (unsigned int c = r + 1; c < N; c++)
            std::swap(_src[N * r + c], _src[N * c + r]);
}

template<typename T>
static void PrintMat(const std::vector<T> &_src)
{
    unsigned int N = std::sqrt(_src.size());

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
            std::cout << mat[N * i + j] << "\t";
        
        std::cout << std::endl;
    }
}

void main(void)
{
    std::vector<int> mat(3 * 3);

    mat[0] = mat[1] = mat[2] = 1;
    mat[3] = mat[4] = mat[5] = 2;
    mat[6] = mat[7] = mat[8] = 3;

    printf(" --- Original matrix ---\n");
    PrintMat(mat);

    Transpose(mat);

    printf(" --- Transposed matrix ---\n");
    PrintMat(mat);

}

There are other methods for non-square matrices.
Well, if your interested in more complex problems, i reckon this book "Numerical Recipes in C++".
Knowing the theory is one thing, BUT in programming algorithm, we need to break down the problem to simpler problems to have an efficient and lesser complexity.

Hope this helps!!!

onako · #4 30-Jul-2010, 05:33

Thanks for your messages.
@davekw
I'm not sure I understand your English (it is not my native language). I guess you are willing to help, but want to know some philosophical background.

@ahbi82
It would be really nice if you could share the code for transposing the non-square matrix
(possibly, with rowNo<colNo). I appreciate your help.

ahbi82 · #5 30-Jul-2010, 06:58

I think i'm pretty nice to remind you

F'[i][j] = F[j][i]

davekw7x · #6 30-Jul-2010, 07:32

Quote:

Originally Posted by onako

... I guess you are willing to help...

I'm sorry, and I realize that my post didn't answer your question.

I was suggesting that you go back to whoever gave you the advice and ask for an example or at least a hint of where to start. I mean if that person was somehow thinking that this would lead to a faster method, I would really like to have some hints from that person myself.

Your post indicated that you are looking for a "faster" way, and I was questioning the whole idea of using the "permutation method" of matrix transposition as an approach to a faster method. I know that is not what you asked, but that's what I have to offer without knowing more about what you really need.

When asking for context, I was trying to indicate that I really wanted to know what your application is. If you are doing this on some embedded system for which resources are limited (not very much system RAM), then in-place methods might be the only way to accomplish the task. If one large matrix takes over half the amount of usable memory, then obviously making a copy of the original won't work and you would have to use some in-place method.

On the other hand, if your assignment is to research and compare various methods of performing matrix transformation, I don't think getting information from a generic programming help forum is necessarily the most efficient way of operating. In other words, most people who contribute to gidforums are willing and able to help people who submit some code and a description of what it is supposed to do. Then we might able to offer some meaningful help.

Bottom line: There is no "best" way to transpose a matrix.

Some ways are faster. But "fastest" depends on system architecture and compiler (or ability to program some or all of the program in assembly language)

Some ways use less system RAM. This is highly dependent on system architecture.

Some ways use less system program space. Savings based on specific compiler optimization or hand optimization may be very inconsistent.

Some ways are "better" because the program is easier to understand.

Etc.

I did not suggest that you use a search engine to find links to the topic, since you obviously know how to use a search engine. (I tried to hint at some key words that you could use in your own search.)

However...

Since you asked about the "permutation method" and you also indicated a desire for "faster," I'll refer you to this:

From Wikipedia: In-place matrix transposition.

Quote:

Performing an in-place transpose (in-situ transpose) is most difficult when N ≠ M, i.e. for a non-square (rectangular) matrix, where it involves a complicated permutation of the data elements, with many cycles of length greater than 2.

Doesn't sound "faster" to me, and, indeed, I can't see how this general approach can be faster (for non-square matrices) than simply copying to another array, which is what I think you are already doing.

That's why I didn't feel like attempting to provide any of the really messy details on that method on this generic programming assistance board without knowing exactly what kind of help you would like.

In other words:

Tell us your requirements. Be specific.
Show us some code.
Explain why this doesn't meet your requirements.
Ask specific questions that can help us help you.

Regards,

Dave

onako · #7 30-Jul-2010, 09:40

Thanks for your message.
Note that I do not need inplace methods, as I need the original matrix.
The problem with the naive approach of iterating through the original matrix is the "large stride" which I encounter with very large matrices (external memory). For these matrices, jumps of size origMatrix.colNo, and resetting iterators when appropriate is inefficient. (to fight this problem I devised a method that performs differently depending on whether rowNo>colNo, iterating through the original matrix, or the transposed (such that the stride is +1 and min(rowNo, colNo) for other matrix).
The problem with storing the matrix in std::vector (row major) is that eventually throws a std::bad_alloc. So, I thought of the following simple algorithm: iterate through the elements of the original matrix, and store entries in std::vector<std::vector>. At the end, go through std::vector<std::vector> and collect the elements in a new (transposed) matrix. Althought the original matrix and std::vector<std::vector> both contain same number of elements, origMatrix based on std::vector will throw an exception for large amount of data(not depending on RAM), but std::vector<std::vector> will not;

CPP / C++ / C Code:

     transposed.rowNo=myMat.colNo;
     transposed.colNo=myMat.rowNo;
     transposed.mat.resize(transposed.rowNo*transposed.colNo);
     typename MatType::vt::const_iterator myFiter=myMat.mat.begin();
     typename MatType::vt::iterator mySiter=transposed.mat.begin();
     std::vector<double> helpVec(myMat.rowNo);
	std::vector<std::vector<double> > myEntries(myMat.colNo, helpVec);
	unsigned int rowCount=0;
	unsigned int colCount=0;
	while(myFiter!=myMat.mat.end()) {
	    myEntries[colCount][rowCount]=*myFiter;
	    ++colCount;
	    if(colCount==myMat.colNo) {
		++rowCount;
		colCount=0;
	    }
	    ++myFiter;
	}
	std::vector<std::vector<double> >::iterator myEiter=myEntries.begin();
	  while(myEiter!=myEntries.end()) {
	    std::vector<double>::iterator myVecIter=(*myEiter).begin();
	    while(myVecIter!=(*myEiter).end()) {
	      *mySiter=*myVecIter;
	      ++mySiter;
	      ++myVecIter;
	    }
	    ++myEiter;
	  }

onako · #8 30-Jul-2010, 09:42

So, I wonder whether there are faster ways of doing this(if I really need to be specific, I'm interested in problems where rowNo<<colNo)

zalezog · #9 30-Jul-2010, 12:14

Well a lot has already been said, although the permutation thing really needs some explanation. You were supposed to post a complete code example, I have no idea what the snippet you posted does. How about something simpler.

CPP / C++ / C Code:

#include <iostream>
#include <vector>

template < typename T>
void find_transpose( std::vector< T > &mat, std::vector< T > &trans, 
     size_t rows, size_t cols )
{
     
     size_t  i, j, k;
     for ( i = k = 0; i < cols; i++ ) {
         for ( j = 0; j < rows; j++ ) {
	      trans[ k++ ] = mat[ cols * j + i ];
	 }
     }
}

int main( void )
{
    size_t rows = 3;
    size_t cols = 2;
    int mat_elem[ ] = {1,2, 3, 4, 5, 6};
    std::vector< int > mat( mat_elem, mat_elem + sizeof mat_elem / sizeof *mat_elem );
    std::vector< int > trans( rows * cols );
    
    find_transpose( mat, trans, rows, cols );
    
    for ( size_t i = 0; i < trans.size( ); i++ ) {
         std::cout << trans[ i ] << " ";
    }
    
    return 0;
}

Edit :
The code which you provided has lots of vectors and perhaps consumes far more memory than the normal ( okay rather naive ) approach does. How many elements did you test on ? How slow was it, how much fast do you want it to be, mind posting results of your tests.

davekw7x · #10 30-Jul-2010, 15:35

Quote:

Originally Posted by onako

So, I wonder whether there are faster ways of doing this(if I really need to be specific, I'm interested in problems where rowNo<<colNo)

I hate to repeat myself, but what, exactly, are your requirements?

You talk about large stride in respect to external memory. What external memory? (See Footnote.) Are you talking about swap space that the operating system uses when the data storage is larger than can fit in physical memory? Or what.

Let's face it: If you have stuff stored in row major order and you want to access the data in column major order, you have to have large spans anyhow. Whether that is inefficient, or how inefficient it is has a huge dependence on system architecture (size of data cache on the CPU, size of hardware disk cache, size of software I/O buffers, etc.)

So, I will ask:

How large are the arrays you will be dealing with? Hundreds of rows? Thousands of rows? Millions of rows? What?

What, exactly, do you need to optimize? Are you going to do a transposition and then access the elements lots of times? Are you going to do a lot of transpositions and access the elements a few times and then do another transposition? Or what? If your program spends more time transposing rather than accessing, then consider what is used in GNU Scientific Library functions: They just create a "view" that access the data differently rather than moving it around. This takes less time to do the transposition but more time to access elements.

If you are concerned with optimization of access time, why are you using vectors? You can access elements of arrays without the overhead of the vector [] operators. Note that if you have the elements in a vector, they are always stored in consecutive (contiguous) memory so the transpose function can be designed with a parameter that is a pointer rather than a vector. That is, the data are stored in a vector if you want to do that, but the function is given the address of the first element of the vector and the number of rows and columns.

There is no standard C++ matrix class, and since we have no way of knowing how yours is designed, we have no way of compiling or investigating anything that happens during execution.

Why are you storing your 2-D matrix values in a 1-D vector? It is certainly possible to write a matrix class for which the data elements are in consecutive memory locations (if that is important), and numerical analysis type programmers often do this so that they can use program optimizations that depend on data being in contiguous memory. (Numerical Recipes MatDoub matrix class is an example.) Transposition requires moving the data around, but access is done with matrix[][] notation and only requires two pointer dereferences to get the address of the element (no arithmetic like i*ncols+j to access element (i,j) in the 1-D vector or array.) So, this is really the "fastest" way to use matrix notation to access elements.

I could go on and on, but there's really no point unless I can get some idea of what your requirements really are. Saying that one wants it to be "fast as possible" is not a statement of requirements since the answer is, "It depends."

Regards,

Dave

Footnote:
To me, when you use the expression "external memory" that means that the program and/or data can't fit into the address space that the operating system recognizes for your particular processor. So your program would have to explicitly break things up into chunks that will fit and explicitly swap them into and out of memory as the program progresses. I see no evidence of that in your code.

Forty years ago million dollar mainframes had a few tens of thousands of words of storage, and if the memory requirements were greater than that, the Job Control Language at the front of your deck of punch cards would instruct the operator to mount a "scratch" tape on one of the arrays of 9-track tape drives lined up along the wall so that the program could read and write very large amounts of data to this external storage.

Nowadays 32-bit operating systems give the user two or three gigabytes of address space, and 64-bit operating systems give even more (lots more). Of course swapping stuff into and out of memory (done automatically by the operating system and not by explicit program statements) is not as efficient as keeping everything resident in physical memory. Speaking in general terms for workstation users, they have no way to know exactly how big things have to be in order to have to swap stuff in and out of memory, since that depends, not only on how much physical memory is present, but also depends on how many other processes are running and what resources they are requiring.

That's why I tried to get you to tell us exactly what your requirements are.

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Problem with changing 'this'	Fematich	C++ Forum	2	07-Apr-2010 08:05
How to start a C++ matrix class like this?	nanchuangyeyu	C++ Forum	0	10-Jul-2009 20:24
Giving garbage value as the result of product	winner	C Programming Language	10	19-Jul-2008 01:47
i need help in C++ PLZ	its_me	C++ Forum	3	04-Dec-2006 21:51
Combining Vectors and References	Frankg	C++ Forum	7	14-Jan-2006 06:17

Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose

Re: Matrix Transpose