We take requests!
Is there a math topic you’d like to learn more about? Would you like to see “illustrated” examples of an algorithm or a calculation technique?
If there’s something that you’d like to model numerically, or if you need a faster way to calculate something you already have, let us know. We might just make that the topic of a future post.
Math for Mere Mortals 
I would like to connect with you. Please check out my blog http://www.alfredexcelvachris.wordpress.com
I am starting my blog with the numerical techniques that I developed while I worked at Grumman Aerospace. These techniques all share a common root of graphical construction. Later on I will add in my Excel VBA tools for code analysis.
Best Regards
Alfred F Vachris Jr Senior Excel VBA Developer ,Chair NYPC Excel SIG
Hi! I just downloaded your bicubic interpolation function, and it works great. I am in need of a interpolation function for 3D tabular data, which takes an x value and an f(x,y), and determines the y value. Any help?
You can do this by combining the optimizer and the interpolation function. The interpolation would take x and y and produce f. The optimizer would then take x as the “by changing” variable. The merit function would be the squared error between f_optimum and f(x, y). In this way the two Excel functions work together to optimize over a 3D surface. The only limitation is that one of the variables (in this case y) has to remain fixed because the optimizer only changes one at a time.
https://mathformeremortals.wordpress.com/2014/04/05/minimize-and-minimizenonnegative-spreadsheet-optimization-v6/
Thanks for your question. It’s a good one because Excel is capable of doing it, but it’s not trivial to set up!
It sounds like you have a 3D surface f(x, y). Given x, you need to find the y that produces a certain value of f. If my understanding is correct, you can use the Minimize or MinimizeNonnegative functions along with the bicubic interpolation function to solve for y. In other words, you’d use both Excel scripts together. The merit function would be the squared error of f: Merit = (f_target – f) ^ 2, and the y value would be in another cell. The minimizer function would change the value of y until it minimizes the error in f. The answer would be the value of the cell that contains y. Let us know if you need help setting it up or would like to see an example. You can do the same thing with the Excel solver, but this approach is automatic; there’s no button to click on or solver dialog box to mess with.
https://mathformeremortals.wordpress.com/2014/04/05/minimize-and-minimizenonnegative-spreadsheet-optimization-v6/
Great website and examples Kintaar. How about a Solver replacement in an array function that can handle Mixed Integer and QP problems ? To be used for example in obtaining optimal portfolio weights given cardinality and other constraints etc.
Thanks for the recommendation. The logistics of that would be tricky. Excel doesn’t accommodate a streamlined way to enter the constraints and boundary conditions for complex problems. That’s why the optimization function we wrote is very simple and can be done within a spreadsheet formula. The Excel Solver can’t do the kinds of problems you ask about, and rewriting it would be too big of a project and would involve a new user interface and implementing the cutting edge of optimization technology… It’s possible and would be a nice, new numerical toy, but it’s beyond our capabilities.
I have been using RegularizeData3d for about 6 months now. It short, it produces a lookup table that has all the properties I desire.
I work with a lot of multidimensional test data. From the test data, I need to produce n-dimensional lookup tables. The properties that I need are
1. Good fit with smoothing of the test data.
2. A small amount of extrapolation. Reasonable extrapolation is not well done with fitting polynomial type functions. There is no guarantee that the polynomial type fit is well behaved outside the fitted data. However, the second derivative constraint in regularization enforces that the lookup table becomes more linear as the query point moves away from the fitted data. This is very nice property!
Because RegularizeData3d only handles 3d data, I plan to rewrite a version of it for nD data. I hope that it inspires you or others to write a better version in n-dimensions.
Any comments or suggestions would be helpful.
It’s great that you are finding the function useful for your work! Presumably you are speaking of the Matlab function, not the Excel function. One of the challenges of solving these systems of equations is the degree of the matrix being solved. When the output domain is a 1D line, you get a pentadiagonal matrix. No problem. But as the output domain grows in dimensions, the system of equations becomes larger in degree. For example, a teeny 5×5 output grid has a degree of 21. A 5x5x5 output cube would have a degree of 101. As you add dimensions, the system of equations grows rapidly in degree because the second derivatives are linking elements that are further and further away from each other. The matrix reordering algorithm helps a lot, but the sheer size of the calculation could become prohibitively large. I do encourage you to give it a try and let us know how it goes, especially with regard to the calculation speed. Good luck, and thanks for your feedback!
On Sun, Mar 27, 2016 at 12:02 AM, Math for Mere Mortals wrote:
>
I am putting the code for regularizeNd here:
https://github.com/jasonnicholson/regularizeNd/
My outline of the algorithm is here:
https://github.com/jasonnicholson/regularizeNd/wiki/Outline-of-algorithm
I have been researching several aspects of writing an nD version of regularizeData3d.
1. Reordering of the sparse matrix. I have found that the MATLAB backslash operator uses the SuiteSparseQR solver for the least squares problem, min(||Ax-b||). The SuiteSparseQR solver uses COLAMD for reordering which you can find out by examining the spparms.m function code. spparms.m says:
% Solving rectangular matrices within \ and /:
% The SuiteSparseQR QR-based solver uses COLAMD.
There is another option for reordering in using AMD. See the spparms.m and spparms(‘autoamd’).
In my research of SuiteSparse, the SuiteSparseQR with column reordering via colamd is pretty optimal and very good even for large matrices. You can see this by running the SuiteSparseQR test suite via Tim Davis’s website: http://faculty.cse.tamu.edu/davis/suitesparse.html . Also, watch his youtube video on SuiteSparse and at 34 minutes he talks about SuiteSparseQR and performance with different reordering algorithms (note this was recorded in 2013): https://www.youtube.com/watch?v=7ph4ZQ9oEIc
So basically, I think I have my solver chosen.
2. Implementing general linear interpolation on unevenly spaced grid. Implementing the linear linterpolation (bilinear, trilinear, quadlinear, quintilinear, etc.) is straight forward. The biggest problem I have run into is locating the cell that the scattered points are located in on an unevenly spaced grid. I haven’t looked closely at RegularizeData3d yet to figure out how you are doing this; I will soon. I assume that a combination of linear search and binary search is probably the best bet. I have to be careful to vectorize the search for speed purposes. Also, for now I have opted to write a evenly spaced (in each dimension) version of regularizeNd; this should be easier to implement than the irregular spaced grid because the cell index can be directly calculated. Once I have written the evenly spaced version and debugged it, I will move on to uneven spacing.
number of points needed for linear nD interpolation: 2^n (2 points in each dimension)
1d – 2 points
2d – 4 points
3d – 8 points
4d – 16 points
5d – 32 points
etc
3. Implementing cubic interpolation on even or uneven spaced grid. General cubic interpolation seems like Lagrange Shape functions in the Finite Element Method (my reference is the Schaum’s Outline for Finite Element Analysis, pages 173, 177, 228, 233). However, I find no documentation comparing Lagrange polynomials to tricubic or bicubic interpolation via google. I don’t see why this comparison has not been made. The Lagrange polynomials for an even spaced grid is where I am going to start. In my research I found a lot of talk about how Lagrangian polynomials can be unstable in that perturbations of the nodal values can cause large changes in the shape of the interpolation functions for high degree Lagrange polynomials. I am hoping that the Lagrangian polynomial approach will be good enough for regularizeNd because of how easy deal with the shape functions are. If you drop me an email, I can send you pictures and more explanation from my resources (mainly Schaum’s Outline).
MATLAB uses the cubic convolution in its griddedInterpolant function. I don’t know what the cubic convolution is even though I have found that bicubic wiki page has a short explanation of the cubic convolution. This might be a better approach but I am unfamiliar with this.
number of points needed for cubic nD interpolation: 4^n (4 points in each dimension)
1d – 4 points
2d – 16 points
3d – 64 points
4d – 256 points
5d – 1024 points
etc
We should discuss this elsewhere, as the messages are getting long and detailed for this forum. Here is a summary.
What you’re doing is a really cool idea!
1. Yes.
2. Generalize for uneven spacing to begin with. You’ll be happy you did. Matlab uses histc to find the indexes for interpolation.
3. Oscillation is not a problem, even though we are using cubic polynomial interpolation.
When you hear the words “cubic interpolation,” you automatically think of oscillation issues. That is the knee-jerk response (no offense) that the professors profess, but that concept doesn’t apply in this technique. The interpolation we are doing relates to an output surface, which is guaranteed to be smooth. One way to think of this is to consider the second derivatives. There is a chain of them, all overlapping and all linked together. This “linking” strategy penalizes concavity. Another way to think about it is to consider that the output surface doesn’t pass through all of the input points. In strict interpolation, a cubic curve is constrained to pass through four points. This technique uses interpolation without imposing that constraint. Essentially you’re fitting a cubic curve to a single point, not to four points. If you have four input points, you’ll have four distinct cubic equations. i.e. one point per cubic equation – not 4 points per cubic equation. Uneven grid spacing doesn’t cause any harm, and for the same reason.
There can be some oscillation in the output, but it will always have a smaller range (albeit in +/- directions) than the input points that caused it. The examples in the book don’t have that property. The easiest way to see this is in Excel in the 2D version. Put in four input points: three collinear points at y=1 coordinate and one oddball point at y=2. The output line will wiggle a little bit between the four input points, but it will not oscillate wildly.
The cubic interpolation algorithm is a verbatim implementation of the formula in the Wikipedia article. If your grid has 50×50 points, you’ll have roughly 100 sets of interpolation coefficients, derivatives, etc., so there is little to be gained by making this part of the code more efficient.
Awesome website, really helpful and informative content. Right now I’m using Matlab to work with implied volatility services and I’m looking for a way to use bicubic interpolation on these surfaces. It seems like a trivial issue but unfortunately Matlab’s bicubic interpolation function can’t deal with irregularly spaced data like yours can. Is there any way you could write a matlab version of your function? I’m sorry if this is a lot to ask but it would supremely helpful if you could and I’d really appreciate it.
Thanks a bunch,
John
Hi, John. Thanks for the compliments. Have you considered using the spline option in Matlab? I know it isn’t quite what you asked for, but this may be an acceptable workaround for what you are trying to do. Matlab’s inability to handle nonuniform grid spacing with cubic interpolation is frankly very mystifying. That type of interpolation involves calculating something once and reusing it a lot of times, so there are advantages to having a uniform grid spacing. Even still, nothing prevents them from detecting whether the grid is uniformly spaced (or detecting *where* the grid is uniformly spaced) and handling the math accordingly.
On Wed, Jun 29, 2016 at 1:56 PM, Math for Mere Mortals wrote:
>
Here is a matlab version:
https://www.mathworks.com/matlabcentral/fileexchange/46223-regularizedata3d
An n-D version is in process here:
https://github.com/jasonnicholson/regularizeNd
It’s not exactly interpolation, but that will give similar results with a small smoothness value like 0.001. Good idea, Jason! It’s interesting to note that you can use this function to calculate a volatility surface from raw trade transaction data. Perhaps that’s what the actuaries use (albeit with tons of smoothing) at the banks that provide these surfaces to their customers. The market does not buy and sell options in convenient gridded increments with a smooth surface profile, but the banks’ volatility surfaces are always so. I have wondered if the artificial smoothing represented an arbitrage opportunity for those with access to the raw data…
Hi,
Thanks for your posts on regularisation – I have learnt a lot! Please may I know how I can reference your work in my dissertation?
Regards,
Rithvik
Hi good day,
Could you please help me. How to use the goal seek in excel with AHT(Average handling time). like for example:
Current AHT: 485
Target AHT: 420
Remaining Days to hit the target: 5
Question is. how to use the goal seek analysis in excel for me to know what will be my aht in the remaining days to hit the target.
or can you please help me the formula use in excel for me to know what will be my AHT in the remaining days to hit the target
It’s an interesting question, but you’ll have to give more specifics about the problem statement. Without knowing how the problem is formulated, it’s impossible to say what your AHT needs to be in the remaining days in order to meet your target AHT. More information would be helpful.
On Sun, Jul 16, 2017 at 11:48 AM, Math for Mere Mortals wrote:
>
There are some attention-grabbing deadlines on this article however I don’t know if I see all of them heart to heart. There’s some validity but I’ll take maintain opinion till I look into it further. Good article , thanks and we would like extra! Added to FeedBurner as well
Hi Kintaar – It looks as if this site may be abandoned – but I am wondering if you could offer help migrating the “Bicubic Interpolation Excel Spreadsheet Function” to Google Sheets Scripts. While Excel is certainly still relevant, Sheets has come a long way and is much more portable.
Not a bad idea! I will have to check on the scripting language to see what it can do.
On Wed, Aug 4, 2021 at 10:22 AM Math for Mere Mortals wrote:
>
Google Apps Scripts is a subset of JavaScript extended for Sheets. Almost everything from JS is there along with most of the spreadsheet functions. I started to convert the code but am not comfortable enough with the mathematical concepts to efficiently do the conversion without a lot of trial, error and frustration. This small site is a wonderful resource – thank you for the well thought out and implemented explanations and work.
Hi Kintaar
– I have ported your code (quick and dirty for ranges, not arrays) to Google Sheets Scripts. It appears to work as expected.I go by beananimal I can be reached at gmail if you have any interest in my port. Thank you again for the great site and work.