Path: news.mathworks.com!not-for-mail
From: "John D'Errico" <woodchips@rochester.rr.com>
Newsgroups: comp.soft-sys.matlab
Subject: Re: overdetermenied system
Date: Tue, 13 Jan 2009 15:03:01 +0000 (UTC)
Organization: John D'Errico (1-3LEW5R)
Lines: 40
Message-ID: <gkiaf5$300$1@fred.mathworks.com>
References: <gkhurv$nv1$1@fred.mathworks.com> <gki4hq$1b9$1@fred.mathworks.com> <gki6bu$6j$1@fred.mathworks.com> <gki89q$85e$1@fred.mathworks.com>
Reply-To: "John D'Errico" <woodchips@rochester.rr.com>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1231858981 3072 172.30.248.35 (13 Jan 2009 15:03:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 13 Jan 2009 15:03:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 869215
Xref: news.mathworks.com comp.soft-sys.matlab:511194

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gki89q$85e$1@fred.mathworks.com>...
> "John D'Errico" <woodchips@rochester.rr.com> wrote in message <gki6bu$6j$1@fred.mathworks.com>...
> > Actually, if you build it as a sparse block diagonal
> > matrix, I think that backslash might survive the
> > ordeal. At the very least, you could do it in chunks,
> > with perhaps 512 blocks in each chunk. The matrix
> > problem MUST be done as a sparse one however.
> > 
> > John
> 
>   Yes, I expect you are right, John.  It could be done that way.  I shouldn't make such generalized assertions.
> 
>   I'm not so sure about its efficiency, though, as opposed to 512*384 individual 4x2 backslashes.  The single block diagonal backslash would have to be smart enough not to waste significant overhead time on all the implied zero "off-diagonals".  The solution to a single 4x2 problem should be very fast, especially if one writes it out as an explicit vectorized expression in terms of the four basic arithmetic operations without using matlab's backslash operator itself.
> 
> Roger Stafford

If your matrix is sparse, then \ really is pretty smart.

blocks = rand(4,2,1000);
A = blktridiag(blocks,zeros(4,2,999),zeros(4,2,999));
rhs = rand(4000,1);

tic
coef = zeros(2,1000);
for i = 1:1000
coef(:,i) = blocks(:,:,i)\rhs((1:4) + 4*(i-1));
end
toc
Elapsed time is 0.105407 seconds.

tic,coef = A\rhs;toc
Elapsed time is 0.044134 seconds.

I will admit that the simple loop is pretty fast though,
especially if I add in the time to create the sparse
block diagonal matrix. blktridiag is not as efficient
as it should be here, since it fills in explicit zeros
into the upper and lower blocks.

John