Computationally intensive software programs can have a sharp performance profile. What I mean with sharp profile is that, there might be a couple of functions which are most time consuming. Very often such expensive functions are trigonometric functions. A way to increase performance is by use of approximations for trigonometric function. There is a trade of between speed and accuracy. Typically, with a loss of precision in the 3rd decimal place it is possible to increase the speed of the trigonometric functions by 2 to 3 times. Here at CERN, my project is to optimize performance of AliRoot. I have been using tools like valgrind etc to generate a performance profile. More details on that can be found on my previous blog post here. After analysing the performance profile, it was found that the arctan function was called 5 billion times in a typical run and consumed about 5% of the running time. Thus, I am trying to approximate the arctan function and get a speedup. Rest of this post explains the Padé approximations in general and how it can be computed on a CAS (Computer Algebra System) like Maxima. My analysis and design of Padé approximation for arctan function is not covered in this post. I shall put that up too soon.
What is Padé Approximations
Padé approximations are rational polynomial approximations derived typically from a Taylor series expansion. In simplistic terms the infinite terms of a Taylor series are made into a polynomial rational function (ie. polynomial over a polynomial).
Just for the reader to get a practical feel of this, follows next is a approximation of sine function with polynomials of degree 2.
There is an excellent tutorial which explains all the mathematical details to derive the coefficients of the approximating polynomials. It explains with an example how the approximating polynomials are derived. The article on Pade Approximation can be downloaded from Here.
Padé Approximation using Maxima
Maxima is a CAS (Computer Algebra System). A CAS can perform symbolic algebraic manipulations. This is particularly handy when manipulating large polynomials. Maxima is a Open Source software under GPL (GNU Public Licence). It is a system for the manipulation of symbolic and numerical expressions, including differentiation, integration, Taylor series, Laplace transforms, ordinary differential equations, systems of linear equations, polynomials, and sets, lists, vectors, matrices, and tensors. Maxima yields high precision numeric results by using exact fractions, arbitrary precision integers, and variable precision floating point numbers. Maxima can plot functions and data in two and three dimensions.
Please follow the screenshot below which shall help you to compute a Pade approximation for a taylor series upto given degree. The GUI for maxima can be initiated with the command `wxmaxima`.
The function taylor() generate a taylor series. In the example above, we are generating a taylor series for sin(x) with the variable x centred at 0 and we need 3 terms of the taylor series. This taylor series is an input for the Pade approximation. This function requires a taylor series. Here the arguments 2,2 are the degrees of numerator and denominator for rational approximating polynomials. You need to do a shift-enter to execute the command.
Pade approximations are a very powerful and handy way of approximation of a taylor series. This short post has the material which would enable you to practically use Pade approximations for your own purpose.