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>
- flop-count