Distributed Linear Interpolation

In a previous article, I introduced a vectorized polynomial interpolation algorithm that is extremely efficient, generating reasonably accurate interpolations of functions in about one to three seconds. You can of course refine the results, which I discussed as well, but the point being, that by using vectorization, we can turn what are otherwise brute force techniques, into elegant and efficient solutions to problems in computing.

I realized that you could take a similar approach to problems that are by their nature distributed, making use of a large number of linear approximations. For example, imagine a gas expanding in a volume, and assume that you want to predict the density in the regions over time. You could subdivide the volume into equally sized cubes, and then use a series of linear equations to predict the densities in each cube. Specifically, if we have N cubes, then we would need N linear equations, with each equation f_i(t) = t\theta_i corresponding to a cube in the volume, approximating its density over time.

This can be done using almost exactly the same code I introduced in the previous article. However, if N > 10, its implementation becomes problematic, simply because there are too many permutations to consider, unless you’re using a truly massively parallel machine, in which case it should be fine. But as a workaround, you can use a Monte Carlo method instead, rather than iterate through all possible permutations of each \theta_i. That is, simply generate a massive number of coefficients, which is vectorized in Octave, rather than all possible coefficients at a given level of granularity. For context, it takes .018 seconds to generate 1.5 million random numbers in Octave, running on an iMac, which is the only initial step necessary to make use of the code I introduced in the previous article.

You could of course repeat this process, adding a constant term, or perhaps higher dimensional terms, creating quadratics, cubics, and other higher dimensional approximations, if necessary, for accuracy. Simply fix the coefficients obtained from the first application, and repeat the same process, generating a large number of possible coefficients for the higher or lower dimensions terms.

An additional upside to this approach is the fact that evaluating a polynomial is also vectorized in Octave, an example of which is included in the code I introduced in the previous article. This implies that evaluating the behavior of a system like an expanding gas, or a moving fluid, can be implemented in a distributed manner, which is not only more efficient, but realistic, in that the parts of a system that aren’t physically proximate, are probably independent, at least in the short run.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s