Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Is there a parallel version of matrix multiplication in MATLAB?
Date: Wed, 4 Nov 2009 15:57:03 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 58
Message-ID: <hcs88f$psp$1@fred.mathworks.com>
References: <hcqehk$17u$1@fred.mathworks.com> <hcs5it$2gu$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
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 1257350223 26521 172.30.248.38 (4 Nov 2009 15:57:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 4 Nov 2009 15:57:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:582423


"Steven Lord" <slord@mathworks.com> wrote in message <hcs5it$2gu$1@fred.mathworks.com>...
> 
> "Cindy" <xzhan2@fhcrc.org> wrote in message 
> news: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.
> 
> From the way you phrased your question, I suspect you're raising the matrix 
> to the 6th power using repeated multiplication.  If so, why?  Just use ^ 
> (the MPOWER operator) instead.
> 
> a = rand(2000);
> tic
>     b = a*a*a*a*a*a;
> t1 = toc
> tic
>     c = a^6;
> t2 = toc
> 
> -- 

One could use the binary decomposition of the power to perform computation with less calculation:

a = rand(2000);
n = 6;

% Compute a^n

% straightforward multiplication
tic
    b = a;
    for k=2:n
        b = a*b;
    end
t1 = toc % 3.6662 seconds

% Matlab power
tic
    c = a^n;
t2 = toc % 3.0213 seconds

% binary decomposition
tic
n = 6;
nb = dec2bin(n);
ak = a;
d = 1;
for k=length(nb)-1:-1:1
    ak = ak*ak;
    if nb(k);
        d = d*ak;
    end
end
t3 = toc % 2.2377 seconds

% Bruno