- 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>
> 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
> 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....
Prev by Date:
Next by Date:
Previous by thread:
Next by thread:
Gaussian Elimination on Compound Matrix
- From: Fabian <email@example.com>