Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
permute complexity

Subject: permute complexity

From: marina

Date: 2 Jan, 2009 09:16:19

Message: 1 of 3

Hello
I was wondering what is the complexity of MATLAB permute algorithm?
And does it allocate additional memory to handle the processing or it is inplace algorithm?
Thanks

Subject: permute complexity

From: Matt

Date: 2 Jan, 2009 09:42:02

Message: 2 of 3

marina <elizabeth.h1@hotmail.com> wrote in message <28554644.1230887840028.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello
> I was wondering what is the complexity of MATLAB permute algorithm?
> And does it allocate additional memory to handle the processing or it is inplace algorithm?
> Thanks

It's definitely not inplace.

Also, it appears that a different permute algorithm is used for different data types (see transcript below from MathWorks Tech Support).
 
Notice that (somewhat ironically), it is significantly slower for single floating point than double.

>>a=rand(200,200,200); as=single(a);

>> tic; permute(as,[3 2 1]);toc
Elapsed time is 1.064809 seconds.

>> tic; permute(a,[3 2 1]);toc
Elapsed time is 0.347932 seconds.


---------------------------------------------------------------------------------------
I am writing in reference to your Service Request # 1-3PWUKX regarding 'permute() behavior'.

PERMUTE is independently defined for different types.

By typing "which -all permute" from the command prompt shows that permute is defined as a method for all standard types including int8 and single.

The reason you have seen that PERMUTE is faster for double, because certain operations are optimized in the double implementation because that is the most common case in MATLAB and other data-types may still be using slower code.

If you need further assistance regarding this issue, please reply to this email preserving the THREAD ID listed below. If you have a new technical support question, please submit a new request here:

http://www.mathworks.com/contact_TS.html.

Sincerely,

Saima
Application Support Engineer
Technical Support Department
The MathWorks, Inc.
Phone: (508) 647-7000 option 5

Subject: permute complexity

From: Roger Stafford

Date: 2 Jan, 2009 23:06:01

Message: 3 of 3

marina <elizabeth.h1@hotmail.com> wrote in message <28554644.1230887840028.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello
> I was wondering what is the complexity of MATLAB permute algorithm?
> And does it allocate additional memory to handle the processing or it is inplace algorithm?
> Thanks

  If A is a two-dimensional m x n matrix, you can do a (somewhat inefficient) transpose operation - which is a simple form of the 'permute' function - as follows:

 [I,J] = ndgrid(m*(0:n-1),1:n);
 p = I+J;
 B = reshape(A(p),n,m);

This can rather easily be generalized to an n-dimensional 'permute' using 'ndgrid', though I am sure the real 'permute' is much faster.

  The array p is a particular kind of permutation of the sequence 1:m*n which is crucial to this operation, and is equivalent to a strange way of counting with digits which uses a mixed base system. The first digit - the most rapidly changing one - is taken mod n and has a place value of m, whereas the second digit is done mod m (with a 1 added) with a place value of 1. This method can be generalized to many digits - that is to say, many dimensions, one for each digit - in an analogous manner.

  It is therefore conceivable to me that Mathworks has figured out a way of generating and using such a permutation, p, inplace, so that there would be no need for holding the entire permutation p all at one time. It could used up as fast as it is generated, just as we do when we count with decimal numbers in the ordinary way. In this case the only large new memory would be the final result of 'permute'. However, I am of course just speculating here. I have no inside information as to Mathworks' methods.

Roger Stafford

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us