Code covered by the BSD License  

Highlights from
Circulant matrix

5.0

5.0 | 3 ratings Rate this file 45 Downloads (last 30 days) File Size: 2.87 KB File ID: #22858

Circulant matrix

by

 

02 Feb 2009 (Updated )

The circulant matrix generated from a vector as the first row (or first column)

| Watch this File

File Information
Description

A circulant matrix is a square matrix generated from a vector as the first row (or column). Successive rows use the same elements as the first row, but each such row is circularly shifted by one element. See that both Wikipedia and Mathworld show the circular shifts as forward shifts.

http://en.wikipedia.org/wiki/Circulant_matrix

http://mathworld.wolfram.com/CirculantMatrix.html

At the same time, others seem to employ backwards shifts (see FEX 22814), so there is clearly a dichotomy in the set of people who use circulant matrices. I'll offer my own version of circulant.m to cover either style. It allows the user to specify either form as desired, although the default uses the forwards shift. For example:

A backwards (-1) shift, the result is a symmetric matrix.
 
   circulant([2 3 5 7 11 13],-1)
 
   ans =
        2 3 5 7 11 13
        3 5 7 11 13 2
        5 7 11 13 2 3
        7 11 13 2 3 5
       11 13 2 3 5 7
       13 2 3 5 7 11
 

A forwards (+1) shifted circulant matrix, built using the first row defined by vec.
 
   circulant([2 3 5 7 11],1)
 
   ans =
        2 3 5 7 11
       11 2 3 5 7
        7 11 2 3 5
        5 7 11 2 3
        3 5 7 11 2
 
And a positively shifted circulant matrix, built from vec as the first column. Here I've provided only one argument, so it uses the default.

   circulant([2;3;5;7;11])
   ans =
        2 11 7 5 3
        3 2 11 7 5
        5 3 2 11 7
        7 5 3 2 11
       11 7 5 3 2

Finally, a negative shift applied to build a character circulant matrix.

   circulant('abcdefghij',-1)

   ans =
   abcdefghij
   bcdefghija
   cdefghijab
   defghijabc
   efghijabcd
   fghijabcde
   ghijabcdef
   hijabcdefg
   ijabcdefgh
   jabcdefghi

Finally, I'll note that the algorithms I chose internally are not absolutely the fastest, although they are fully vectorized. I could have achieved a further 10-20% speed boost with the use of bsxfun. The code for the bsxfun variants is included, but commented out. The problem is that many people still have not upgraded to a release that includes bsxfun. While I could have put in a test to see if bsxfun exists, that test itself takes some time since exist is relatively slow. On small vectors, the test itself might take more time than it takes to generate the matrix.

So for any user who has bsxfun and needs maximal throughput, I've put it all in there for you.

Acknowledgements

Circular Matrix Computation inspired this file.

This file inspired Circulant (V2.0, Feb 2009).

MATLAB release MATLAB 7.5 (R2007b)
Other requirements virtually any matlab release
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (12)
21 Jan 2013 John D'Errico

Why not? A good question, but it shows that you have not tried it, or seriously tested it, or even looked at the help.

My circulant code is FASTER than the gallery code. So why would you use (or recommend) a slower solution?

>> c = 1:100;
>> timeit(@() gallery('circul',c))
ans =
4.6459e-04

>> timeit(@() circulant(c))
ans =
2.5056e-04

Next, circulant is CONSIDERABLY more flexible than the gallery trick, allowing you to build a variety of related matrices. So use a tool that is flexible, is fast, AND has good help. All of that suggests use of this tool.

I could have written circulant as a wrapper for the gallery trick, but why?

21 Jan 2013 Richard Zapor

Why not use R2012B

gallery('circul',c)'; ?

29 May 2009 Lutful Nishan

Hey John,
I think I figured it out myself, the function was in the download file link.
Thanks Anyways

29 May 2009 Lutful Nishan

Hi John,
I am new to matlab, so sorry for asking such stupid question.
Did you create a function for circulant? or was it a library call?
Because when I copy paste circulant([2;3;5;7;11]) or our other commands in matlab I receive error.
Thanks in advance for helping.

06 Feb 2009 John D'Errico

us is right. Duane sent me his revision, and I was lazy, just submitting it essentially as he wrote it, only acknowledging his effort on the website. I'll revise that now.

06 Feb 2009 us

dear john,
in your 'updates' note you tell the community that duane has substantially added to the help section of your already great submission...
however, if i look at the revised code, i do not see any acknowledgement of his effort embedded in the code...
appreciating you as an academically very honest author, i am sure this is just a temporary mishap...
us

03 Feb 2009 Jos (10584)

This well-written function inspired me to submit my own version that uses simple matrix operations which should be up soon. Well done John and thanks for the inspiration.

03 Feb 2009 John D'Errico

I agree with Duane. He offered a help block that was cleaner, and far less verbose, so the new version I just put up has his help. My thanks.

03 Feb 2009 Duane Hanselman

Other than having non MATLAB standard help text formatting, this does everything one could ask for and more.

02 Feb 2009 John D'Errico

Husam asks a good question. I considered a try/catch construct, as well as just a test against exist('bsxfun'). The thing is, the alternative was fast enough that bsxfun does not give a terribly significant speed gain. For reasonably small matrices, a simple test for bsxfun may cost as much time as creating the entire matrix. Even for larger matrices, the time penalty did not seem excessive for avoiding bsxfun here. As I suggest, for someone who needs to truly maximize speed, they will not want to pay any additional time penalty.

I'll look at try/catch to see if it costs less than exist. If not, in a year or so, most of the matlab base will have moved to a release that includes bsxfun, so I'll look to change the code then.

02 Feb 2009 Husam Aldahiyat

Why no use try/catch for the bsxfun thing?

02 Feb 2009 us

a long overdue function with excellent help and examples as well as a clean computational engine including copious comments...
what else...
us

Updates
06 Feb 2009

Acknowledged Duane in the code for his revised help block.

Contact us