4
$\begingroup$

This is my first time asking a question here, so I may not be asking this in the right place. I am trying to find the roots of a monotonic function with as few function evaluations as possible.

I have approximated a manifold with a piece-wise defined polynomial. The manifold is periodic and so I am only considering its unit cell (one period). I split the unit cell, in general a parallelogram but in this case a square, into triangles.

enter image description here

I then approximate each sheet of the manifold within each triangle with a unique quadratic polynomial.

enter image description here

I would like to find the root that satisfies the equation \begin{equation} \sum_{i}^{\mathrm{sheets}} \sum_{j}^{\mathrm{triangles}} \int p_{i,j}(x,y) \, \mathrm{d}C_{i,j} - A = 0 \end{equation} where $i$ is a sum over the sheets of the manifold, $j$ is a sum over the triangular tiles, $p_{i,j}$ is the second degree polynomial approximation of the manifold's $i$th sheet within the $j$th tile, and $C_{i,j}$ is the region within a level curve of the polynomial approximation of the manifold's $i$th sheet within the $j$th tile. Here is a plot of the $C_{i,j}$ for each triangle and sheet for some estimate of the root.

enter image description here

Said another way, I would like to find an isovalue where the area within the level curves of the polynomials, regions where the polynomials are less than the isovalue, is some predetermined value $A$.

At the moment I am using the bisection method, which is very slow because at each iteration it takes a significant amount of time to interpolate the manifold and then calculate the level curves and their containing areas. I may have hundreds of triangles and tens of sheets.

I also tried the regular falsi method but ran into cases where its convergence was worse than the bisection method.

$\endgroup$
13
  • $\begingroup$ Have you tried using marching triangles? $\endgroup$ – nicoguaro Jan 10 '19 at 23:19
  • $\begingroup$ I'm not sure I understand. I thought marching triangles was an algorithm for refining boundaries and small features. Can it be used to find roots? $\endgroup$ – jerjorg Jan 10 '19 at 23:33
  • $\begingroup$ I meant marching squares $\endgroup$ – nicoguaro Jan 10 '19 at 23:37
  • $\begingroup$ I haven't tried either because, as far as I know, those aren't root finding algorithms. $\endgroup$ – jerjorg Jan 11 '19 at 0:41
  • 2
    $\begingroup$ Clearly for you to arrive at a fast solution for this problem, you need to make the computation of the area for the level curves across all the manifolds more efficient. Bisection itself is going to be pretty fast if your function evaluations are efficient, so changing the root finding algorithm will likely be not be super useful. To me, one needs to use geometry information from each triangle and manifold to divide and conquer this problem to make function evaluations for the area much cheaper and try to avoid computing level curves whenever necessary. I'll lay out some ideas later. $\endgroup$ – spektr Jan 12 '19 at 2:53
1
$\begingroup$

It seems your main concern is bracketing the root in as few iterations as possible, since each iteration is costly. In some cases you have found the regula falsi method to be unreliable, suggesting the bounds on the root may be large or the function cannot be linearly approximated easily. To handle such cases without being significantly slower than bisection, you may want to try Brent's method. It uses a combination of bisection and concepts similar to the regula falsi method to give faster convergence when possible.

If you are certain the root should be simple, and Chandrupatla's method could be used instead. In my experience it tends to be faster than Brent's method when initial iterations benefit most from bisection.

If you do not need this much speed, the Illinois method may also suffice. It's a modification of the regula falsi method which greatly improves the rate of convergence and reliability. Though not as fast/reliable as the above algorithms, it is much simpler.

$\endgroup$

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.