Some of this, sum of that

| categories: recursive, miscellaneous | tags: | View Comments

Matlab plot

Python provides a sum function to compute the sum of a list. However, the sum function does not work on every arrangement of numbers, and it certainly does not work on nested lists. We will solve this problem with recursion.

Here is a simple example.

v = [1, 2, 3, 4, 5, 6, 7, 8, 9] # a list
print sum(v)

v = (1, 2, 3, 4, 5, 6, 7, 8, 9)  # a tuple
print sum(v)

If you have data in a dictionary, sum works by default on the keys. You can give the sum function the values like this.

v = {'a':1, 'b':3, 'c':4}
print sum(v.values())

1 Nested lists

Suppose now we have nested lists. This kind of structured data might come up if you had grouped several things together. For example, suppose we have 5 departments, with 1, 5, 15, 7 and 17 people in them, and in each department they are divided into groups.

Department 1: 1 person Department 2: group of 2 and group of 3 Department 3: group of 4 and 11, with a subgroups of 5 and 6 making up the group of 11. Department 4: 7 people Department 5: one group of 8 and one group of 9.

We might represent the data like this nested list. Now, if we want to compute the total number of people, we need to add up each group. We cannot simply sum the list, because some elements are single numbers, and others are lists, or lists of lists. We need to recurse through each entry until we get down to a number, which we can add to the running sum.

v = [1, 
    [2, 3],
    [4, [5, 6]],

def recursive_sum(X):
    'compute sum of arbitrarily nested lists'
    s = 0 # initial value of the sum

    for i in range(len(X)):
        import types  # we use this to test if we got a number
        if isinstance(X[i], (types.IntType,
            # this is the terminal step
            s += X[i]
            # we did not get a number, so we recurse
            s += recursive_sum(X[i])
    return s

print recursive_sum(v)
print recursive_sum([1,2,3,4,5,6,7,8,9]) # test on non-nested list

In Post 1970 we examined recursive functions that could be replaced by loops. Here we examine a function that can only work with recursion because the nature of the nested data structure is arbitrary. There are arbitary branches and depth in the data structure. Recursion is nice because you do not have to define that structure in advance.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

Read and Post Comments

Smooth transitions between discontinuous functions

| categories: miscellaneous, nonlinear algebra | tags: | View Comments

original post

In Post 1280 we used a correlation for the Fanning friction factor for turbulent flow in a pipe. For laminar flow (Re < 3000), there is another correlation that is commonly used: \(f_F = 16/Re\). Unfortunately, the correlations for laminar flow and turbulent flow have different values at the transition that should occur at Re = 3000. This discontinuity can cause a lot of problems for numerical solvers that rely on derivatives.

Today we examine a strategy for smoothly joining these two functions. First we define the two functions.

import numpy as np
from scipy.optimize import fsolve
import matplotlib.pyplot as plt

def fF_laminar(Re):
    return 16.0 / Re

def fF_turbulent_unvectorized(Re):
    # Nikuradse correlation for turbulent flow
    # 1/np.sqrt(f) = (4.0*np.log10(Re*np.sqrt(f))-0.4)
    # we have to solve this equation to get f
    def func(f):
        return 1/np.sqrt(f) - (4.0*np.log10(Re*np.sqrt(f))-0.4)
    fguess = 0.01
    f, = fsolve(func, fguess)
    return f

# this enables us to pass vectors to the function and get vectors as
# solutions
fF_turbulent = np.vectorize(fF_turbulent_unvectorized)

Now we plot the correlations.

Re1 = np.linspace(500, 3000)
f1 = fF_laminar(Re1)

Re2 = np.linspace(3000, 10000)
f2 = fF_turbulent(Re2)

plt.figure(1); plt.clf()
plt.plot(Re1, f1, label='laminar')
plt.plot(Re2, f2, label='turbulent')
>>> >>> >>> >>> >>> <matplotlib.figure.Figure object at 0x051FF630>
[<matplotlib.lines.Line2D object at 0x05963C10>]
[<matplotlib.lines.Line2D object at 0x0576DD70>]
<matplotlib.text.Text object at 0x0577CFF0>
<matplotlib.text.Text object at 0x05798790>
<matplotlib.legend.Legend object at 0x05798030>

You can see the discontinuity at Re = 3000. What we need is a method to join these two functions smoothly. We can do that with a sigmoid function. Sigmoid functions

A sigmoid function smoothly varies from 0 to 1 according to the equation: \(\sigma(x) = \frac{1}{1 + e^{-(x-x0)/\alpha}}\). The transition is centered on \(x0\), and \(\alpha\) determines the width of the transition.

x = np.linspace(-4,4);
y = 1.0 / (1 + np.exp(-x / 0.1))
plt.figure(2); plt.clf()
plt.plot(x, y)
plt.xlabel('x'); plt.ylabel('y'); plt.title('$\sigma(x)$')
>>> <matplotlib.figure.Figure object at 0x0596CF10>
[<matplotlib.lines.Line2D object at 0x05A26D90>]
<matplotlib.text.Text object at 0x059A6050>
<matplotlib.text.Text object at 0x059AF0D0>
<matplotlib.text.Text object at 0x059BEA30>

If we have two functions, \(f_1(x)\) and \(f_2(x)\) we want to smoothly join, we do it like this: \(f(x) = (1-\sigma(x))f_1(x) + \sigma(x)f_2(x)\). There is no formal justification for this form of joining, it is simply a mathematical convenience to get a numerically smooth function. Other functions besides the sigmoid function could also be used, as long as they smoothly transition from 0 to 1, or from 1 to zero.

def fanning_friction_factor(Re):
    '''combined, continuous correlation for the fanning friction factor.
    the alpha parameter is chosen to provide the desired smoothness.
    The transition region is about +- 4*alpha. The value 450 was
    selected to reasonably match the shape of the correlation
    function provided by Morrison (see last section of this file)'''
    sigma =  1. / (1 + np.exp(-(Re - 3000.0) / 450.0));
    f = (1-sigma) * fF_laminar(Re) + sigma * fF_turbulent(Re)
    return f

Re = np.linspace(500,10000);
f = fanning_friction_factor(Re);

# add data to figure 1
plt.plot(Re,f, label='smooth transition')
... ... ... ... ... ... ... ... >>> >>> >>> >>> ... <matplotlib.figure.Figure object at 0x051FF630>
[<matplotlib.lines.Line2D object at 0x05786310>]
<matplotlib.text.Text object at 0x0577CFF0>
<matplotlib.text.Text object at 0x05798790>
<matplotlib.legend.Legend object at 0x05A302B0>

You can see that away from the transition the combined function is practically equivalent to the original two functions. That is because away from the transition the sigmoid function is 0 or 1. Near Re = 3000 is a smooth transition from one curve to the other curve.

Morrison derived a single function for the friction factor correlation over all Re: \(f = \frac{0.0076\left(\frac{3170}{Re}\right)^{0.165}}{1 + \left(\frac{3171}{Re}\right)^{7.0}} + \frac{16}{Re}\). Here we show the comparison with the approach used above. The friction factor differs slightly at high Re, because Morrison's is based on the Prandlt correlation, while the work here is based on the Nikuradse correlation. They are similar, but not the same.

# add this correlation to figure 1
h, = plt.plot(Re, 16.0/Re + (0.0076 * (3170 / Re)**0.165) / (1 + (3170.0 / Re)**7))

ax = plt.gca()
handles, labels = ax.get_legend_handles_labels()

ax.legend(handles, labels)
>>> >>> >>> >>> >>> >>> >>> <matplotlib.legend.Legend object at 0x05A5AEB0>

1 Summary

The approach demonstrated here allows one to smoothly join two discontinuous functions that describe physics in different regimes, and that must transition over some range of data. It should be emphasized that the method has no physical basis, it simply allows one to create a mathematically smooth function, which could be necessary for some optimizers or solvers to work.

Copyright (C) 2013 by John Kitchin. See the License for information about copying.

org-mode source

Read and Post Comments