Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Is there a parallel version of matrix multiplication in MATLAB?
Date: Thu, 5 Nov 2009 14:21:02 +0000 (UTC)
Organization: University College Dublin
Lines: 29
Message-ID: <hcun0e$ngj$1@fred.mathworks.com>
References: <hcqehk$17u$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1257430862 24083 172.30.248.38 (5 Nov 2009 14:21:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 5 Nov 2009 14:21:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 87230
Xref: news.mathworks.com comp.soft-sys.matlab:582724


"Cindy" <xzhan2@fhcrc.org> wrote in message <hcqehk$17u$1@fred.mathworks.com>...
> Hi, I am calculating powers of large matrix. For example, taking a matrix of size 2000*2000 to the power of 6. I know that MATLAB  is known for its performance in matrix operations. But in this case, it is still quite slow. 
> 
> I have the parallel toolbox, I'm wondering is there any parallel version of matrix multiplication available? If so, could anyone give me a short example of how to use it?
> 
> Thanks so much!
> Cindy



Cathy,

The answer to your question depends on what you want to do with A^6. If you must calculate A^6 then Stephen Lord points out that A^6 is faster than A*A*A*A*A*A, because A^6 uses repeated squaring: A2 = A*A, A4 = A2*A2, A6 = A2*A4, which use 3 mat-mults instead of 5.

However, if you want to solve A^k = b then Golub & Van Loan's method (page 121) is much faster:

[L,U,P] = lu(A);
for m = 1:k
    y = L\(P*b);
    b = y;
    x3 = U\y;
    b = x3;
end;

This has complexity O(n^3 + k*n^2), which is much faster than Matlab's O(n^3*log_2 k), and yours O(n^3*k).

See http://www.derekroconnor.net/NA/LE/LE-2006-6.pdf

Derek O'Connor