2
$\begingroup$

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?

$\endgroup$
7
  • 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, 2015 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$ Jan 26, 2015 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, 2015 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, 2015 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, 2015 at 17:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.