1 ////////////////////////////////////////////////////////////////////////////////////// 2 // This file is distributed under the University of Illinois/NCSA Open Source License. 3 // See LICENSE file in top directory for details. 4 // 5 // Copyright (c) 2016 Jeongnim Kim and QMCPACK developers. 6 // 7 // File developed by: Paul R. C. Kent, kentpr@ornl.gov, Oak Ridge National Laboratory 8 // Mark A. Berrill, berrillma@ornl.gov, Oak Ridge National Laboratory 9 // 10 // File created by: Paul R. C. Kent, kentpr@ornl.gov, Oak Ridge National Laboratory 11 ////////////////////////////////////////////////////////////////////////////////////// 12 13 14 // http://pathintegrals.info // 15 ///////////////////////////////////////////////////////////// 16 17 ///////////////////////////////////////////////////////////////////////////// 18 // // 19 // Adaptive Gauss-Kronrod integration // 20 // // 21 // This C++ version was written by Burkhard Militzer Livermore 02-20-02 // 22 // Based on the GNU scientific library // 23 // // 24 ///////////////////////////////////////////////////////////////////////////// 25 26 #ifndef _GKINTEGRATION_ 27 #define _GKINTEGRATION_ 28 29 #include <iterator> 30 #include <list> 31 #include "Standard.h" 32 33 class GK15 34 { 35 public: 36 static const int n = 8; 37 static const double xgk[n]; 38 static const double wg[n / 2]; 39 static const double wgk[n]; 40 }; 41 42 class GK21 43 { 44 public: 45 static const int n = 11; 46 static const double xgk[n]; 47 static const double wg[n / 2]; 48 static const double wgk[n]; 49 }; 50 51 class GK31 52 { 53 public: 54 static const int n = 16; 55 static const double xgk[n]; 56 static const double wg[n / 2]; 57 static const double wgk[n]; 58 }; 59 60 class GK41 61 { 62 public: 63 static const int n = 21; 64 static const double xgk[n]; 65 static const double wg[(n + 1) / 2]; 66 static const double wgk[n]; 67 }; 68 69 class GK51 70 { 71 public: 72 static const int n = 26; 73 static const double xgk[n]; 74 static const double wg[n / 2]; 75 static const double wgk[n]; 76 }; 77 78 class GK61 79 { 80 public: 81 static const int n = 31; 82 static const double xgk[n]; 83 static const double wg[n / 2]; 84 static const double wgk[n]; 85 }; 86 87 //////////////////////////////////////////////////////////////////////////////////////// 88 89 template<class F, class GKRule = GK31> 90 class GKIntegration 91 { 92 private: 93 class IntervalResult 94 { 95 public: IntervalResult(const double a_,const double b_,const double delta_)96 IntervalResult(const double a_, const double b_, const double delta_) 97 : a(a_), b(b_), result(0.0), err(0.0), delta(delta_){}; 98 double a, b, result, err, delta; 99 ErrorL()100 double ErrorL() const { return (delta ? err / delta : err); } 101 102 friend std::ostream& operator<<(std::ostream& os, const IntervalResult& ir) 103 { 104 os << "[a= " << ir.a << " b= " << ir.b << " result= " << ir.result << " error/L= " << ir.err / (ir.b - ir.a) 105 << " error= " << ir.err << " ]"; 106 return os; 107 } 108 }; 109 110 std::list<IntervalResult> ir; 111 F& f; // could be not const in case where calling f() actually modifies the object 112 bool relativeErrors; 113 114 public: GKIntegration(F & f_)115 GKIntegration(F& f_) : f(f_), relativeErrors(false) {} 116 SetAbsoluteErrorMode()117 void SetAbsoluteErrorMode() { relativeErrors = false; } SetRelativeErrorMode()118 void SetRelativeErrorMode() { relativeErrors = true; } 119 120 private: 121 // funnel all calls through this function and branch to specific n knot rule GK(IntervalResult & r)122 void GK(IntervalResult& r) { GKGeneral(GKRule::n, GKRule::xgk, GKRule::wg, GKRule::wgk, r); } 123 124 // handle all n knot rule with the passed in positions and weights GKGeneral(const int n,const double xgk[],const double wg[],const double wgk[],IntervalResult & r)125 void GKGeneral(const int n, const double xgk[], const double wg[], const double wgk[], IntervalResult& r) 126 { 127 const double center = 0.5 * (r.a + r.b); 128 const double halfLength = 0.5 * r.delta; 129 const double fCenter = f(center); 130 131 double resultGauss = 0; 132 double resultKronrod = fCenter * wgk[n - 1]; 133 134 if (n % 2 == 0) 135 { 136 resultGauss = fCenter * wg[n / 2 - 1]; 137 } 138 139 for (int j = 0; j < (n - 1) / 2; j++) 140 { 141 const int jtw = j * 2 + 1; // j=1,2,3 jtw=2,4,6 142 const double xx = halfLength * xgk[jtw]; 143 const double fval1 = f(center - xx); 144 const double fval2 = f(center + xx); 145 const double fsum = fval1 + fval2; 146 resultGauss += wg[j] * fsum; 147 resultKronrod += wgk[jtw] * fsum; 148 } 149 150 for (int j = 0; j < n / 2; j++) 151 { 152 int jtwm1 = j * 2; 153 const double xx = halfLength * xgk[jtwm1]; 154 const double fval1 = f(center - xx); 155 const double fval2 = f(center + xx); 156 resultKronrod += wgk[jtwm1] * (fval1 + fval2); 157 }; 158 159 /* scale by the width of the integration region */ 160 resultGauss *= halfLength; 161 resultKronrod *= halfLength; 162 163 r.result = resultKronrod; 164 r.err = std::abs(resultKronrod - resultGauss); 165 //r.err = pow(200.0 * std::abs(resultKronrod - resultGauss), 1.5); 166 // BMWrite(r); 167 } 168 PrintList()169 void PrintList() 170 { 171 std::cout << "/------------------------------------------\\" << std::endl; 172 int i = 0; 173 for (typename std::list<IntervalResult>::iterator p = ir.begin(); p != ir.end(); p++) 174 { 175 BMWrite2(i, *p); 176 i++; 177 } 178 std::cout << "\\------------------------------------------/" << std::endl; 179 } 180 181 //Print interval with maxium error per interval length 182 //(not with maximum error - this is on top of the list) PrintMax()183 void PrintMax() 184 { 185 typename std::list<IntervalResult>::iterator rMax(ir.begin()); 186 187 for (typename std::list<IntervalResult>::iterator r = ir.begin()++; r != ir.end(); r++) 188 { 189 if ((*r).ErrorL() > (*rMax).ErrorL()) 190 rMax = r; 191 } 192 193 BMWrite(*rMax); 194 } 195 CheckList()196 void CheckList() 197 { 198 if (ir.size() == 0) 199 return; 200 201 for (typename std::list<IntervalResult>::iterator p = ir.begin(); p != ir.end(); p++) 202 { 203 typename std::list<IntervalResult>::iterator pn = p; 204 pn++; 205 if (pn != ir.end()) 206 if (((*p).err) < ((*pn).err)) 207 { 208 PrintList(); 209 BMWrite2(*pn, *p); 210 ::error("Ordering problem in list"); 211 } 212 } 213 } 214 CheckError(const double err)215 void CheckError(const double err) 216 { 217 double errorSum = 0.0; 218 219 if (ir.size() > 0) 220 { 221 for (typename std::list<IntervalResult>::iterator p = ir.begin(); p != ir.end(); p++) 222 { 223 errorSum += (*p).err; 224 } 225 } 226 227 if (errorSum == 0.0) 228 { 229 if (err != 0.0) 230 error("CheckError", errorSum, err); 231 } 232 else 233 { 234 if (err / errorSum - 1.0 > 1e-8 && std::abs(err - errorSum) > 1e-14) 235 error("CheckError", errorSum, err, errorSum - err); 236 } 237 238 BMWrite4("PassedErrorCheck", errorSum, err, errorSum - err); 239 } 240 RecomputeError()241 double RecomputeError() 242 { 243 double errorSum = 0.0; 244 245 if (ir.size() > 0) 246 { 247 for (typename std::list<IntervalResult>::iterator p = ir.begin(); p != ir.end(); p++) 248 { 249 errorSum += (*p).err; 250 } 251 } 252 253 return errorSum; 254 } 255 Insert(const IntervalResult & r)256 void Insert(const IntervalResult& r) 257 { 258 // std::cout << "Inserting.." << std::endl; 259 // PrintList(); 260 261 if (ir.empty()) 262 { 263 ir.push_back(r); 264 return; 265 } 266 267 if (ir.back().err >= r.err) 268 { 269 ir.push_back(r); 270 return; 271 } 272 273 if (r.err >= ir.front().err) 274 { 275 ir.push_front(r); 276 return; 277 } 278 279 // size must be >=2 280 typename std::list<IntervalResult>::iterator p = ir.end(); 281 p--; 282 283 // p cannot become less the begin() because of check above 284 while (r.err > (*p).err) 285 p--; 286 287 // go one down because insert put the element before p 288 p++; 289 ir.insert(p, r); 290 // CheckList(); 291 } 292 Integrate(const double a,const double b,const double absError,const bool absErrorFlag,const double relError,const bool relErrorFlag,const bool andFlag)293 double Integrate(const double a, 294 const double b, 295 const double absError, 296 const bool absErrorFlag, 297 const double relError, 298 const bool relErrorFlag, 299 const bool andFlag) 300 { 301 ir.clear(); 302 303 // #define PRINT_IT 304 #ifdef PRINT_IT 305 std::cout << "Beginning integration" << std::endl; 306 #endif 307 308 double errorUnresolved = 0.0; 309 const int iterationMax = 30; 310 // double lengthMin = (b-a)*pow(0.5,iterationMax); 311 double lengthMin = ldexp(b - a, -iterationMax); 312 313 IntervalResult r0(a, b, b - a); 314 GK(r0); 315 double result = r0.result; 316 double err = r0.err; 317 double errLast = err; 318 319 ir.push_back(r0); 320 321 bool quitFlag; 322 do 323 { 324 // PrintList(); 325 326 // Test if the interval with the biggest error has already been subdivided 327 // the maximum number of times. If this is the case throw it out and print add 328 // this contribution to the 'unresolved' errors to be printed at the end 329 while (ir.size() > 0) 330 { 331 IntervalResult& rTest(ir.front()); 332 double lengthTest = rTest.delta; 333 if (lengthTest < lengthMin) 334 { 335 warning("KC:Interval was divided too many times", iterationMax, rTest.a, rTest.b, rTest.err, ir.size()); 336 // warning("KC:current result=",result,"error=",err); 337 if (absErrorFlag) 338 warning("Absolute accuracy = ", absError); 339 if (relErrorFlag) 340 warning("Relative accuracy = ", relError, "->absolute accuracy=", relError * std::abs(result)); 341 // this means there is a problem with the integrand->you could exit here 342 // exit(1); 343 errorUnresolved += rTest.err; 344 // PrintList(); 345 ir.pop_front(); 346 } 347 else 348 break; 349 } 350 // do you want to exit with a warning after the first unresolved sub-interval occurred? 351 if (ir.size() == 0 || errorUnresolved > 0.0) 352 break; 353 // or print as many as occur 354 // if (ir.size()==0) break; 355 356 IntervalResult& r(ir.front()); 357 358 double center = 0.5 * (r.a + r.b); 359 IntervalResult r1(r.a, center, 0.5 * r.delta); 360 IntervalResult r2(center, r.b, 0.5 * r.delta); 361 362 GK(r1); 363 GK(r2); 364 365 // must not use r after popping 366 result += r1.result + r2.result - r.result; 367 err += r1.err + r2.err - r.err; 368 369 #ifdef PRINT_IT 370 std::cout.setf(std::ios::scientific); 371 std::cout << "Refined [ " << r.a << " " << r.b << " ] err/L=" << (r1.err + r2.err) / (r.b - r.a) 372 << " error=" << err << std::endl; 373 #endif 374 375 // must remove old element first because new ones could move to top 376 ir.pop_front(); 377 378 Insert(r1); 379 Insert(r2); 380 381 // In rare events, the error decreases over may (>10) orders of magnitude 382 // during the refinement. Rounding errors from the beginning can prevent 383 // err from becoming small enough. Recompute err after a substantial decrease. 384 if (err < 1e-6 * errLast) 385 { 386 err = RecomputeError(); 387 errLast = err; 388 } 389 390 // CheckError(err); 391 // PrintList(); 392 393 const bool relOk = (err < relError * std::abs(result) || result == 0.0); 394 const bool absOk = (err < absError); 395 396 if (absErrorFlag && relErrorFlag) 397 { 398 quitFlag = andFlag ? (relOk && absOk) : (relOk || absOk); 399 } 400 else 401 { 402 quitFlag = absErrorFlag ? absOk : relOk; 403 } 404 405 } while (!quitFlag); 406 407 #ifdef PRINT_IT 408 PrintMax(); 409 #endif 410 411 if (errorUnresolved > 0.0) 412 { 413 warning("KC:Unresolved error sum=", errorUnresolved, "for integration interval", a, b); 414 warning("KC:--> Result=", result, "total error=", err, 415 "rel. error=", ((result != 0.0) ? err / std::abs(result) : 0.0)); 416 // if (absErrorFlag) warning("Absolute accuracy = ",absError); 417 // if (relErrorFlag) warning("Relative accuracy = ",relError, 418 // "->absolute accuracy=",relError*std::abs(result)); 419 } 420 421 // CheckList(); 422 #ifdef PRINT_IT 423 std::cout << "End integration" << std::endl; 424 #endif 425 double sum = 0.0; 426 int numIntervals = 0; 427 for (typename std::list<IntervalResult>::iterator p = ir.begin(); p != ir.end(); p++) 428 { 429 sum += p->result; 430 numIntervals++; 431 } 432 433 // if (numIntervals > 2000) 434 // std::cerr << "Number of intervals = " << numIntervals << std::endl; 435 436 double badSum = std::abs((result - sum) / sum); 437 if ((badSum > 1.0e-7) && (std::abs(result - sum) > absError)) 438 { 439 std::cerr << "absError tolerance = " << absError << std::endl; 440 std::cerr << "Percent error = " << badSum * 100.0 << std::endl; 441 std::cerr << "Number of intervals = " << numIntervals << std::endl; 442 std::cerr << "result = " << result << " sum = " << sum << std::endl; 443 } 444 445 446 return result; 447 } 448 449 public: Integrate(const double a,const double b,const double acc)450 double Integrate(const double a, const double b, const double acc) 451 { 452 return Integrate(a, b, acc, !relativeErrors, acc, relativeErrors, false); 453 } Integrate(const double a,const double b,const double accAbs,const double accRel,const bool andFlag)454 double Integrate(const double a, const double b, const double accAbs, const double accRel, const bool andFlag) 455 { 456 return Integrate(a, b, accAbs, true, accRel, true, andFlag); 457 } 458 }; 459 460 #endif // _GKINTEGRATION_ 461