toeplitz matrix
in [Matlab]
|
From: Bc on 18 Feb 2010 00:49 Hi all, I am trying to create a toeplitz matrix which will be of a really large size. In fact, when doing a symmetric for r = 9216x1 toeplitz(r) I get an error. The worst part is that this is a small r for what I need, so I wanted to ask what there is in terms of a solving Ax = b for x, given b and that A is a toeplitz matrix. I was going to do inv(A) or A\b, but I can't even create the toeplitz in the first place. Thanks! -Bc
From: Matt J on 18 Feb 2010 04:02 "Bc " <bcortez23(a)gmail.com> wrote in message <hlikch$6o5$1(a)fred.mathworks.com>... > Hi all, > > I am trying to create a toeplitz matrix which will be of a really large size. In fact, when doing a symmetric for r = 9216x1 > > toeplitz(r) > > I get an error. The worst part is that this is a small r for what I need, so I wanted to ask what there is in terms of a solving Ax = b for x, given b and that A is a toeplitz matrix. I was going to do inv(A) or A\b, but I can't even create the toeplitz in the first place. =============== A little more info is needed on how sparse your matrix A is. If it is sparse, my interpMatrix tool might be of help: http://www.mathworks.com/matlabcentral/fileexchange/26292-regular-control-point-interpolation-matrix-with-boundary-conditions It is fairly well optimized at creating sparse Toeplitz and Toeplitz-like matrices. If A is not sparse, it is no surprise that it is exceeding memory limits. In that case, you can probably exploit the fact that A*x=conv(A(:,1),x) . If you zero-pad this linear convolution so as to make it a circulant convolution, your equation has the closed form solution fft(x)=fft(b)./fft(A(:,1)) assuming that fft(A(:,1)) is non-zero everywhere. Otherwise, there is no solution.
From: Bc on 18 Feb 2010 11:40 Hi Matt, To be clear, the vector being passed to the toeplitz function is something like: r = [0.2095 0.5811 0.2095 0 0 .... 0] and is of size 9216x1 which means that toeplitz returns me a 9216x9216 size matrix. I think this is sparse enough, but I can only create the toeplitz in my command windows using a zeros vector, and not in my .m file using the above vector. Also, what do you think about the Levison-Durbin method to solve it? I am not sure how to use it, but perhaps this is the only way. Finally, why can matrices be only so small (9300x9300)? This will only be the smallest size I need to work with. Thanks, Bc
From: Steven Lord on 18 Feb 2010 13:46 "Bc " <bcortez23(a)gmail.com> wrote in message news:hljqhm$k60$1(a)fred.mathworks.com... > Hi Matt, > > To be clear, the vector being passed to the toeplitz function is something > like: > > r = [0.2095 0.5811 0.2095 0 0 .... 0] and is of size 9216x1 > > which means that toeplitz returns me a 9216x9216 size matrix. I think this > is sparse enough, Your r is not a sparse vector (i.e. it does not have the sparse attribute) and so the matrix TOEPLITZ returned is not a sparse matrix -- it is stored as a dense matrix. > but I can only create the toeplitz in my command windows using a zeros > vector, and not in my .m file using the above vector. > > Also, what do you think about the Levison-Durbin method to solve it? I am > not sure how to use it, but perhaps this is the only way. > > Finally, why can matrices be only so small (9300x9300)? This will only be > the smallest size I need to work with. A 9300-by-9300 real double dense matrix requires about 650 MB of contiguous memory -- and any intermediary matrices required to construct that 9300-by-9300 matrix may require additional large blocks of contiguous memory. If that's the smallest matrix you're going to try to work with, you should be on a 64-bit OS with a 64-bit version of MATLAB, or if you're going to be working with MUCH larger matrices perhaps a cluster of machines using Parallel Computing Toolbox and MATLAB Distributed Computing Server. http://www.mathworks.com/support/tech-notes/1100/1106.html http://www.mathworks.com/products/parallel-computing/ http://www.mathworks.com/products/distriben/ -- Steve Lord slord(a)mathworks.com comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
From: Oskar Vivero on 18 Feb 2010 13:49
"Bc " <bcortez23(a)gmail.com> wrote in message <hljqhm$k60$1(a)fred.mathworks.com>... > Hi Matt, > > To be clear, the vector being passed to the toeplitz function is something like: > > r = [0.2095 0.5811 0.2095 0 0 .... 0] and is of size 9216x1 > > which means that toeplitz returns me a 9216x9216 size matrix. I think this is sparse enough, but I can only create the toeplitz in my command windows using a zeros vector, and not in my .m file using the above vector. > > Also, what do you think about the Levison-Durbin method to solve it? I am not sure how to use it, but perhaps this is the only way. > > Finally, why can matrices be only so small (9300x9300)? This will only be the smallest size I need to work with. > > Thanks, > > Bc Matt's solution is working with vectors only, so you should be able to compute it. Levinson's algorithm is of order (N^2), so for for a 9300 matrix you will need 86490000 operations to find some estimate of x, unless your matrix fulfils some extra conditions, if so inverting such a matrix will require only N operations if my memory serves right. Why do you need such a large matrix in the first place? |