# Efficient root finding algorithm for monotonic function

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.

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

I would like to find the root that satisfies the equation $$$$\sum_{i}^{\mathrm{sheets}} \sum_{j}^{\mathrm{triangles}} \int p_{i,j}(x,y) \, \mathrm{d}C_{i,j} - A = 0$$$$ 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.

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.

• Have you tried using marching triangles? Jan 10 '19 at 23:19
• 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? Jan 10 '19 at 23:33
• I meant marching squares Jan 10 '19 at 23:37
• I haven't tried either because, as far as I know, those aren't root finding algorithms. Jan 11 '19 at 0:41
• 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. Jan 12 '19 at 2:53