Is there any algorithm to determine the minimum number of multiplication(division) of a specific expression? and the optimal expression form for implementation?

For example, given values of $\cos\alpha, \sin\alpha$, $\cos\beta, \sin\beta$ and $\cos\theta,\sin\theta$, what is the minimum number of multiplication in order to obtain numerical matrix:

enter image description here

How to obtain the final optimal expression (codes) for implementation?

  • 1
    $\begingroup$ This sounds like a potential case of premature optimization. Do you have a working implementation and some profiling or instrumentation that indicates that computing this matrix is a bottleneck in your program? $\endgroup$ – Bill Barth Jan 26 '15 at 13:58
  • $\begingroup$ This matrix appears in the objective function of a stochastic optimization; in order to reach a global convergence, there will be tens of millions of evaluation. Such implementation is slower than another equivalent objective function for the same problem, I am just curious whether similar issue is critical. $\endgroup$ – LCFactorization Jan 26 '15 at 14:08
  • $\begingroup$ Is there a difference between the LaTeX/MathJax version of your matrix and the image? Maybe you should remove one of them. Unfortunately the LaTeX version renders very wide, overwriting some of the right column text, so you might consider keeping only the image if they are the same (or shrinking the LaTeX font). $\endgroup$ – Bill Barth Jan 26 '15 at 14:21
  • 1
    $\begingroup$ Which language are you using? At least in Python, multiplication is really at same speed as addition. And I think computers nowadays usually can do * very quick. (Division is slower) Maybe your bottleneck is really sin and cos? Have you tried cache common terms in your entries? $\endgroup$ – jf328 Jan 26 '15 at 16:33
  • 2
    $\begingroup$ Some of those trig formulas can be simplified. For example, $\cos^2 - sin^2 + 1 = cos^2 + (1 - sin^2) = 2cos^2$. Also some double-angle formula manipulations can be done. $\endgroup$ – Nick Alger Jan 26 '15 at 17:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.