Graeme Dennes has been continuing work on his Tanh-Sinh Quadrature function, and recently sent me a revised version, which can be downloaded from: Tanh-Sinh.zip
The main change is a new automatic tolerance adjustment feature which automatically increases the tolerance for badly behaved functions that will not converge to the default tolerance. The result is much better performance for a few of the sample functions. The download file also includes extensive additional notes.
Microsoft recently introduced the facility to embed a link to a live spreadsheet stored on Windows Skydrive.
This is my first attempt to use this facility. The spreadsheet below is a list of all the files published on this blog, together with a link to the latest relevent blog post. You can navigate around the spreadsheet in the usual way, and click on file names to open or download the file, or click on the blog post link to open the related post. Click on the icon on the bottom right to view the spreadsheet full size. This list is also accessible from the new Downloads page, and will be kept updated as new files are posted.
It has just been pointed out that the single span beam spreadsheet presented at Frame Analysis with Excel 1 does not work for a propped cantilever. The same applies to the spreadsheet for single span sloping beams at Frame Analysis with Excel 2.
The spreadsheets were really mainly intended for educational purposes, and the continuous beam spreadsheet at Frame Analysis with Excel 3 handles a single span propped cantilever already, but the earlier spreadsheets are handy for the quick analysis of a single span beam, so I have modified them so that they will handle the propped cantilever condition. The revised spreadsheets cane be downloaded from:
Beam1 output for propped cantilever
In my previous post about numerical integration I mentioned that I would be writing about another lesser known method providing better speed and/or accuracy in many cases. The method is known as Tanh-Sinh quadrature, and has been implemented in Excel by a reader of this blog, Graeme Dennes. Graeme has incorporated a Tanh-Sinh function along with functions for the Gauss-Kronrod method and the Romberg method, and compared their performance at calculating the integrals of 55 different functions.
The spreadsheet (including full open source code and extensive notes) may be downloaded from: Tanh-Sinh.zip.
Graeme’s notes on the origins of the method and its advantages are given below, together with some screen shots of the output.
TANH-SINH, GAUSS-KRONROD AND ROMBERG QUADRATURE PROGRAMS
by Graeme Dennes
Introduction:
This Excel VBA workbook provides three single-dimension quadrature programs as User Defined Functions (UDF) for calculating the definite integral of a non-oscillatory analytic function over a finite interval (a,b). The three methods provided are Tanh-Sinh, Gauss-Kronrod, and Romberg.
Key Purposes:
1. To demonstrate and compare the astounding speed and accuracy of the Tanh-Sinh quadrature method in comparison to the Gauss-Kronrod and Romberg methods.
2. To provide a fast, accurate, practical VBA Tanh-Sinh quadrature program with source code.
3. To hopefully inspire others to improve the performance of the Tanh-Sinh program through judicious code tuning.
Refer to the Readme1, Readme2, About, and Copyright worksheets for complete details of the programs and their usage. Extensive notes on the program are also provided in the VBA module README, including the original Fortran code used as the source for the present Tanh-Sinh program.
The Tanh-Sinh Method:
Tanh-Sinh quadrature is a method proposed by Hidetosi Takahasi and Masatake Mori in 1974. It uses the change of variables to transform an integral on (-1, 1) to an integral on the entire real line (-inf, inf). After this transformation, the integrand decays at a double exponential rate, and thus, this method was originally known as the double exponential (DE) formula, although Tanh-Sinh is but one of the D-E formulas. The key reference documents for the Tanh-Sinh method are listed in the About worksheet.
To paraphrase from the document published in 2006 by David H. Bailey titled Tanh-Sinh High-Precision Quadrature, available at http://crd.lbl.gov/~dhbailey/dhbpapers/dhb-tanh-sinh.pdf: “The Tanh-Sinh quadrature scheme is the fastest known high-precision quadrature scheme, especially when the time for computing abscissas and weights is considered. It has been successfully employed for quadrature calculations of up to 20,000-digit precision. It works well for functions with blow-up singularities or infinite derivatives at endpoints, demonstrating one of its strengths.”.
To paraphrase from the document published in 2005 by David H. Bailey, Karthik Jeyabalan, and Xiaoye S. Li titled “A Comparison of Three High-Precision Quadrature Schemes”, available at the web site: http://crd.lbl.gov/~dhbailey/dhbpapers/quadrature-em.pdf, “The Tanh-Sinh and Gaussian quadrature programs have proven their value in a certain domain of quadrature problems. The Gaussian quadrature methods are very fast and accurate for continuous, well-behaved integrands, and where relatively lower precision calculations are used. However, for functions that are not well behaved in the interval, especially near the endpoints, its accuracy is quite poor. Another major drawback of the Gaussian schemes is that their initialisation time (the generation of the abscissas and weights) is many times higher than that of the Tanh-Sinh scheme. On the other hand, the Tanh-Sinh scheme is able to evaluate problems with infinite derivatives and blow-up singularities at the endpoints to the full precision required.”.
Now to Today!
Although 36 years have passed since the Tanh-Sinh scheme was first proposed, the method is still very much unknown outside of a small number of mathematical researchers and research institutions. Even so, much work has been done in recent years researching the speed, accuracy and application of the Tanh-Sinh method by David H. Bailey of the Lawrence Berkeley National Laboratory, California USA, and Jonathan M. Borwein of the University of Newcastle, NSW, Australia, to name but two of the modern day champions of the Tanh-Sinh method. David H. Bailey is probably the most prolific researcher and writer regarding this method, and most of his papers are freely available for download. Further, the method is so relatively new that very little of its subject matter has appeared in mathematical texts to this time. Much of the published information is in authored papers. Try an Internet search on ‘tanh sinh’.
Overall, the Tanh-Sinh scheme appears to be the preferred numerical integration method for the majority of integrand types, and it has excellent accuracy and runtime performance as well, with its initialisation time being less than for Gaussian quadrature. Still, the Gaussian integrator can be quicker than the Tanh-Sinh integrator for some functions which are well behaved in the full interval, yet slower than the Tanh-Sinh method for many types of functions, or where extended precision and accuracy are required.
As the last concluding remark, in the report by D. H. Bailey and X. S. Li in 2003 on a comparison of high-precision quadrature schemes: “Overall, the Tanh-Sinh scheme appears to be the best. It combines uniformly excellent accuracy with fast run times. It is the nearest we have to a truly all-purpose quadrature scheme at the present time.”.
The Present Program:
This Excel VBA Tanh-Sinh program combines the fastest speed and highest accuracy of any Excel VBA quadrature program this author has witnessed. A range of test functions is included for integration by the three methods, and the integral results, the calculation times, and the true answers are presented for comparison. The speed of the Tanh-Sinh method in comparison to other methods almost has to be seen to be believed, and its accuracy seems to be almost perfect, and for many of the functions listed, it IS perfect, being accurate to the full 15 significant digits of Excel.
Try these three integration programs, and compare their results (speed and accuracy) with your own integrators. I think you’ll be as impressed as I was with the performance of the Tanh-Sinh method.
As noted at the very start here, I’m hopeful others will apply their programming skills towards enhancing the performance of the Tanh-Sinh routine, and present their refinements for the benefit of all.
In conclusion, this really isn’t about numbers. It’s about insight.
Your comments and suggestions are sought.
Graeme Dennes
September 2010
Tanh-Sinh Function output, click for full size view
Gauss-Kronrod Function Output
Romberg Function Output
I have modified the fern input parameters in the spreadsheet presented in the previous post to match the layout used by Barnsley and others, so that examples such as those given at the Wikipedia article can be entered directly. The new file can be downloaded from: Fern chart-Barnsley.zip :
Modified Fern Parameter Input
In doing so I also tidied up the VBA matrix multiplication algorithm, and compared it with using the worksheetfunction.MMULT function. The example above is for calculating and plotting 1 million rows, using Excel 2010. It can be seen that:
Edit 4th Oct 10: I meant to mention that the times recorded here were done on a Dell laptop computer with an Intel P8700 processor (2.53 GHz) and 4 MB RAM, and with a finite element analysis program running in the background, using the full resources of one core virtually all the time. Re-running without any hungry background processes made virtually no difference to the VBA running time (as would be expected since VBA only uses one core), but also made very little difference to the times for the calculation using the MMULT function, or for the re-plotting time. That is surprising since Microsoft say they put a lot of effort into improving the performance of Excel 2010 (compared with 2007). It looks to me like there is plenty of scope for further improvement here.
Times for plotting 40,000 rows are shown below:
Plot times for 40,000 rows
The Wikipedia article links to more examples at: http://www.home.aone.net.au/~byzantium/ferns/fractal.html . Some of the different fern varieties reported in that paper have been plotted in the spreadsheet:
Parameters for four different fern types
Modified Barnsley Fern
Culcita Dubia
"Fishbone" Fern
Cyclosorus Fern
Newton Excel Bach, not (just) an Excel Blog 