Code covered by the BSD License

### Highlights from Circulant matrix

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

# Circulant matrix

### John D'Errico (view profile)

02 Feb 2009 (Updated )

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

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
21 Jan 2013 John D'Errico

### John D'Errico (view profile)

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?

Comment only
21 Jan 2013 Richard Zapor

### Richard Zapor (view profile)

Why not use R2012B

gallery('circul',c)'; ?

Comment only
29 May 2009 Lutful Nishan

### Lutful Nishan (view profile)

Hey John,
Thanks Anyways

Comment only
29 May 2009 Lutful Nishan

### Lutful Nishan (view profile)

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.

Comment only
06 Feb 2009 John D'Errico

### John D'Errico (view profile)

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.

Comment only
06 Feb 2009 us

### us (view profile)

dear john,
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

Comment only
03 Feb 2009 Jos (10584)

### Jos (10584) (view profile)

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

### John D'Errico (view profile)

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.

Comment only
03 Feb 2009 Duane Hanselman

### Duane Hanselman (view profile)

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

02 Feb 2009 John D'Errico

### John D'Errico (view profile)

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.

Comment only
02 Feb 2009 Husam Aldahiyat

### Husam Aldahiyat (view profile)

Why no use try/catch for the bsxfun thing?

Comment only
02 Feb 2009 us

### us (view profile)

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