Skip to main content

matrix - Why is calling Dot with many arguments so inefficient?


Say I want to multiply a reasonably large list of symbolic matrices.


tab = 
Partition[#,4]&/@
Table[
Symbol[CharacterRange["a","z"][[nm]]<>ToString[nn]],{nn,1,12},{nm,1,16}];

tab[[3]]



{{a3,b3,c3,d3},{e3,f3,g3,h3},{i3,j3,k3,l3},{m3,n3,o3,p3}}*)

Applying Dot directly on the list is pretty slow.


Dot@@tab // AbsoluteTiming // First


2.761965

However, because of associativity I can split the multiplication in a way that Dot is always called with a small number of arguments.


FDot=

Dot@@
Nest[
(Dot@@@(Partition[#,Divisors[Length@#][[2]]]))&,
#,
Total[Last/@FactorInteger@Length@#]]&;

FDot@tab // AbsoluteTiming // First


 0.002115


This is $3$ orders of magnitude faster.


So, can anybody explain to me why Mathematica computes $$ ((a \cdot b) \cdot (c \cdot d)) \cdot ((e \cdot f) \cdot (g \cdot h)) $$ faster than $$ a \cdot b \cdot c \cdot d \cdot e \cdot f \cdot g \cdot h \quad? $$


This is a follow-up on this question.


Update


I revisited the problem and came up with a more elegant implementation of the faster Dot function.


FastDot[a_,b___]:=a.b;
FastDot[a_,b_,rest__]:=a.b.FastDot[rest];

FastDot@@tab // AbsoluteTiming // First



0.006545




Answer



For a wide variety of applications, the cost of doing a scalar product is rarely linear in the complexity of the multiplicands. Furthermore, the complexity of a product is usually larger than the complexity of the inputs. This can range from the simple case of multiplying two $n$-bit integers to get a $2n$-bit sum, to the horrible case of multiplying two sparse polynomials with $n$ terms each and getting a polynomial with $n^2$ terms.


The product of two matrices, of course, involves doing lots of scalar products, and correspondingly the product matrix has entries of greater complexity than the inputs. In your example, the scalar sums involved in taking a matrix product are increasing the complexity of your matrix entries too.


Since the costs aren't linear, the cost of chained multiplications can vary wildly depending on the order. A simple method that often gets nearly optimal performance is to try and balance the products: e.g. by always multiplying the two least complex terms of the list.


Grouping terms as you've done achieves this. Doing the products in order, however, is pretty much the worst case scenario.





Addendum: the sparse polynomial example maybe wasn't such a good choice, because in the typical case, the cost of computing the product is linear in the complexity of the output. But I think the main idea is still relevant in this case because you're doing the additions too.


Also, in the case of sparse polynomials, usually the game is to try and maintain the sparseness as long as possible, before products have so many terms they have to be considered dense. Generally there isn't much you can do to maintain sparsity, but what little you can do in a generic way amounts again to balanced products.


Comments

Popular posts from this blog

plotting - How to draw lines between specified dots on ListPlot?

I would like to create a plot where I have unconnected dots and some connected. So far, I have figured out how to draw the dots. My code is the following: ListPlot[{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4,13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full] I have thought using ListLinePlot command, but I don't know how to specify to the command to draw only selected lines between the dots. Do have any suggestions/hints on how to do that? Thank you. Answer One possibility would be to use Epilog with Line : ListPlot[ {{1, 1}, {2, 2}, {3, 3}, {4, 4}, {1, 4}, {2, 5}, {3, 6}, {4, 7}, {1, 7}, {2, 8}, {3, 9}, {4, 10}, {1, 10}, {2, 11}, {3, 12}, {4, 13}, {2.5, 7}}, Ticks -> {{1, 2, 3, 4}, None}, AxesStyle -> Thin, TicksStyle -> Directive[Black, Bold, 12], Mesh -> Full, Epilog -> { Line[ ...

calculus and analysis - Integral of the Sinc product

Let us consider the following integral $$ B_n = \int_0^\infty \prod_{k=1,3,5,\dots}^n\frac{\sin (x/k)}{x/k}dx $$ By definition, Sinc[x] == Sin[x]/x , therefore B[n_?OddQ] := Integrate[Product[Sinc[x/k], {k, 1, n, 2}], {x, 0, Infinity}] B /@ Range[1, 13, 2] {Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2, Pi/2} OK, everything is fine. But... B[15] 467807924713440738696537864469 Pi/935615849440640907310521750000 What's going on? Answer As Eckhard wrote in comments B[n] is the n-th Borwein integral . (The letter B was not accidental :) ) This funny properties of Borwein integrals is related to the Fourier transform of Sinc function FourierTransform[Sinc[x], x, k] 1/2 Sqrt[Pi/2] (Sign[1 - k] + Sign[1 + k]) Plot[%, {k, -2, 2}, Filling -> 0] which is the box function. The result is $\pi/2$ while the sum $$ 1/3+1/5+\dots+1/n $$ B_n = \frac{\pi}{2} - \pi \bigg(\sum_{k=3,5,\ldots}^n\frac{1}{k} -1\biggr)^\frac{n-1}{2}\prod_{k=3,5,\dots}^n\frac{k}{k-1}. $$ For $n=15$ it is equal to $$ \frac{46780...

list manipulation - Selecting multiple columns from a matrix?

Sample data: data = { {{2013, 1, 1}, 24.13, 167.67, 231.82}, {{2013, 1, 2}, 32.15, 170.92, 225.99}, {{2013, 1, 3}, 35.43, 172.68, 221.67}, {{2013, 1, 4}, 36.73, 173.05, 218.32}, {{2013, 1, 5}, 58.19, 165.96, 197.05}, {{2013, 1, 6}, 69.99, 163.50, 187.52}, {{2013, 1, 7}, 71.37, 154.21, 175.58}, {{2013, 1, 8}, 72.51, 149.66, 163.25}}; I want a DateListPlot with three graphs, so for a matrix formed by columns 1 and 2, one for columns 1 and 3, and 1 for columns 1 and 4. At the moment I'm using this code: data2 = Transpose[{data[[All, 1]], data[[All, 2]]}]; data3 = Transpose[{data[[All, 1]], data[[All, 3]]}]; data4 = Transpose[{data[[All, 1]], data[[All, 4]]}]; DateListPlot[{data2, data3, data4}, Joined -> True, Filling -> {3 -> {1}}] but I have a hunch that this can be done more efficiently. I don't like the Transpose s in particular. Any ideas? edit (for extra credit) What if I need to multiply the second column by 2, which in my solution is simp...