# root of 1d monotone picewise linear function

 Register Blogs Members List Search Today's Posts Mark Forums Read

 January 29, 2009, 02:43 root of 1d monotone picewise linear function #1 bill Guest   Posts: n/a Do you knowe a fast method to find root of a monotonice picewise linear function? basically it's easy to compute, however a fast method is desired, any reference is very appreciated

 January 29, 2009, 22:14 Re: root of 1d monotone picewise linear function #2 Ananda Himansu Guest   Posts: n/a I am no expert, so I cannot cite references to the absolute fastest method, if such exists. You could use parallel processing, especially shared-memory such as in GPGPU computing. However, I assume you seek a serial algorithm. I also assume you are unable to amortize the initial cost of constructing an inverse lookup function over the need for multiple queries (as in thermodynamic property inverse lookups). I also assume your function is C0 continuous (at the nodes or cell-interfaces) and that its values at the nodes are available, so that it is cheap to evaluate it as a function of the node index i. The hard part (if you have many cells in your domain) is to first locate the cell that contains the root. Given that the function is piecewise linear, the second phase of finding the precise root within that cell is trivial. In the second phase, you use f as a function of the spatial coordinate x within the cell. For the first phase, you should work directly with the function f as a discrete gridfunction of the node index i. This way, you avoid the cost of finding the interval that contains a given x (this latter is almost as expensive as the original problem and similar to it). For the first phase, you have a nonlinear function of the node indices (even if f were globally linear in the spatial coordinate x, if you had nonuniform mesh spacing, f would be a nonlinear function of i). I suggest a bracketing nonlinear rootfinding method that does not use derivative information, such as Bisection, False Position or Ridder's Method (see the Numerical Recipes book by Press et al). The latter two methods will be faster than bisection on most well-behaved functions. The bracketing property is convenient since you are trying to home in on the cell that contains the root. You retain the real number arithmetic of the algorithm, even though the independent variable i takes only integer values. You will have to modify the root finder slightly in order to round the estimated real number root up or down to the nearest integer node number such that the root remains bracketed. You must also modify the convergence test. Assuming that the root is initially bracketed by the endpoints of your domain, the test for convergence of the first phase will be when the latest two (rounded) roots differ by unity, i.e., they are neighboring node indices which are endpoints of the cell containing the exact root. Then you execute the second phase to find the exact root.

 January 29, 2009, 23:09 Re: root of 1d monotone picewise linear function #3 Ananda Himansu Guest   Posts: n/a An alternative method for the first phase would be to work with the square of the given function and minimize that using a derivative-free downhill type optimizer. Since your function is monotonic, there will be no minima other than the desired root. Unsure whether this would be any faster or slower than the approach of my previous post.

 January 30, 2009, 04:43 Re: root of 1d monotone picewise linear function #4 Jed Guest   Posts: n/a This is way more complicated than necessary. You have a sorted (due to monotonicity) array of function values f and a corresponding sorted array of node coordinates x. A single function evaluation f(s) involves searching x for s to find the index (binary search is optimal in the general case), then doing piecewise linear interpolation. This search is just as expensive as finding the region where the root occurs using binary search on f. Assuming nothing lucky is in cache and no page faults are triggered, this will take about 2 microseconds on modern hardware for an array of 1 billion double precision values (8 GB).

 January 30, 2009, 07:57 Re: root of 1d monotone picewise linear function #5 Ananda Himansu Guest   Posts: n/a Isn't that what I said? I was more verbose, though

 January 30, 2009, 15:20 Re: root of 1d monotone picewise linear function #6 Jed Guest   Posts: n/a Yes, although I would definitely not suggest False Position since it has `O(n)` worst case runtime for a function/sampling that is not so pathological. Ridder's method has an easily achivable worst case that is double bsearch. Worst case for Brent's method is basically the same as bsearch. Also note that once the relevant part of the array is in cache (guaranteed for the last thousand values or so), the overhead of casting and division is significant compared to function evaluation (array index). Basically, since function evaluation becomes so cheap once you enter the neighborhood where higher-order convergence applies, I would advise sticking with bsearch. If the function is sufficiently well-behaved at the global scale and really huge, you might be able to beat bsearch by using Brent's method early (when function evaluation is expensive due to memory latency) and switching to plain bsearch once the interval size is narrowed down. I think you'd be very hard-pressed to find a case where this was worth the bother.

 January 30, 2009, 17:20 Re: root of 1d monotone picewise linear function #7 Ananda Himansu Guest   Posts: n/a Yes, I agree that binary search (bisection) is well-behaved, and there is likely not much to be gained from Ridder's or Brent's, since here we are not concerned with asymptotic convergence rate (which would matter if you were looking for high accuracy in a real root). The original poster did not specify how large his dataset is, and he asked for a really fast method.

 February 1, 2009, 05:40 Re: root of 1d monotone picewise linear function #8 bill Guest   Posts: n/a valuable commnets, thanks Ananda and also Jed (i missed to track this thread) i have forgotten to notify that my domain is one dimensional, so root of an x-y function is desired. > "I suggest a bracketing nonlinear rootfinding method that does not use derivative information, such as Bisection, False Position or Ridder's Method " thanks, i currently use bisection method it works rubost but when we do not have uniform distribution of break-points its convergence is slow, a simple solution can be median based bisection, i.e., break-points set bisection instead of interval bisection. However, finding set medians is expensive and function of number of breakepoints (note that breakepoints are known for me), am i correct? is there method to find median vry fast, or way to do bi-section based on breakpoints distribution? it seems that i should try "False Position" and "Ridder" methods you mentioned as well. if you have any other commnet, its very wellcome cheers -bill

 February 1, 2009, 15:25 Re: root of 1d monotone picewise linear function #9 Ananda Himansu Guest   Posts: n/a I do not understand your use of the terms bisection, set, interval, and median. Therefore, I am unsure exactly what you are currently doing. Perhaps you can explain exactly what you do in terms of x(i), y(i), i = 1,...,n, where i is the node index. I particularly fail to follow what you mean by "interval bisection" versus "break-points set bisection". As Jed and I both pointed out, during the first phase (location of the root-containing cell), you should work with y as a function of i, and not involve x at all. There should be no "interval bisection" involved, if "interval" refers to an interval of the x domain. You should be doing bisection on the i bracket, which (since i is an integer) amounts to binary search as Jed referred to it. In bisection (binary search), what you do coincides precisely with finding the median observation (because your y data are monotonic, i.e., ordered). If the current bracket has iL=J as the left end and iR=J+2K as the right end, then the bisection point is exactly the median point iM=J+K+1. This is trivial to calculate as iM=iL+(iR-iL+2)/2. Then y(iM) is the median observation which will replace either the left end or the right end of the current bracket. Note that if rather iR=J+2K-1, then as I previously said, you will have to round iM to either J+K or J+K+1, instead of taking the average observation of y(J+K) and y(J+K+1). It so happens that x(iM) is also the median x-observation (since x is ordered with respect to i), but as I said this should play no part in your algorithm. The bisection method Jed and I described may indeed not be the fastest method. Since you say your function y is monotonic, I suspect that False Position or Ridder's Method or Brent's Method may be significantly faster in terms of number of iterations required. However, as Jed pointed out, they involve quite a bit more arithmetic per iteration than binary search does. You may have to try the various methods in practice, to see which is fastest for your class of functions.

 February 1, 2009, 15:54 Re: root of 1d monotone picewise linear function #10 bill Guest   Posts: n/a currently i used Brant method in numerical recipe codes, it works better than bisectin, is satisfactory so no need for further refinement, thanks PS: regarding to set bisection: for picewise linear graph with "n" segment we have 2n breake points, root is located within two consecutive breakpoints, set bisection means to use median of breakpoint set as boundary of new interval, so its worst case convergence is explicitely known as a function of n, by set bisection we finally reach to a segment in which zero occured so just do an interpolation, main drawback is to find set median which is expensive

 February 2, 2009, 01:37 Re: root of 1d monotone picewise linear function #12 bill Guest   Posts: n/a Ananda, thanks, interesting to follow first i should say that in my problem cost of one function evaluation is high, actually my problem is dual of a large scale minimazation with large number of parameters. In dual setting we have one objective functional to be minimized with one unknown parameter x (actually lagrange multiplier of sub-problem) and my actual parameters are now known within the solution of this sub-problem which is matter of this thread. I have 2n interval in which function is picewise linear, so 2n-1 breakpoints. Breakpoints are a-priori known, *however* they are not sorted in an ascending order. in interval bisection method i used, i bisect x-coordinate to shrink interval and it work well (i can not understand what you say about my wrong) however, if we have non-uniform distribution of breakpoints, and concenteration of breakpoint near a specific point, then interval bisection methods may takes lot of function evaluation to explor concentration region. in contrast set bisection method, always remove half of breakpoints so its upper cost is a-priori known as a function of n. But to find bisection point of set we need to find median (at each cycle) and remove pointes that are either smaller or larger than median. This need one sort procedurec O(2n log 2n) not simply "one multiplication, one addition, one division" you said (becasue *breakponts positions* are not available in an ascending order) exactly the reverse scenario is present in contrast to your understanding, i.e. to find interval bisection no scanning is needed it is juast avaraging between current set endpoints (you may forget that x- is continuous) if you have additional commnet, i'm interested to hear it.

 February 2, 2009, 15:21 Re: root of 1d monotone picewise linear function #14 bill Guest   Posts: n/a Ananda i got my answer and do not like to take your time more. so lets to close this thread and save energy for future. thanks for all of your advices. Best PS: c^0 assumtion hold for my case

 February 2, 2009, 17:51 Re: root of 1d monotone picewise linear function #15 Ananda Himansu Guest   Posts: n/a You are welcome, bill. Glad you were able to get satisfactory convergence.

 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is OffTrackbacks are On Pingbacks are On Refbacks are On Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post ivanyao OpenFOAM Running, Solving & CFD 1 October 12, 2012 09:31 Chrisi1984 OpenFOAM Installation 0 December 31, 2010 07:42 phsieh2005 OpenFOAM Bugs 25 February 9, 2010 05:37 skabilan OpenFOAM Installation 3 July 28, 2009 00:35 Rasmus Gjesing (Gjesing) OpenFOAM Native Meshers: blockMesh 10 April 2, 2007 14:00

All times are GMT -4. The time now is 20:43.