[Date Index] [Thread Index] [Author Index]

Re: flop-count

• To: mathgroup at smc.vnet.net
• Subject: [mg92309] Re: [mg92283] flop-count
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Sat, 27 Sep 2008 06:50:48 -0400 (EDT)
• References: <200809261025.GAA09990@smc.vnet.net>

Fabian wrote:
> Dear Group-
> 
> Is there a way to compute the flop-count (i.e., number of sums and
> products) in matrix algebra ?  For example:
> 
> ScalarResult = x.A.B.C.D.E.F.y
> 
> where:
> 
> x = 1 x ... vector
> y = ... x 1 vector
> A,B,C,D,E,F = ... x ... matrices
> 
> I was considering the possibility of using FullForm, Head, or counting
> the number of Plus and Times instances, but no luck.
> 
> Any help is appreciated.
> 
> Thank you.


The flop count depends on many details of implementation. For one thing, 
unlike the actual matrix product, that count is not associative. 
Moreover there are sub-cubic matrix multiplication methods (for 
compatible matrices of comparable dimensions).

You might code for a "best case" which assumes no asymptotically fast 
method but uses the best possible associativity arrangement. So your 
count for a length n vector dot product would be n products and n-1 
sums, or O(2n). Proceed from there to get matrix results....

Daniel Lichtblau
Wolfram Research

• References:
  • flop-count
    • From: Fabian <fabian.uriarte@gmail.com>