[lmi-commits] [lmi] odd/brent 662390c 11/11: Test Brent's method with Chandrupatla's IQI criterion

[Greg Chicares]

branch: odd/brent
commit 662390cc9dab0f441d049ab717a3d56a74cd25e1
Author: Gregory W. Chicares <gchicares@sbcglobal.net>
Commit: Gregory W. Chicares <gchicares@sbcglobal.net>

    Test Brent's method with Chandrupatla's IQI criterion
    
    [Terminology: in Brent's method, 'b' and 'c' bracket a root, and the
    third point for IQI is a prior value of 'b' on the same side of that
    root.]
    
    Brent (AfMWD, page 51) said:
    | When inverse quadratic interpolation is used the interpolating
    | parabola cannot be a good approximation to f unless it is single-
    | valued between (f, f(b)) and (c, f(c)). Thus, it is natural to
    | accept the point i if it lies between b and c, and up to three-
    | quarters of the way from b to c: consider the limiting case where
    | the interpolating parabola has a vertical tangent at c and
    | f(b) = - f(c).
    
    The first of those two quoted sentences is a mathematical idea, while
    the second describes the algorithm. How consonant are they?
    
    For the present experiment, lmi's full system test was run, with
    customizations in earlier commits that dump every solve iteration
    to a file, using this command (without 'make' parallelism):
      rm /opt/lmi/test/trace.txt; time make system_test
    This test, using decimal_root() as in HEAD, took a total of 7737
    function evaluations. Then decimal_root() was changed to use
    Chandrupatla's criterion for accepting an IQI iterate instead of
    Brent's criterion--only the current commit, and nothing more.
    
    Before comparing the results, it was conjectured that Brent's criterion
    might be half of Chandrupatla's, which precisely implements the first
    sentence quoted above, whereas Brent ignores a vertical tangent at 'b';
    and that using both Chandrupatla conditions together would improve
    Brent's algorithm, by testing that sentence's principle rigorously.
    
    The result was surprising: 8578 function evaluations, about eleven
    percent worse. Before and after run times for a serial system test:
      make system_test 2>&1  77.67s user 66.92s system 89% cpu 2:40.77 total
      make system_test 2>&1  81.15s user 69.99s system 90% cpu 2:47.41 total
    The difference of about seven seconds would imply that solves account
    for about 70 of the 160 clock seconds taken by the system test, which
    seems reasonable.
    
    This command:
      for z in I B L Q b ; \
        do grep --count " $z " /opt/lmi/test/trace_b.txt | sed -e"s/^/$z /";
      done
    counts how many times each technique was used. Tabulating the results:
    
         brent   chand
      I    870     870   initialize (evaluate given bounds)
      B     56      70   bisect while dithering close to a root
      L   3303    3708   linear (secant method)
      Q   1408     636   inverse quadratic interpolation (IQI)
      b   2100    3294   bisect when IQI iterate rejected
    
    The complete Chandrupatla criterion rejects most of the IQI iterates
    that Brent's criterion accepts: most of them "cannot be...good
    approximation[s]" according to Brent's first sentence above, but this
    practical experiment suggests otherwise. Thus, the Brent quote is not
    a necessary principle followed by an approximate realization; rather,
    it is a good heuristic preceded by an approximate rationalization.
    
    Denouement: Brent's heuristic doesn't coincide with either end of
    Chandrupatla's two-ended conditional. Three boolean conditions have been
    recorded in the trace files:
     - convergence is fast enough--bisection NOT forced by Brent
     - Brent's IQI criterion
     - Chandrupatla's IQI criterion
    and the boolean triplets are analyzed by this command:
    
      for z in 000 001 010 011 100 101 110 111 ; do
        grep --count " $z " /opt/lmi/test/trace_b.txt | sed -e"s/^/$z /";
      done
    
    for the "brent" and "chand" runs discussed above:
    
        brent      chand
      000 2778   000 2621
      001    0   001    0
      010  235   010  253 B accepts, C rejects
      011    0   011    0
      100   13   100   11 both reject
      101    0   101    4 B rejects, C accepts
      110 4183   110 5057 B accepts, C rejects
      111  528   111  632 both accept
---
 zero.hpp | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/zero.hpp b/zero.hpp
index c75bd90..281bd3c 100644
--- a/zero.hpp
+++ b/zero.hpp
@@ -33,7 +33,7 @@
 #include <limits>
 #include <ostream>
 
-//#define USE_CHANDRUPATLA_IQI_CRITERION
+#define USE_CHANDRUPATLA_IQI_CRITERION
 
 template<typename T>
 inline T signum(T t)