[SciPy-User] circulant matrices

Warren Weckesser warren.weckesser@enthought....
Mon Feb 1 01:53:58 CST 2010


Paul wrote:
> I would like to find,
>
> argmin_c   norm( x - dot(phi, c), 2)
>
> where x, c are vectors and phi is a circulant matrix. Is there a way
> to do this with a built-in numpy or scipy function? LAPACK doesn't
> seem to have a circulant matrix type. There is a Fortran library
> NAPACK on netlib.org that has a circulant matrix type though I don't
> know anything about it. I guess I could try to add these functions
> with f2py.
>
> I tried to solve this problem using a naive deconvolution approach
> with fft's but it's not robust. I guess I have to do some more
> research. I can't really afford to treat phi as anything other than
> circulant (like a general banded or dense matrix) as it has to be
> fast.
>
>   


Is phi singular?  If not, then wouldn't you just solve dot(phi,c) = x for c?

Based on the wikipedia article 
http://en.wikipedia.org/wiki/Circulant_matrix,
I implemented a quick test of the FFT method--see the attached script.  
(Sorry,
my notation is the usual Ax=b instead of phi*c=x.)  It seems to work, and it
is much faster than linalg.solve(), but the script is the full extent of my
experience with circulant matrices (i.e. probably even more naive than
what you have already tried), so there are probably details that I am 
missing.

Warren


> Any pointers would be appreciated.
>
> Thanks,
> Pål
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>   

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: circtest.py
Url: http://mail.scipy.org/pipermail/scipy-user/attachments/20100201/abf4faed/attachment.pl 


More information about the SciPy-User mailing list