4
$\begingroup$

Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and webpages online, they all basically say "Here's the equation. Solve for $p$. It equals (whatever). Moving on now to the integral..." without explaining how they solved the equation.

If I had to figure it out I could use a binary search but I imagine there is a more mathematical way to get an exact answer.

It is not at all obvious to me how you're supposed to solve for p.

That is:

$$ a_1 b_1^p + a_2 b_2^p + a_3 b_3^p + \dots + a_k b_k^p = 1, $$

Where all $a_i$ terms are positive and all $b_i$ terms are fractional ($0 < b_i < 1$).

How can you solve for $p$ by hand?

$\endgroup$
1
  • $\begingroup$ You might get lucky and "see" what $p$ satisfies the equation and thus "solve by hand". Most of the time you will have to use a numerical method like Newton's $\endgroup$ – vonbrand Jan 15 '16 at 20:56
3
$\begingroup$

You don't solve for $p$ by hand. You use a computer to get a numerical solution. In general, there is no reason to expect that $p$ have some nice form.

Since the left-hand side of the equation is monotone decreasing, there is at most one solution. Furthermore, when $p \to -\infty$ the left-hand side tends to $\infty$, whereas when $p \to \infty$ it tends to $0$. This shows that a solution does exist. The computer can find it using standard root-finding methods.

This kind of situation is encountered in many other places in computer sciences. Here are two examples:

  • The approximation ratio of the Goemans–Williamson algorithm is $$ \min_{0 \leq \theta \leq \pi} \frac{2}{\pi} \frac{\theta}{1-\cos\theta} \approx 0.878, $$ which doesn't have a closed form. Surprisingly, assuming the unique games conjecture, this approximation ratio is the best that polynomial time algorithms can achieve in the worst case.

  • Running times of fast matrix multiplication algorithms are of the form $O(n^\rho)$ where $\rho$ is in simple cases the solution of an equation similar to the one you describe, and in other cases the solution of a much more complicated optimization problem. Again, there is no closed form for $\rho$ in most cases (other than Strassen's algorithm, perhaps).

$\endgroup$
4
  • $\begingroup$ So in practice you would not use something like binary search necessarily? Or are you saying you would? I can't tell if this counts as a "numeric" method but I assume it does. $\endgroup$ – AJJ Jan 15 '16 at 21:08
  • $\begingroup$ There are several numerical methods for solving equations. Your computer algebra system will use one of them to solve the equation for you. I personally don't care which. $\endgroup$ – Yuval Filmus Jan 15 '16 at 21:09
  • $\begingroup$ What does the computer algebra system use to solve the equation? (e.g. Wolfram Alpha or Mathematica) $\endgroup$ – AJJ Jan 15 '16 at 21:09
  • 1
    $\begingroup$ It depends on the computer algebra system and on its user. If you're interested, take a course in numerical analysis or read the source code of SAGE. The phrase numerical methods means that the computer doesn't use a formula. $\endgroup$ – Yuval Filmus Jan 15 '16 at 21:10

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.