MathGroup Archive 2008

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

Search the Archive

Re: flop-count


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


  • Prev by Date: SparseArray
  • Next by Date: Re: Help
  • Previous by thread: flop-count
  • Next by thread: Gaussian Elimination on Compound Matrix