# Speed up replacement using Rule Dispatch Associtation

I knew that this has asked many times, but I hope there is something more could be done to speed this up.

The expression kappa is here.

Get["expr.txt"] (* read kappa into the notebook *)
kappa (* just to check *)
pars = Variables[Level[kappa, -2]]
npars = Length[pars]

DD1 = D[kappa, {pars}]
Dimensions[DD1]


The dimension is "small" here, compared to what I am actually doing. Since a symbolic rank is almost impossible to get. So I am simulating some random values to determine it's "true" rank.

rules = Thread[pars -> RandomReal[{-3, 3}, Length[pars]]]
AbsoluteTiming[DD1 /. rules;]


{20.514036, Null}

disp = Dispatch@rules
AbsoluteTiming[DD1 /. disp;]


{5.413209, Null}

assoc = Association@rules
AbsoluteTiming[DD1 /. assoc;]


{4.789208, Null}

The dimension of the matrix is only {511,30} .Dispatch and Association does make a significant difference in this case. However, it is still too long for a {1024,100} matrix.

Is there something more could be done to speed it up?

I tried something like

AbsoluteTiming[ParallelEvaluate[DD1 /. assoc;]]
AbsoluteTiming[ParallelEvaluate[DD1 /. disp;]]
AbsoluteTiming[ParallelEvaluate[DD1 /. rules;]]


But there is an error:

ReplaceAll::reps: {assoc} is neither a list of replacement rules nor a valid dispatch table, and so cannot be used for replacing.

ReplaceAll::reps: {disp} is neither a list of replacement rules nor a valid dispatch table, and so cannot be used for replacing.

ReplaceAll::reps: {rules} is neither a list of replacement rules nor a valid dispatch table, and so cannot be used for replacing.

For this example, each run still takes about 5 seconds, and I will run each of the matrix using 5 sets of values, so it's about 20 seconds for each matrix. This is still not very efficient.

Any suggestions?

• I think this is a dead-end in terms of having a general answer. Suggestions and tricks that might help speed this up will likely depend on how the kappa expression is obtained, about which you don't say anything. We're effectively being asked to analyze and optimize a blackbox expression. You should perhaps consider stepping away from Mathematica for a bit and turning to mathematics to try and simplify the problem. – rm -rf Jan 4 '15 at 1:26
• Note that the rank of your matrix $X$ is bounded by the number of columns which is much less than the number of rows. Does your formulation permit an easy calculation of $X^\top X$ which is only $30\times 30$ (or $100\times 100$ in the bigger one)? If so, then you can try and compute the rank of that, as it should be the same as the rank of $X$. Assuming that all elements of $X\in \mathbb{R}^{n\times m}, n \gg m$ take roughly the same time to compute and the time taken to compute an element of $X$ is the same as $X^\top X$, then you've gone from having to compute $O(n m)$ elements to $O(m^2)$. – rm -rf Jan 4 '15 at 1:26
• @rm-rf I always know that but I never thought about using DD1^T*DD1. Would that not change the rank of the matrix? Is there a theorem behind this? – Chen Stats Yu Jan 4 '15 at 1:30
• @rm-rf I have used Dnew = Transpose[DD1].DD1; to compute the 30x30 matrix. However, i think AbsoluteTiming[Dnew /. assoc;] or AbsoluteTiming[Dnew /. disp;] takes significantly longer to process. That's a bit odd. And it almost crashed my laptop. The memory usage go up to 4GB rapidly. – Chen Stats Yu Jan 4 '15 at 1:55
• I'm not surprised. It's not unconceivable that Transpose[DD1].DD1 is more complex (in terms of leaf count and computations involved) than just DD1. What I said in my previous two comments was that you should go back to the drawing board and see if you can use mathematics to simplify the problem before throwing it to Mathematica. Since we don't know the origins of your problem or how you arrive at kappa, we cannot help you there (nor is this necessarily the site for that). – rm -rf Jan 4 '15 at 4:02