Re: BZDEV: Matrix multiplication

[Rob L. <lo...@la...>]

On Thu, 10 Dec 1998, Luc Bourhis wrote:

> I noticed that expression templates are used for matrix multiplications
> : this means that with matrices A (MxN), B (NxP) and C (PxR), the
> product D = A*B*C will be computed using the formula : D_mr =
> A_mn*B_np*C_pr (with an implicit summation on repeated indices). But the
> first multiplication is done many times with the same operands.
> Therefore, the following two steps calculation : D1 = A*B, D = R1*C will
> reduce the number of operations.

Someone replied to this stating that this may not be a common problem, but
I inadvertently deleted the message.

For my own applications, a _very_ common and simpler example is
v = A * B * r, where A(N,N), B(N,N), v(N), and r(N). Computing this as
v = (A * B) * r is an O(N^3) operation, whereas v = A * (B * r) is O(N^2).

At this point, I don't expect that expression templates will take care of
all optimizations.  Moreover, so that when all else "fails," (in terms of
efficiency) I'm hopeful that whatever array container I'm using will be
reasonably efficient for scalar indexing.  I guess the loop constructs
don't annoy me as much as other programmers.

-Rob

--
 Rob Lowrie                     \       Los Alamos National Laboratory
 lo...@la...                 \ Hydrodynamic Methods, X-HM, MS D413
 http://www.c3.lanl.gov/~lowrie/  \          Los Alamos, NM  87545 USA

--------------------- blitz-dev list --------------------------------
* To subscribe/unsubscribe: mail to maj...@oo..., with
"subscribe blitz-dev" or "unsubscribe blitz-dev" in the body of the message
* Blitz++ web page: http://oonumerics.org/blitz/