0
$\begingroup$

I have to solve a nonlinear (trigonometric) equation (that always has only one solution) $$f(x)=0$$ where function $f: D \subset \mathbb{R} \to \mathbb{R}$ is strictly increasing. I used the MATLAB function fsolve with the "trust-region-dogleg" method to solve the equation and the result is fine.

I would like to know the computational complexity of the algorithm used by MATLAB (i.e. trust-region method) in my case. Can I say that the CPU's computational time for solving such problem is the complexity of the algorithm?

I very much appreciate any answer or suggestion!

$\endgroup$
5
  • $\begingroup$ When you say that $f$ is strictly increasing, this seems to imply that $D$ is ordered. Is $D$ a subset of the real line? $\endgroup$
    – Servaes
    Commented Aug 30, 2019 at 8:26
  • $\begingroup$ Yes, actually, the set $D$ is $D := [0~a]$ where $a > 0$, so $D$ is a subset of $\mathbb{R}$. I have edited the question. $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 8:31
  • $\begingroup$ @Rodrigo de Azevedo: My function comprises of some basic sine and cosine functions. $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 9:34
  • 1
    $\begingroup$ It may be a good idea to post at scicomp.stackexchange.com too. Cross-link the questions, please. $\endgroup$ Commented Aug 30, 2019 at 9:42
  • $\begingroup$ Thanks @Rodrigo de Azevedo for your recommendation. I never know that forum before. But I think I have an answer now so is a cross-link needed? $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 9:58

1 Answer 1

1
$\begingroup$

You can have a grasp on the required time by comparing execution times under different conditions.

For instance, what happens if $D$ was twice the dimension, or you required twice the precision?

Let's put a simple example: adding two binary numbers $a,b$ of length $k$ requires $\mathbb{O}(k)$ operations to be computed. But $k$ is roughly $\log_2{a}$, so you can say the computation is $\mathbb{O}(\max{(\log_2{a},\log_2{b})})$

Note that, if we work with $a+1$ and $b+1$ rather than $a$ and $b$, we don't expect to need any extra opreations, except in the case one of them happens to be $111....111$ (or $999...999$ if we work in decimal)

If we need numbers with an extra digit (like $2a$ and $2b$), we will need one more operation. If we need numbers twice as long (like $a^2$ and $b^2$) we will need twice as many operations. Note that this fits well into the log-order complexity, since:

$$\log{(x+1)} \cong \log{(x)}$$ $$\log{(2x)} \cong 1+ \log{(x)}$$ $$\log{x^2} = 2 \log{(x)}$$

This types of relationships is what we usually check to find computationanl complexity in practice. Note that time is to some extent proportional to the number of basic operations (bit-additions), so we can use time as a "proxy" and work with it instead. That's why I suggest to check what happens when you have one more variable or twice as many variables in order to grasp the relationship between execution time and number of variables.

EDIT: Now that we know $D \subset \mathbb{R}$ the number of variables comparison does not apply. But you may want to use the complexity of $f$ (for example, adding a few degrees is $f$ is a polynomial), or the precision of the solution

$\endgroup$
6
  • $\begingroup$ Thanks David! I understood that the algorithm complexity should be performed by counting the total basic operations. However, in this case, I used the function fsolve of MATLAB so I don't know the algorithm in detail. $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 8:33
  • 4
    $\begingroup$ @lyhuehue01 : You can add a print statement in the function $f$, for instance printing the argument it is called with. Also, there should be an option to get an info object in the result of fsolve that contains the number of function evaluations, Jacobian computations etc. $\endgroup$ Commented Aug 30, 2019 at 8:52
  • $\begingroup$ Thanks @LutzL! That is a good point! But I think the number of function evaluations, Jacobian computations will vary with different initial guess of the solution, so we cannot know the complexity of the algorithm in general. Is it correct? $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 9:26
  • 1
    $\begingroup$ @lyhuehue01 When there are many factors that can vary the output (for example if the method is stochastic), I would repeat the execution a few times under slightly different conditions and use some statistics on the results (it may be good enough to just work with the average time if differences are not big) $\endgroup$
    – David
    Commented Aug 30, 2019 at 9:28
  • $\begingroup$ Thanks @David! Now I understood the idea of your answer. I think in my case, since I know the solution from the solver and the range of the variable $x$, I can gradually vary the initial guess of $x$ away from the solution and output the computational time. If we assume that the distance between the initial guess and the solution is proportional with the computation time, then we can derive the complexity of the algorithm. But I think it is quite rough and not reasonable to assume so. $\endgroup$
    – lyhuehue01
    Commented Aug 30, 2019 at 9:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .