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 15:20:19 +0000 (UTC)
Organization: Boeing
Lines: 15
Message-ID: <hcuqfj$4m7$1@fred.mathworks.com>
References: <hcqehk$17u$1@fred.mathworks.com> <hcs5it$2gu$1@fred.mathworks.com> <hcs88f$psp$1@fred.mathworks.com> <hcs8t2$7r8$1@fred.mathworks.com> <hcs9ef$c0u$1@fred.mathworks.com> <hct1kq$kd$1@fred.mathworks.com> <hct2k7$ao$1@fred.mathworks.com>
Reply-To: <HIDDEN>
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 1257434419 4807 172.30.248.35 (5 Nov 2009 15:20:19 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 5 Nov 2009 15:20:19 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 756104
Xref: news.mathworks.com comp.soft-sys.matlab:582763


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <hct2k7$ao$1@fred.mathworks.com>...
> "James Tursa" <aclassyguy_with_a_k_not_a_c@hotmail.com> wrote in message <hct1kq$kd$1@fred.mathworks.com>...
> 
> > 
> > Hey Bruno ... out of curiosity, do you happen to know if the polyvalm function uses this type of scheme (or similar) to minimize total computations? I could code something up and make some timing tests, but wondered if you already knew the answer.
> 
> Hi James,
> 
> I believe (!) POLYVAL uses horner's scheme. I have no idea how they compare to each other. I would say Horner's is more efficient in general, but if you confirm that it will be great!!! Thanks for bringing this interesting question up.
> 
> Bruno

Well, Horner's scheme is just a simple nested rewrite of the polynomial evaluation. That is definitely not the most computationally efficient method if a lot of the polynomial coefficients are zero. e.g., for A^16 Horner's scheme, if taken literally, would do 15 multiplies, whereas the binary decomposition scheme would do only 4 multiplies. But for a general case where there is a mix of zero and non-zero coefficients, it seems you could in some cases still use some form of binary decomposition to get the minimum overall computation, but at the expense of storing more intermediate matrices. I may have to make some tests ...

James Tursa